Beispiel 459
Results 1 to 7 of 7

Thread: Beispiel 459

  1. #1
    dj_m.o.h.t.'s Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Posts
    428
    Thanks
    0
    Thanked 0 Times in 0 Posts

    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?

  2. #2
    lj_scampo's Avatar
    Title
    Baccalaureus
    Join Date
    Mar 2002
    Posts
    582
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Lightbulb

    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..
    Attached Images Attached Images  
    Last edited by lj_scampo; 25-04-2002 at 23:58.

  3. #3

    Title
    Veteran
    Join Date
    Apr 2002
    Posts
    18
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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...

  4. #4

    Title
    Principal
    Join Date
    Dec 2001
    Posts
    88
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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
    Last edited by qmp; 28-04-2002 at 14:12.

  5. #5
    lj_scampo's Avatar
    Title
    Baccalaureus
    Join Date
    Mar 2002
    Posts
    582
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Thumbs up

    stimmt!
    @ Joachim: ich hatte das "schlicht" doch glatt überlesen
    @ qmp: Diese beiden Möglichkeiten waren mir entwischt! Danke!
    Für (a,e) gilt allerdings (c,d,b,a,<b>e,f</b>,c)

  6. #6

    Title
    Master
    Join Date
    Mar 2002
    Posts
    158
    Thanks
    0
    Thanked 0 Times in 0 Posts

    kurze Frage noch

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

  7. #7

    Title
    Elite
    Join Date
    Feb 2002
    Posts
    482
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @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!"

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
  •