Verwirrung um Hamilton: PO Bsp. 1b.)

  • Eine Frage zu Hamilton, da ist irgendwo ein Hunz-Denkfehler versteckt:


    Geg. Kantenmenge E eines Graphen.
    E(X)={(a,b),(a,c),(b,c),(b,d),(c,d),(c,e),(c,f),(e,f)}


    Zu untersuchen ist, ob der Graph einen eulerschen, bzw. hamiltonschen Kreis enthält, wenn nein, dann soll man durch hinzufügen oder entfernen einer Kante einen erzeugen.


    So weit so gut, also Euler hat er nicht --> (b,c) streichen --> eulersch.


    Aber bei Hamilton ist das unklar. Zunächst ist der Graph doch nicht hamiltonsch.
    Durch hinzufügen der Kante (a,e) kann man dann aber eindeutig einen Kreis fahren, der jeden Knoten genau einmal trifft.
    ABER:
    Laut den Eigenschaften im Skriptum dürfte der Graph dann trotzdem KEINE Hamilton-Linie besitzen, weil:


    Regel 1: Sei X zusammenhängend und |V(X)>=3| (V(X) ist im Bsp. also 6). Ist für je 2 nicht adjazente Knoten x,y aus V(X) stets d(x)+d(y)>=|V(X)|, so ist X hamiltonscher Graph.


    Trifft nicht zu, da Knoten a und f nicht adjazent sind, und d(a)=3,d(f)=2 --> 2+3=5 --> 5 ist nicht >= 6 !


    Regel 2: Sei X zus.hängend und |V(X)>=3|. Ist für alle x € V(X) (Anmerkung: also ist der €uro doch zu was gut :D ) stets d(x) >= 1/2 * |V(X)|, so ist X ein Ham. Graph.


    Trifft auch nicht zu, da:
    d(d)=2 --> 2 ist nicht >= 1/2 * 6 !!


    Beide Bedingungen, und auch der Satz von Ore treffen nicht zu. Warum kann man dann trotzdem eine hamiltonsche Linie finden??
    Oder kann man gar keine finden, krieg die nur ich zam?


    Die ham.Linie die ich meine zu wissen ist: a-->b-->d-->c-->f-->e-->a


    Wo liegt der Fehler??

    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  • 1) ist das ein ungerichteter Graph? ich hoffe schon ;)


    2) bist dir sicher, dass man nur eine einzige Kante dazumalen darf? Weil logisch gesehen, hast du ja am Anfang (Angabe) einen Graphen mit 4 Knoten, die genau den Grad 2 haben. wenn du genau EINE Kante zeichnest, dann legalisierst ja sozusagen nur 2 Knoten und 2 weitere bleiben uebrig. ist irgendwie unmoeglich mit nur E I N E R Kante.


    [edit] von wo hast du das Bsp. - ist ziemlich kniffelig :confused:

    Der beste Beweis, dass ausserirdische Intelligenz existiert, ist der dass bis jetzt noch keiner Kontakt zu uns aufgenommen hat

  • Hoi Jimmy,
    ich versteh nicht ganz was du meinst.
    [edit] Nämlich diese Aussage: "dann legalisierst ja sozusagen nur 2 Knoten und 2 weitere bleiben uebrig. ist irgendwie unmoeglich mit nur E I N E R Kante"
    [/edit]
    Am Anfang hat man 4 Knoten mit dem Grad 2, durch hinzufügen einer Kante sind es dann 2 Knoten mit dem Grad 2.


    Ich poste mal die genaue Angabe, ist vom PO, Prüfung vom 19.11.99:


    E(X)={(a,b),(a,c),(b,c),(b,d),(c,d),(c,e),(c,f),(e,f)}
    Gesucht ist ein Eulerscher Kreis. Wenn keiner gefunden wird, soll man durch hinzufügen oder wegnehmen von GENAU EINER Kante einen Graphen erzeugen, der einen Eulerschen Kreis enthält. Das gleiche auch für Hamiltonscher Kreis.

    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  • Der Satz von Ore, sowie Folgerung 1 und 2 sind hinreichende, aber nicht notwendige Bedingungen für die Existenz einer Hamiltonschen Linie. Das heisst ein Graph der eine der Bedingungen erfüllt ist sicher Hamiltonisch, aber das heisst doch nicht dass jeder Hamiltonsche Graph diese Bedingungen erfüllen muss.


    siehe Unterschied zw. hinreichend und notwendig: http://rs6k.feig.at/informatik…wthread.php?threadid=2339


    Der 1.Graph auf S.35 ist ja laut Skript auch ein Hamiltonscher Graph, erfüllt aber weder Folgerung 1 noch 2, da d(2)+d(5) = 6 und das ja nicht grösser oder gleich |V(X)|= 7 ist und d(2) =3 ist ja auch nicht grösser oder gleich 1/2*|V(X)| = 3.5.


    Meiner Meinung nach liegt da der Fehler von dem Ganzen.


    mfg


    snigo

  • "nur" hinreichend ist gut.. hinreichend ist ja stärker als notwendig..
    Beispiel:
    es ist notwendig, dass jemand >1,70m sein muss, wenn man eine Person sucht, welche >1,80m ist.
    und es ist hinreichend, wenn diese Person >1,90m ist, weil sie dann auf alle Fälle auch >1,80m ist..


    Ich hoffe, das hat das Ganze jetzt nicht noch mehr verkompliziert ;)

  • Uh...


    Also... notwendig hin, hinreichend her... blubb


    Wichtig ist eines:
    Ein Graph KANN SEHR WOHL hamiltonsch sein, auch wenn der Satz von Ore und beide Folgerungen nicht zutreffen.


    Ein Graph IST SICHER hamiltonsch wenn der Satz von Ore, bzw eine der beiden Folgerungen zutrifft.


    Solange das stimmt bin ich zufrieden :D

    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  • Zitat

    Original geschrieben von lj_scampo
    "nur" hinreichend ist gut.. hinreichend ist ja stärker als notwendig..


    Hinreichend und notwendig sind halt zwei verschiedene Sachen, die kann man nicht so einfach vermischen.


    Sicher ist es hinreichend wenn jemand >1,90 ist und alle Leute gesucht sind sie die >1,80 sind aber das heisst ja noch lange nicht dass das eine notwendige Bedingung ist um grösser als 1,80 zu sein. Es gibt ja schliesslich auch Leute die >1,80 aber <1,90 sind.
    Daher: hinreichend ist eben ungleich notwendig


    mfg


    snigo