Eulerscher Graph!!!!!!!
Results 1 to 10 of 10
  1. #1

    Title
    Principal
    Join Date
    Mar 2002
    Posts
    74
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Eulerscher Graph!!!!!!!

    Hallo an Alle!
    Ich habe ein paar Fragen zum eulerschen Graph.Ich hoffe irgendjemand kann sie mir so schnell wie möglich beantworten.
    Also:

    Iste jeder Graph,den man in einem Zug zeichnen kann Eulersch?Man nenne eine notwendige Bedingung dafür,dass man einen Graphen in einem Zug zeichnen kann.Ist diese Bedingung hinreichend?Manm zeichne einen Graphen der eulersch ist,aber nicht Hamiltonisch & einen d. Hamiltonisch ist aber nicht eulersch!.

    Das wars auch schon

    Also es wäre wirklcih net wenn jemand die Fargen beantworten könnte.
    Danke,

    bye,dido

  2. #2
    patricasso's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    750
    Thanks
    1
    Thanked 2 Times in 2 Posts
    -Alle Antworten ohne Gewähr-

    Ist jeder Graph,den man in einem Zug zeichnen kann Eulersch?
    Ich denk mal nicht, da eine weitere notwendige Bedingung beim Eulerschen Graph ist, dass die Kanten höchstens einmal durchlaufen werden (= geschlossener Kantenzug). "...Mit einem Zug..." könnte aber was anderes gemeint sein (nehm ich so an), weil auch ein Hamiltonischer Graph so gezeichnet (!) werden könnte (also ohne Unterbrechung).

    Man nenne eine notwendige Bedingung dafür,dass man einen Graphen in einem Zug zeichnen kann?
    Also da könnte entweder die Definiton für eine Kantenfolge-Kantenzug auf S. 27 oder auch der Satz auf S. 33 im Skriptum hingehören. Vielleicht gehört aber auch der Algorithmus fürn Euler-Graph (S.34) beschrieben?
    Ist diese Bedingung hinreichend?
    Die obigen Definitonen sollten schon hinreichend sein (wenn das verlangt worden ist).

    Mann zeichne einen Graphen der eulersch ist,aber nicht Hamiltonisch & einen d. Hamiltonisch ist aber nicht eulersch!.
    Die hab ich schon (hoffentlich richtig) gezeichnet - muss sie aber erst einscannen! Werd sie dann hier posten.

    Wenn was falsch sein sollte, bitte ausbessern! Bin mir nämlich nicht ganz sicher, ob das alles stimmt.
    http://www.svkukmirn.com + http://www.swc-kukmirn.com

    Topfield TF 5000 PVR 80GB (incl. Alphacrypt) + TF 3000 CIpro (incl. Cryptoworks) + D-BoxII (Sagem - Neutrino :-) + SAB-Explorer CISC + Panasonic DMR-EH52EG-S (80 GB HD/DVD Recorder)... 19,2°E, 13° E
    -----------SUCHE MÜNZTAUSCHPARTNER/INNEN-----------

  3. #3
    patricasso's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    750
    Thanks
    1
    Thanked 2 Times in 2 Posts
    Keine Ahnung ob das jetzt stimmt aber ...

    ... Graph 1 ist ein EULERscher Graph, weil:
    1) Die Kanten nur 1x durchlaufen werden - der Kantenzug lautet:
    x1,e1,x2,e2,x3,e3,x4,e4,x5,e5,x3,e6,x6,e7,x1
    2) Alle Knoten geraden Grad haben

    ... Graph 2 ist ein HAMILTONscher Graph, weil:
    1) Die Knoten werden in den beiden Durchläufen nur einmal "benutzt".
    2) Wenn |V(X)| >= 3 dann gilt: d(x) >= 1/2 * |V(X)| - bei diesem Graphen ist die Halbe-Knotenmenge 3, und da jeder Knoten einen Grad >= 3 besitzt, sollte dass erfüllt sein.
    3) Wenn Knoten x1 = X und x6 = Y (zwei nicht adjazente Knoten), dann ist die Summe der kürzesten Abstände gleich 8 (bzw. 10 im 2. Durchlauf) und dass ist wiederrum >= der Anzahl der Knotenmenge (=7) - wenn ich dass richtig interpretiert haben sollte. -> siehe Folgerung auf Seite 36 im Skriptum.

    Ob jetzt der Eulersche Graph nicht hamiltonisch ist bzw. umgekehrt, weiß ich jetzt aber auch nicht so wirklich genau.
    Attached Files Attached Files
    http://www.svkukmirn.com + http://www.swc-kukmirn.com

    Topfield TF 5000 PVR 80GB (incl. Alphacrypt) + TF 3000 CIpro (incl. Cryptoworks) + D-BoxII (Sagem - Neutrino :-) + SAB-Explorer CISC + Panasonic DMR-EH52EG-S (80 GB HD/DVD Recorder)... 19,2°E, 13° E
    -----------SUCHE MÜNZTAUSCHPARTNER/INNEN-----------

  4. #4

    Title
    Principal
    Join Date
    Mar 2002
    Posts
    74
    Thanks
    0
    Thanked 0 Times in 0 Posts

    DANKEEEE!!!!!

    HEY,
    Danke echt nett von euch.

    Bye Dido

  5. #5
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Original geschrieben von Dido
    Iste jeder Graph,den man in einem Zug zeichnen kann Eulersch? Man nenne eine notwendige Bedingung dafür,dass man einen Graphen in einem Zug zeichnen kann.Ist diese Bedingung hinreichend? Man zeichne einen Graphen der eulersch ist,aber nicht Hamiltonisch & einen d. Hamiltonisch ist aber nicht eulersch!.
    Nicht jeder Graph, den man in einem Zug zeichen kann ist eulersch. beispiel wäre ein graph, der aus zwei adjazenten knoten besteht, die mit nur einer kante inzident sind. man kann ihn natürlich in einem zug zeichen, er ist aber trotzdem nicht eulersch, da man nie zum ausgangspunkt zurückkommt, ohne die kante zweimal zu verwenden.

    Bedingung: Vielleicht "Zusammenhang" ? Wäre natürlich nicht hinreichend.

    Original geschrieben von patricasso
    Ob jetzt der Eulersche Graph nicht hamiltonisch ist bzw. umgekehrt, weiß ich jetzt aber auch nicht so wirklich genau.
    Der 1. graph ist eulersch aber nicht hamiltonsch, der 2. graph ist hamiltonsch aber nicht eulersch, dh beide würden sich für dieses beispiel eignen.

    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.

  6. #6
    patricasso's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    750
    Thanks
    1
    Thanked 2 Times in 2 Posts
    Glaub die Frage mit der "notwendigen Bedingung" bezieht sich auf Eulersche Graphen und nicht auf allgemeine Graphen.

    Also ist die Bedingung, den Euler-Graphen in einem Zug zeichnen zu können zwar notwendig, aber nicht hinreichend, da weitere Bedingungen erfüllt sein müssen, wie z.B. dass der Kantenzug geschlossen sein muss!
    http://www.svkukmirn.com + http://www.swc-kukmirn.com

    Topfield TF 5000 PVR 80GB (incl. Alphacrypt) + TF 3000 CIpro (incl. Cryptoworks) + D-BoxII (Sagem - Neutrino :-) + SAB-Explorer CISC + Panasonic DMR-EH52EG-S (80 GB HD/DVD Recorder)... 19,2°E, 13° E
    -----------SUCHE MÜNZTAUSCHPARTNER/INNEN-----------

  7. #7
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    Genau.
    Und da steht ja GESCHLOSSENER Kantenzug --> heisst Anfangspunkt=Endpunkt.
    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.

  8. #8
    Jimmy's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    539
    Thanks
    0
    Thanked 0 Times in 0 Posts
    also wenn ichs verstanden hab... bei einem EULER'schen Graphen MUSS x0=xn sein , und beim Hamiltonschen KANN (aber nicht notwendig) x0 != xn sein oder?

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

  9. #9

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    aber es gibt ja eine pruefungsfrage die lautet:
    was versteht man unter einer offenen bzw geschlossenen eulerschen linie?

    also muss nicht immer x0=xn sein, oder?

    somit waere auch ein graph mit nur zwei knoten, der durch eine kante verbunden ist, eulersch?

    hass mathe, bin schon ganz verwirrt.
    also sorry, falls i nur bloedsinn red.

  10. #10
    patricasso's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    750
    Thanks
    1
    Thanked 2 Times in 2 Posts
    Original geschrieben von meriadoc

    somit waere auch ein graph mit nur zwei knoten, der durch eine kante verbunden ist, eulersch?
    Bei einem Eulerschen Graph müssen die Knoten aber alle eine gerade Gradzahl haben. Der Graph mit nur 2 Knoten und einer Kante hat aber die Gradzahl "1" = ungerade => kein EG.
    Zudem ist dieser Graph auch nicht geschlossen.
    http://www.svkukmirn.com + http://www.swc-kukmirn.com

    Topfield TF 5000 PVR 80GB (incl. Alphacrypt) + TF 3000 CIpro (incl. Cryptoworks) + D-BoxII (Sagem - Neutrino :-) + SAB-Explorer CISC + Panasonic DMR-EH52EG-S (80 GB HD/DVD Recorder)... 19,2°E, 13° E
    -----------SUCHE MÜNZTAUSCHPARTNER/INNEN-----------

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
  •