 |
 |
 |
 |
 |
 |
Startseite » Forum » Anzahl der Wege zwischen zwei beliebigen Knoten
Anzahl der Wege zwischen zwei beliebigen Knoten
Universität / Fachhochschule
Sonstiges
Tags: Graphentheorie, vollständiger Graph
 
|
  |
|---|
|
Hallo. Die Frage lautet wie folgt: Wie viele verschiedene Wege der Länge gibt es zwischen zwei beliebigen Knoten des vollständigen Graphen Kn? Die Lösung dazu findet ihr im Anhang. Könntet ihr die Lösung kurz anhand eines vollständigen Graphen mit 4 Knoten erläutern? Dann kann ich es besser nachvollziehen.  Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Hallo, die Lösung ist eine Standard-Formel der Kombinatorik. Du könntest diese Formel aufschreiben und umformen und Dir die Definition von "Weg in einem Graphen" anschauen. Gruß pwm |
 |
|
Hmm. Es heißt nehm ich an über weil es um den Weg zwischen zwei Knoten geht und dieser höchstens lang sein kann. Und die kommt daher, dass man die Anzahl der Wege zwischen den restlichen Knoten zählt, die ausgehend von den Endknoten durchlaufen wird? Aber warum wird danach nochmal mit multipliziert? |
|
|
|
Also ich würde mal die Definition von "Weg" hier hinschreiben und mich dann fragen, wie man einen solchen Weg aufbauen kann. Gruß pwm |
|
|
|
Ein Graph heißt Weg, wenn die Knoten paarweise verschieden sind. Das versteh ich. Die einzige Idee die ich habe ist, dass man sich jeden zum Anfangsknoten benachbarten Knoten anschaut und schaut, wie viele Möglichkeiten es gibt, einen Weg der Länge von jedem dieser Knoten zum Endknoten zu bilden, ohne dabei den Knoten zu kreuzen. da man die Kante die vom Knoten ausgeht außen vor lässt. Ist meine Grundidee richtig? Der Binominalkoeffizient ist dadurch definiert, auf wie viele verschiedene Arten man Objekte (hier Kanten) aus verschiedenen Objekten (die Anzahl der Kanten) auswählen kann. Der Weg hat eine Länge von . Demnach haben die Wege von (Nachbarn von die Länge . Nun verstehe ich aber nicht, warum es in der Lösung heißt. Wenn man den Knoten nicht mitrechnet, gibt es immer noch Knoten (Objekte), aus denen man den Weg auswählt. Auch verstehe ich nicht, warum im Anschluss nochmal mit multipliziert wird. Dass die Rechnung aufgeht weiß ich, nur weiß ich nicht anhand welcher Überlegung man sich die Formel so herleitet. Deshalb frage ich ja, weil ich in Mathe bei weitem nicht der beste bin. Aber man lernt dazu. |
|
|
|
Du hast Knoten zur Verfügung und 2 davon sind als Start und Ziel bereits ausgewählt. Für einen Weg der Länge benötigst du Punkte. Also musst du dir aus den verbleibenden Knoten noch auswählen . Nun musst du noch zählen, wie viele verschiedene Wege es mit diesen Punkten gibt. Da Start und Ziel vorgegeben sind, kannst du nur die "inneren" Knoten permutieren Multiplikativ zusammengesetzt ergibt das deine Lösung. |
 |
|
Super, danke. :-) |
1251835
1251352