Beispiel 459

  • Angabe: Gegeben sei der Graph mit der Kantenmenge E(X)={(a,b), (a,c), (b,c), (b,d), (c,d), (c,e), (c,f), (e,f)}. Existiert in diesem Graphen ein Euler'scher Kreis? Wenn ja, welcher? Wenn nein, ist genau eine Kante hinzuzufügen oder zu entfernen, sodass ein Euler'scher Kreis existiert und der Graph schlicht bleibt. Welche Möglichkeiten gibt es dafür? Man behandle dieselbe Fragenstellung auch für Hamilton'sche Kreise.


    Lösung: I have no idea! Was ist ein Euler'scher und Hamilton'scher Kreis?

  • Mein Lösungsversuch:


    Eulerscher Kreis = geschlossener Kantenzug, der jede Kante genau einmal enthält. (d.h. ich starte vom Knoten x0, durchlaufe alle Kanten genau einmal und komme wieder bei x0 an; dabei ist es egal, wie oft die einzelnen Knoten getroffen werden)
    Lösungsvorschlag in beiliegender Grafik:
    1) Graph laut Angabe
    2) Eulerscher Kreis mittels Streichen einer Kante
    3) E.K. mittels Hinzufügen einer Kante


    Hamiltonsche Linie = ein Kreis, der jeden Knoten genau einmal trifft.
    Lösungsvorschlag in beiliegender Grafik:
    4) und 5) H.L. mittels Hinzufügen einer Kante
    6) ACHTUNG: In der Angabe war nur die Rede von Kanten; die Knoten wurden nicht angegeben. D.h. falls es isolierte Knoten gibt (z.B. den Knoten g), kann logischerweise keine H.L. exisitieren, da ja keine Kante dorthin führen würde!


    Ich hoffe, dass alles stimmt..

  • also mit 3 stimme ich nicht überein. der graph soll ja schlicht bleiben und das ist mit dieser mehrfachkante (b,c) nicht mehr gegeben!
    wenn ich mich nicht täuschen gibt es für die eulersche linie nur eine möglichkeit. (nämlich die zwei knoten mit ungeraden knotengrad zu elminieren, was ja nur durch das wegnehmen funktioniert)
    für hamilton die 2 genannten möglichkeiten...

  • es gibt noch 2 andere Möglichkeiten Hamiltonsche Kreise zu erzeugen:


    (a,e) -> (c,d,b,a,e,f,c)
    (d,f) -> (c,a,b,d,f,e,c)


    edit: Verdreher ausgebessert

  • Die Lösungen sind so weit klar. Nur versteh i des Math-Skript net ganz. "Sei X zusammenhängend und |V(X)|>=3. Ist für alle x element V(x) stets d(x)>=1/2|V(X), so ist X ein Hamiltonscher Graph (S. 36). Das ist doch nicht erfüllt!
    Thx für eine Klarstellung...

  • skytale : im Skriptum steht aber, glaub ich, nicht drin, dass der Graph "dann und nur dann" einen Hamilton'schen Kreis hat, sondern nur, dass wenn der Satz erfüllt ist, er bestimmt einen hat.
    Wenn der Satz nicht gilt, dann *könnte* es trotzdem einen H. Kreis geben, wenn der Satz schon erfüllt ist, gibt es aber auf jeden Fall einen!


    ich hoff, du verstehst, was ich mein!


    PS: Weiter oben auf derselben Seite steht sogar "es gibt keinen allgemeinen Alg. für Hamiltonkreise!"