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.
Studyflix vernetzt: Hier ein Video aus einem anderen Bereich
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?
Euler- und Hamiltonkreis — häufigste Fragen
(ausklappen)
Euler- und Hamiltonkreis — häufigste Fragen
(ausklappen)-
Was ist ein Eulerpfad?Ein Eulerpfad ist ein Weg in einem Graphen, bei dem man jede Kante genau einmal entlanggeht. Anfangsknoten und Endknoten müssen dabei nicht derselbe Knoten sein. Ein Eulerkreis ist die Spezialform davon, bei der man am Ende wieder am Startknoten ankommt.
-
Ist ein Eulerkreis automatisch auch ein Eulerweg?Ein Eulerkreis ist automatisch auch ein Eulerweg, weil man dabei ebenfalls jede Kante genau einmal benutzt. Der Unterschied ist nur, dass beim Eulerkreis Start- und Endknoten gleich sind, beim Eulerweg nicht unbedingt.
-
Ist das Haus vom Nikolaus ein Eulerkreis?Das Haus des Nikolaus ist kein Eulerkreis, weil man beim Zeichnen als zusammenhängender Zug zwar jede Kante genau einmal nachfährt, aber nicht am gleichen Punkt endet, an dem man gestartet ist. Es ist damit ein Eulerweg und kein Eulerkreis.
-
Was ist ein Beispiel für einen Eulerkreis?Ein Beispiel für einen Eulerkreis ist ein Dreieck aus drei Knoten A, B und C mit den Kanten AB, BC und CA. Der Rundweg
nutzt jede Kante genau einmal und endet wieder bei A.
Graphentheorie verstehen
Euler- und Hamiltonkreise gehören zur Graphentheorie und sind wichtige Begriffe für Wege und Kreise in Graphen. Wer sich mit Graphentheorie beschäftigt, schaut auf Knoten, Kanten und ihre Verbindungen in einem Graphen. Dabei wird klar, worauf es bei einem Weg, einem Kreis oder einem Grad im Graphen ankommt. Im Informatikbereich findest du passende Videos zu diesem und verwandten Themen.
