Bezüglich offene bzw geschlossene Euler Linie

  • Hab folgende Frage im PO gefunden:


    Was versteht man unter einer offenen bzw geschlossenen Eulerschen Linie, was unter einer offenen bzw geschlossenen Hamiltonschen Linie? Sei G ein schwach zusammenhängender Graph. Wie kann man dann mit Hilfe der Knotengrade feststellen, ob G eine offene Eulersche Linie ist?


    Ich dachte eigentlich eine Eulersche Linie muss geschlossen sein!?
    Überhaupt die ganze Frage ist mir ein wenig suspekt!


    Wäre super wenn mir jemand das erklären könnte!


    mfg

  • könnte vielleicht eine Fangfrage sein, da die Definition eindeutig von einem geschlossenen Kantenzug spricht. Gäbe es einen offenen Kantenzug, gäbe es mindestens einen Knoten mit ungeradem Grad (nämlich 1), wodurch die Charakteristik der Eulerschen Graphen nicht mehr zutrifft.

  • IHMO ist es so, in einer offenen Eulerschen Linie gibt es 2 Knoten
    ungeraden Grads (nicht notwendigerweise 1), also den Anfang und das Ende.


    Code
    1. O-----O-----O hat eine "offene" eulersche Linie
    2. +-A-----B-+ hat auch eine "offene" eulersche Linie
    3. | | | | obowhl beide ungerade Grad haben
    4. | +-----+ | startet in A nach B, zurück nach A und
    5. +---------+ über die 3 Kante wieder nach B


    hth


    Hannes

  • Laut folgender Seite http://fachschaft.informatik.f…mathe/m1_kap5/m1_kap5.htm gilt:


    Zitat

    Definition:
    Durchläuft in einem Grapgen G ein offener oder geschlossener Kantenzug Z alle Kanten von G, so heißt z eine offene oder geschlossene Euler'sche Linie von G.


    Satz:
    Ein ungerichteter zusammenhängender Graph G besitzt dann und nur dann eine offene (geschlossene) Euler'sche Linie, wenn es in G zwei (keine) Knoten von ungeradem Grad gibt.


    Da bei der Definition eines Eulerschen Graphen im Skript nicht die Rede von einer offenen Linie ist und das auch sonst nirgends erwähnt, glaube ich nicht dass die PO Frage kommen kann.


    Außer er hat es halt extra in der Vorlesung einmal erwähnt - weiß das vielleicht jemand?


    mfg


    snigo

  • Wie auch immer, es ist ja nicht schwer zu merken:


    Wenn genau 2 Knoten ungeraden Grad haben, so gibt es eine offene eul. Linie. Bei nur geraden Graden ist es eine geschlossene.


    Offene Eulerlinie ist nichts anderes als eine geschlossene Eulerlinie, aber Startknoten != Zielknoten (deswegen ja offen, siehe offene Kantenfolge)


    Zusammenhängende Graphen die eine offene eulersche Linie besitzen sind NICHT Eulersch. Nur wenn sie eine geschlossene besitzen.

    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.

  • Die genauen Definitionen von "offenen Eulerlinien" etc. gibts übrigens (erstaunlicherweiße leicht verständlich) im grauen Mahte Büchlein vom Baron - Band 3.

  • Prüfung ist zwar vorbei, aber zum vorigen Post.


    Hab das Buch leider nicht zur Hand gehabt, und konnte so die genaue Seite nicht angeben.
    Ich wollts nur kurz erwähnen.


    Selbstverständlich werd ich das nächste Mal auch Seitenzahlen nennen. Hoff man hat es trotzdem gefunden.
    Sorry, falls es eventuelle Umstände bereiten haben sollte (wollt nur helfen).