Beweis für Eulergraphen
Results 1 to 9 of 9
  1. #1
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Beweis für Eulergraphen

    Man zeichne einen schlichten, eulerschen graphen mit gerader knotenanzahl und ungerader kantenanzahl, oder man beweise, dass es einen solchen graphen nicht gibt (begründung).

    hm ... ich denk mal so einen graphen gibt´s nicht (allein weil die frage so blöd gestellt ist ) ... aber wie geht der beweis ?

    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.

  2. #2
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts
    hm ... bin jetzt nach ein bisschen herumzeichnen und tüfteln doch auf einen graphen gekommen, der diese bedingungen erfüllt.

    V(x) = {a, b, c, d, e, f}
    E(x) = {(a,b), (b,c), (c,d), (d,e), (b,e), (b,f), (f,a)}

    |V| = 6
    |E| = 7

    müsste doch stimmen, oder ?

    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.

  3. #3
    jeuneS2's Avatar
    Title
    Baccalaureus
    Join Date
    Jan 2002
    Posts
    547
    Thanks
    1
    Thanked 45 Times in 29 Posts
    jepp, stimmt, einen Kreis mit ungerader Knoten- bzw. Kanten-Anzahl und einen Kreis gerader Knoten- bzw. Kanten-Anzahl zusammenschmeißen, die einen Knoten gemeinsam haben (und keine Kante)
    ->(2i+1)+(2k) - 1 = 2m Knoten (Inklusion, Exklusion )
    ->(2i+1)+(2k) = 2m +1 Kanten
    Why bother spending time reading up on things? Everybody's an authority, in a free land.

  4. #4
    Jimmy's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    539
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @Zonk: Hab da ne Frage: also laut Angabe muss der Graph ja sooo auschauen (-> s.Anhang)
    heissts, aber nicht, dass man jeden Eulerschern Graphen so zeichnen kann, dass ich jede Kante 1x und jeden Knoten "ohne die Bleistiftspitze zu heben" berueheren muss? wie kommst du dann auf (b,e) und nicht auf (e,b) oder ist das egal? (naja glaub ich nicht, ist ja ein geordnetes Tupel)
    Last edited by Jimmy; 24-09-2002 at 10:12.

  5. #5

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Original geschrieben von Jimmy
    wie kommst du dann auf (b,e) und nicht auf (e,b) oder ist das egal? (naja glaub ich nicht, ist ja ein geordnetes Tupel)
    in der Angabe nichts davon, dass der Graph gerichtet sein muss. Und bei einem ungerichteten Graphen sinds eben ungeordnete Paare, also ists egal würd  ich sagen

    mfg, Chris
    hi, i'm a signature virus. copy me into your signature to help me spread.

  6. #6
    Jimmy's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    539
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ich dachte, beim ungerichteten Graphen schreibt man die Kantenendknoten in [] Klammern und bei gerichteten in ()
    und der Zonk verwendet halt runde (),
    klar beim ungerichteten Gr. waer das Bsp. schon logisch und korrekt.
    nur darf man einen Knoten auch 2x benuetzen?
    Der beste Beweis, dass ausserirdische Intelligenz existiert, ist der dass bis jetzt noch keiner Kontakt zu uns aufgenommen hat

  7. #7

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ja, glaube schon, dass du einen Knoten öfter benutzen darfst (aber jede Kante nur einmal..)

    mfg, Chris
    hi, i'm a signature virus. copy me into your signature to help me spread.

  8. #8
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts
    sorry für das missverständnis, ich hab natürlich einen ungerichteten graphen gemeint !

    für einen gerichteten graphen müsste man die kanten eines kreises halt immer in eine richtung machen.

    ... und ich bin mir auch ziemlich sicher, dass man einen knoten mehrmals verwenden darf.

    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.

  9. #9

    Title
    Principal
    Join Date
    Feb 2002
    Location
    wien
    Posts
    59
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: [ FRAGE ] Beweis für Eulergraphen

    schaut von euch auch einer ins skriptum ?
    da steht, "euler graph ist (iii) kantendisjunkte vereinigung endlich vieler
    kreise" (seite 33)
    wie bitte soll man kreise kantendisjunkt vereinigen, wenn nicht ueber
    gemeinsame knoten?
    ich denke mal, mit aussagen wie "ich glaube" ist hier niemandem wirklich
    geholfen,
    da waer es gescheiter man schreibt nix, weil unsicher ist sich der fragende
    denk ich selber.
    lg
    peter

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
  •