Verwirrung um Hamilton: PO Bsp. 1b.)
Results 1 to 11 of 11
  1. #1
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts

    HILFE: 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 ) 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??
    Last edited by AntiBit; 25-09-2002 at 14:19.
    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.

  2. #2
    Jimmy's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    539
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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
    Last edited by Jimmy; 24-09-2002 at 22:54.
    Der beste Beweis, dass ausserirdische Intelligenz existiert, ist der dass bis jetzt noch keiner Kontakt zu uns aufgenommen hat

  3. #3
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    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.
    Last edited by AntiBit; 25-09-2002 at 00:13.
    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.

  4. #4
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    Weiß das denn keiner?? Oder machen nur so wenige die Prüfung am 4ten...
    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.

  5. #5

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    29
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Hinreichend != Notwendig

    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-forum...?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

  6. #6
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    Super, danke.
    Dachte die Bedingungen wären notwendig, aber wenn sie nur hinreichend sind, dann ist alles klar

    Ciao,
    AntiBit
    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.

  7. #7
    lj_scampo's Avatar
    Title
    Baccalaureus
    Join Date
    Mar 2002
    Posts
    582
    Thanks
    0
    Thanked 0 Times in 0 Posts
    "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

  8. #8
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    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
    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.

  9. #9

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    29
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Nicht vermischen

    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

  10. #10
    lj_scampo's Avatar
    Title
    Baccalaureus
    Join Date
    Mar 2002
    Posts
    582
    Thanks
    0
    Thanked 0 Times in 0 Posts
    genau das wollte ich ja eigentlich sagen.. Langsam glaube ich, jeder kapierts, nur erkl&auml;rts jeder ein bissl anders

  11. #11
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ich werd mir jetzt mal ein hinreichendes frühstück machen, das hab ich jetzt nämlich notwendig.

    sry

    MfG, -z0nk-
    zonked [zpnkt] - if someone is zonked or zonked out, they are not capable of doing anything because they are tired, drunk, or drugged; an informal word.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •