User Image User
User Image User

Noch Fragen?

Komplexität

Wieviel Möglichkeiten gibt es x Punkte miteinander zu verbinden? Formel?
Frage Nummer 32577
Antworten (9)
Überleg selber: Den ersten Punkt kannst du mit wie vielen anderen Punkten verbinden? Mit allen außer sich selber, also (x-1) Punkten. Den zweiten Punkt kannst du ebenfalls mit (x-1) Punkten verbinden, allerdings steht die Verbindung zu Punkt 1 ja schon, die darfst du nicht doppelt zählen, bleiben für Punkt 2 (x-2) Verbindungen. Punkt 3 ist nun schon mit Punkt 1 und Punkt 2 verbunden, bleiben als mögliche neue Verbindungen (x-3) übrig.

Du erkennst das Prinzip? (x-1)+(x-2)+(x-3)+…. +(x-x)
Der letzte Punkt x ist am Ende schon mit allen verbunden, daher hat er mit (x-x) null neue Verbindungsmöglichkeiten. Kannst du also weglassen und mit dem vorletzten Punkt, also( x-1) beenden. Bleibt (x-1)+(x-2)+(x-3)+…+(x-(x-1))
Das brauchst du jetzt nur noch eleganter aufzuschreiben. In der Mathematik setzt man ein Summenzeichen dafür ein, das große griechische Sigma. Oben drüber kommt der Endwert, bei dir (x-1), darunter eine Laufvariable samt Startwert, hier k=1, dahinter die Funktion, also was mit den Zahlen zwischen Start- und Endwert passieren soll, bevor sie addiert werden, bei uns (x-k). Wie das korrekt aussieht, liest du bei Wikipedia, hier kriege ich Summenzeichen nicht hin.
Diese Rechnung ist falsch.
Für 3 Punkte ergäben sich (3-1)+(3-2)=3 Möglichkeiten.
Tatsächlich gibt es aber 8 Möglichkeiten:
1. keine
2. jeder mit jedem
3. P1 mit P2
4. P2 mit P3
5. P1 mit P3
6. P1 mit P2 mit P3 (keine Verbindung zwischen P3 und P1)
7. P2 mit P3 mit P1 (keine Verbindung zwischen P1 und P2)
8. P3 mit P1 mit P2 (keine Verbindung zwischen P2 und P3)
[br]
Bei mehr Punkten wird es noch komplizierter.
es ist jedesmal nur eine Möglichkeit
Aber es geht noch einfacher: Du hast beim Betrachten der Formel am Ende meines ersten Beitrages ja gemerkt, dass der letzte Teil der Reihe (x-(x-1))= 1 ist. Der vorletzte wäre (x-(x-2)) gewesen, also 2, der drittletzte (x-(x-3))=3.

Also kannst du deine Summe errechnen durch die Addition aller Zahlen von 1 bis (x-1). (Du erinnerst dich: x-1 war die Anzahl der möglichen Verbindungen für den ersten deiner Punkte.) Das schreibst du mit Summenzeichen als: Summenzeichen mit unten k=1, oben x-1 und Funktion k.
Serofine: Ich bin davon ausgegangen, dass die maximale Zahl an Verbindungen zwischen den Punkten gefragt war, also jeder Punkt mit jedem anderen zu verbinden ist. Ginge es um eine Art Wegstrecke, auf der alle Punkte liegen müssten, aber jeder nur einmal besucht werden dürfte, läge ich natürlich falsch: Ich könnte dann bei jedem der x Punkte beginnen, (Start der Formel: x*), hätte dann als erstem Teil des Weges die Wahl zwischen der Verbindung zu jedem der anderen Punkte (x-1). (Gesamtformel bis hierher: x*(x-1) ) Nun bliebe für die zweite Wegstrecke jeder noch nicht besuchte Punkt (x-2) als denkbare nächste Station übrig. (Gesamtformel bis jetzt: x*(x-1)*(x-2)) Wie es weiter geht, liegt auf der Hand: x*(x-1)*(x-2)+(x-3)*…*(x-(x-1)) Wenn man am vorletzten Punkt (x-1) angekommen ist, bleibt nur noch eine Wahlmöglichkeit, nämlich die zum letzten Punkt x, der keine weitere Option besitzt, zu einem noch nicht besuchten Punkt weiter zu führen. Die Formel endet daher mit …*(x-(x-1)).
Serofine: Den Fall, keinen der Punkte oder nur einzelne zu verbinden, lasse ich mal außen vor. Gefragt war nach Möglichkeiten, die Anzahl von Punkten miteinander zu verbinden, und sie sind eben nicht verbunden, oder eben nicht in der gefragten Zahl, wenn du welche von ihnen ausnimmst.
Gefragt war nach der Anzahl der Möglichkeiten x Punkte zu verbinden.
Und "nicht verbunden" ist auch eine Möglichkeit der Verbindung.
@serofine die Frage impliziert, dass verbunden wird und nicht nicht verbunden.
"Nicht verbunden" ist keine Möglichkeit der Verbindung sondern ihr Gegenteil.