Theoretische Informatik

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.

Wege in gewichteten und ungewichteten Graphen
direkt ins Video springen
Wege und Pfade in Graphen

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.

Eulerkreis

Eine besondere Form eines Zyklus ist der Eulerkreis, der manchmal auch Eulerscher Kreis genannt wird. Das ist ein Zyklus, bei dem jede Kante des Graphen genau einmal genutzt wird.

Der Name Euler Kreis kommt von Leonhard Euler, der 1736 das Königsberger Brückenproblem löste.

Königsberger Brückenproblem

Königsberg wird durch den Pregel in einzelne Stadtteile geteilt. Über den Fluss führten damals Sieben Brücken.

Eulerweg und Königsberger Brückenproblem
direkt ins Video springen
Königsberger Brückenproblem

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.

Eulerscher Weg
direkt ins Video springen
Eulerweg: Alle Kanten werden 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.

Hamilonscher Kreis
direkt ins Video springen
Hamitonkreis: Jeder Knoten wird durchlaufen

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?

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.