Hallo, kann mir jemand bei folgende Aufgabe helfen (Danke jetzt schon):
Man soll zeigen, wenn der Graph eulersch ist, dann ist der dazugehörige Kantengraph L(G) Hamiltonsch. Gilt die Umkehrung auch?
Hallo.
Lt. dem Buch Graphentheorie von Peter Tittmann ist ein eulerscher Graph eine geschlossene Kantenfolge in einem Graphen G, die jede Kante von G genau einmal durchläuft + wenn der Grad jedes Knotens von G eine gerade Zahl ist(=Haus vom Nikolaus). Ein Hamiltonkreis G=(V,E) ist ein Kreis von G, der alle Knoten aus V enthält (=Rundreiseproblem).
Beim eulerschen Kreis muss man nicht alle Knoten verbunden haben, von daher gilt Hamilton’sch --> Euler’sch nicht in jedem Fall.
HTH
mfg M.L.
Danke für deine Antwort, aber das wusste ich auch vorher.
Damtit ist aber meine Frage nicht beantwortet, denn man soll beide Richtungen zeigen.
–> Euler’sch nicht in
jedem Fall.
Das weiß ich auch, aber schon gesagt: man muss das zeigen.
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]