Graphen: eulersch und hamiltonsch

Neue Frage »

Julia 004 Auf diesen Beitrag antworten »
Graphen: eulersch und hamiltonsch
Meine Frage:
Ich verstehe zwar den Unterschied in der Definition von eulerschen und hamiltonschen Graphen, allerdings bin ich irgendwie nicht in der Lage ein Beispiel für einen Graphen anzugeben der eulersch ist, aber nicht hamiltonsch und umgekehrt.

Meine Ideen:
Wikipedia: Ein Hamiltonkreis ist ein geschlossener Pfad in einem Graphen, der jeden Knoten genau einmal enthält. Im Gegensatz zum leicht lösbaren Eulerkreisproblem, bei dem ein Kreis gesucht wird, der alle Kanten genau einmal durchläuft, ist das Hamiltonkreisproblem NP-vollständig. Was bedeutet NP-vollständig?

Also der Unterschied besteht darin, dass eulersche Graphen über Kanten und hamiltonsche Graphen über Knoten definiert sind.
Ein geschlossener Kantenzug heißt Euler-Zug, wenn jede Kante des Graphen genau einmal durchlaufen wird. G ist eulersch, wenn G einen Euler-Zug enthält.
Ein Pfad auf dem alle Knoten von G besucht werden, heißt Hamilton-Weg. Ein geschlossener Weg auf dem alle Knoten von G besucht werden, heißt Hamilton-Kreis und jeder Graph, der einen Hamilton-Kreis enthält heißt hamiltonsch.

ist z.B. hamiltonsch und eulersch
ist ebenfalls hamiltonsch, aber wenn ich mich nicht täusche dürft dieser nicht eulersch sein, oder? Es können nicht alle Kanten genau einmal durchlaufen werden, sondern es muss mindestens eine geben, die doppelt durchlaufen wird. Stimmt das?
Kennt ihr ein Beispiel für einen Graphen der eulersch, aber nicht hamiltonsch ist?
IfindU Auf diesen Beitrag antworten »
RE: Graphen: eulersch und hamiltonsch
Bis jetzt hast du alles richtig verstanden smile

Ein triviales (degeneriertes?) Beispiel wäre ein Graph bestehend aus isolierten Punkten. Ein etwas interessanteres Beispiel wäre ein Plus-Graph. Damit meine ich einen Graphen mit 5 Punkten auf einer Uhr: Einer bei 12 Uhr, 3 Uhr, 6 Uhr, 9 Uhr und in der Mitte. Verbunden sind alle Knoten erst einmal nur mit der Mitte. (Es sollte wie ein Plus aussehen).

Der Graph ist weder eulersch noch hamilitonsch. Das Hinzufügen einer Kante macht zwischen "benachbarten Uhrzeiten" macht diesen eulersch, nicht aber hamiltonsch.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »