Euler- und Hamiltonkreis
Wege, Pfade, Zyklen in Graphen, Euler- und Hamiltonkreis. Wer soll da denn den Durchblick behalten? Kein Problem wir erklären es dir kurz und verständlich!
Inhaltsübersicht
Wege, Pfade, Kreise und Zyklen in Graphen
Die Knoten und Kanten eines Graphen kann man oftmals als Weg oder Pfad durchlaufen. Manchmal bilden sie sogar einen Zyklus. Aber am besten schauen wir uns das jeweils einzeln, mithilfe von Beispielen, genauer an.
Wege oder Pfade in Graphen
Als Weg oder Pfad bezeichnet man eine Abfolge von Knoten und Kanten, um von einem Knoten zum anderen zu gelangen. Jeder Weg hat eine Länge. Bei ungewichteten Graphen entspricht diese Länge ganz einfach der Anzahl der genutzten Kanten. Unser Pfad von A nach E hat somit die Länge 4. Bei einem gewichteten Graph entspricht die Länge des Weges der Summe der Kantengewichte, sprich 17.
Zyklus
Sobald der Anfangsknoten und der Endknoten eines Pfades gleich sind spricht man von einem Zyklus. Fügst du also in unser Beispiel noch eine Kante von C nach E ein erhältst du einen Zyklus von C nach D, nach E und wieder zurück zu Knoten C.
Jede Kante darf dabei nur einmal genutzt werden. Enthält ein Graph keinen Zyklus spricht man von einem azyklischen Graph.
Königsberger Brückenproblem
Königsberg wird durch den Pregel in einzelne Stadtteile geteilt. Über den Fluss führten damals Sieben Brücken.
Euler fand heraus, dass in einem Graphen nur ein Eulerweg existiert, wenn maximal 2 Knoten einen ungeraden Grad haben. In Königsberg hatte jedoch jeder der Knoten einen ungeraden Grad. Somit bewies Euler, dass es keinen Weg und somit auch keinen Rundweg durch Königsberg gibt, bei dem man jede der Sieben Brücken genau einmal überquert.
Euler Weg: Haus des Nikolaus
Ein ganz bekanntes Beispiel für einen Euler Weg ist das Haus des Nikolaus. Im Unterschied zum Euler Kreis entspricht beim Euler Weg zwar der Anfangsknoten nicht dem Endknoten, doch alle Kanten werden ebenfalls genau einmal durchlaufen.
Hamiltonkreis
Beim sogenannten Hamiltonkreis dagegen spielen die Kanten keine so große Rolle. Hier muss jeder Knoten des Graphen durchlaufen werden. Ein Zyklus von A ausgehend nach A über B, C und D ist also ein Hamiltonscher Kreis. Der Zyklus von A nach A nur über B und C allerdings ist kein Hamiltonkreis da Knoten D nicht durchlaufen wird.
Hamiltonweg
Bei einem Hamiltonweg, auch Hamiltonscher Weg genannt, wird ebenfalls jeder Knoten des Graphen durchlaufen. Anfangsknoten und Endknoten müssen jedoch im Unterschied zum Hamitonkreis nicht identisch sein.
Ein Graph G der einen Hamiltonpfad, jedoch keinen Hamitonkreis enthält nennt man auch semihamiltonisch.
Sehr gut, jetzt weist du alles rund um Wege, Pfade, Zyklen und Kreise in Graphen! Das war doch eigentlich ganz easy, oder?