Städte Verbinden wie viele Möglichkeiten?
Hallo,
also wenn es 2 Punkte gibt kann ich die ja einmal verbinden. Bei 3 Punkten gibt es zwei Möglichkeiten sie zu verbinden oder? Bei 4 gibt es sechs Möglichkeiten. Wie sieht es dann z.b bei 20 Punkten aus? Gibt es da ne Formel oder wie rechnet man das aus?
Danke
5 Antworten
Ok Danke. Aber laut deiner aussage gibt es bei 4 Punkten 24 verschiedene Möglichkeiten sie zu verbinden. Mir ist bekannt das es aber nur 6 gibt.
Jetzt ist mir doch glatt ein Lapsus unterlaufen n!/n im gerichteten Fall und n!/2n im ungerichteten, weil Zyklen mit gleichem Startpunkt ohne Beachtung der Richtugn auch noch zusammenfallen.
Wenn ich mir die Tags anschauen, befasst Du Dich mit dem TSM-Problem (Travelling Salesman)?
Sei n die Anzahl Glieder, so sind die Verbindungsmöglichkeiten
n!. Das ! ist ein mathematisches Zeichen und heißt Fakultät. Da verbirgt sich folgendes dahinter:
4!=1*2 *3 * 4
5!= 1 *2 * 3* 4* 5
usw.
Doppelte Verbindungen sind hier aber ausgeschlossen, damit kommst du mit der Fakultät hier nicht weit.
Wenn die Frage ist, wieviele Verbindungsstrecken es zwischen den Punkten (Städten) gibt, dann ist die Frage eigentlich:
Wieviele 2er Gruppen kann ich aus n Elementen bilden, ohne zurückzulegen. D.h. die Paarung a,b ist mit b,a identisch. (Die Richtung der Verbindung zwischen den Städten spielt keine Rolle).
Es gilt allgemein n über k Gruppen der Größe k lassen sich bei einer Menge der Größe n in dieser Weise bilden:
n über k=n!/( k! * (n-k)! ). Wir kürzen und erhalten für den speziellen Fall: n*(n-1)/2.
Die Frage findet sich unter anderem auch in der Graphentheorie: Wieviele mögliche Kanten besitzt ein Graph mit n Knoten.
(n*n-1)/2
Bei drei Punken gibt es 3 Möglichkeiten
A mit B, A mit C und B mit C
n*(n-1)/2
@Einstein0815
Also, ich habe zwar auch einen Fehler gemacht, es muss aber heißen n!/n bzw. (n-1)!.
Was du hier gepostet hast ist die Gaußsche Summenformel, mit der man 1+2+3+4+5+...+n ausrechnet.
Yep! Liest man sich die Aufgabenstellung noch einmal genau durch, so fällt auf, dass KunFu eigentlich selber überhaupt keine Ahnung hat, was er eigentlich will, bzw das nicht vernünftig erklären kann. Dumm gelaufen für ihn!
Achtung Rundreisen sind wieder eine völlig neue Fragestellung, dies wäre n!/n, was im Falle von n=4 mit der Anzahl der möglichen Verbindungen (Kanten) zusammenfällt. (Grund: Jede Reise mit n Punkten kann in einem der n Punkte beginnen, ohne daß ich sie unterscheiden müßte).
Im gerichteten Fall stellt sich das erneut anders dar, oder aber wenn der Startpunkt nicht mehr frei wählbar ist.