Graphen: eulersch und hamiltonsch |
14.09.2020, 00:20 | Julia 004 | Auf diesen Beitrag antworten » |
Graphen: eulersch und hamiltonsch 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? |
||
14.09.2020, 07:46 | IfindU | Auf diesen Beitrag antworten » |
RE: Graphen: eulersch und hamiltonsch Bis jetzt hast du alles richtig verstanden 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. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|