Bestimmen Sie die Anzahl der einfachen Zyklen mit dem Startknoten 0, die alle Knoten des Graphen enthalten.

Question

Aufgabe:

(b) \( G \) sei der ungerichtete (schlingenfreie) Graph mit den Knoten \( 0,1, \ldots, n-1(n>2) \), bei dem jeder Knoten mit jedem anderen Knoten durch eine Kante verbunden ist. Bestimmen Sie die Anzahl der einfachen Zyklen mit dem Startknoten 0, die alle Knoten des Graphen enthalten. Dabei sollen zwei Zyklen, die die gleichen Kanten enthalten, nicht als verschieden betrachtet werden.

Ansatz/Problem:

Ich habe mir das zuerst mal mit einem Graph mit nur 3 Knoten angeschaut da komme ich dann auf n-1 Zyklen, auch bei einem Graph mit 4 Knoten komme ich auf die selbe Anzahl an Zyklen. Also sollte dies auch für die folgenden gelten oder irre ich mich?

3 Knoten (0-2)-> <0,1,2,0> u. <0,2,1,0>

4 Knoten (0-3) -> <0,1,2,3,0> <0,2,3,1,0> und <0,3,1,2,0>

Beim letzten Satz bin ich mir unsicher ist damit gemeint Zwei Zyklen die exakt die gleichen Kanten beinhalten und ja ich weiß bei ungerichteten Graphen ist die Kante 0,1 und 1,0 die gleiche Kante, oder auch schon wenn eine einzige Kante so schon in einem anderne Zyklus vorkam?

Answer 1

3 Knoten (0-2)-> <0,1,2,0> u. <0,2,1,0>

Du hast die Forderung "Dabei sollen zwei Zyklen, die die gleichen Kanten enthalten, nicht als verschieden betrachtet werden." nicht erfüllt.

4 Knoten (0-3) -> <0,1,2,3,0> <0,2,3,1,0> und <0,3,1,2,0>

Das ist richtig.

Allgemein kann man einen der gesuchten Zyklen im Graphen mit \(n\) Knoten konstruieren, indem man aus einem Zyklus des nächstkleineren Graphen eine Kante entfernt und den Knoten \(n\) mit den Enden des so entstandenen Weges verbindet.

Das liefert eine Rekursionsformel für die Anzahl der beschriebenen Zyklen.

Comments

Hallo, ja es war spät und habe es auch einfach nicht gesehen ^^, ich bin mir auch aktuell nicht sicher ob ein Graph mit 3 Knoten überhaupt zur Aufgabe zählt habe jetzt erst gesehen das man n > 2 wählen soll. Ich habe jetzt einfach mal noch 5 und 6 Knoten Pfade probiert und komme auch bei diesen auf n-1 Zyklen, vorausgesetzt da hat sich kein Fehler eingeschlichen

---

Graph mit den Knoten \( 0,1, \ldots, n-1(n>2) \), bei dem jeder Knoten mit jedem anderen Knoten durch eine Kante verbunden ist.

Ein solcher Graph heißt vollständiger Graph und er wird üblicherweise mit \(K_n\) bezeichnet.

einfachen Zyklen mit dem Startknoten 0, die alle Knoten des Graphen enthalten.

Ein solcher Zyklus heißt Hamiltonkreis.

Die Aufgabe lässt sich dann kürzer formulieren durch "Bestimme die Anzahl der Hamiltonkreise in \(K_n\) für \(n>2\)".

ob ein Graph mit 3 Knoten überhaupt zur Aufgabe zählt habe jetzt erst gesehen das man n > 2 wählen soll.

Nun ja, es ist \(3>2\), also gehört der \(K_3\) zur Aufgabe.

Der Hamiltonkreis im \(K_3\) sieht so aus:

        \(\langle 0,1,2,0\rangle\)

4 Knoten (0-3) -> <0,1,2,3,0> <0,2,3,1,0> und <0,3,1,2,0>

Diese drei Kreise kommen wie folgt zustande:

• \(\langle 0,1,2,3,0\rangle\) entsteht aus dem Kreis \(\langle 0,1,2,0\rangle\) indem man die Kante \(2-0\) entfernt und die Kanten \(2-3\) und \(3-0\) hinzufügt.
  
• \(\langle 0,2,3,1,0\rangle\) ist der gleiche Kreis wie \(\langle 0,1,3,2,0\rangle\). Dieser entsteht aus dem Kreis \(\langle 0,1,2,0\rangle\) indem man die Kante \(1-2\) entfernt und die Kanten \(1-3\) und \(3-2\) hinzufügt.
  
• \(\langle 0,3,1,2,0\rangle\) entsteht aus dem Kreis \(\langle 0,1,2,0\rangle\) indem man die Kante \(0-1\) entfernt und die Kanten \(0-3\) und \(3-1\) hinzufügt.

Für den \(K_5\) entstehen so aus \(\langle 0,1,2,3,0\rangle\) vier weitere Kreise, weil \(\langle 0,1,2,3,0\rangle\) vier Kanten hat. Ebenso entstehen aus \(\langle 0,1,3,2,0\rangle\) vier weitere Kreise und aus \(\langle 0,3,1,2,0\rangle\) vier weitere Kreise. Der \(K_5\) hat also \(3\cdot 4 = 12\) Hamiltonkreise.

komme auch bei diesen auf n-1 Zyklen

Das ist nicht richtig.

---

Ok vielen Dank für die ganzen hilfreichen Infos ich werde es mit im laufe des Tages genau anschauen diesen Begriff höre ich in der Tat zum ersten mal aber schon mal gut das es dafür eine Bezeichnung gibt.