Not logged in. · Lost password · Register

xlemmingx
Member since Jul 2011
35 posts
Subject: Graphen 05.08.2010
Hey,

habe eine Frage zu der Graphenaufgabe dieser alten Klausur. Die a) und b) sind ja Standard, allerdings steh ich bei der c) grade auf dem Schlauch.
Ein Eulerpfad ist doch ein Pfad in dem man alle Kanten einmal geht, ohne dabei eine doppelt zu laufen oder? Ist das nicht unmöglich wenn man nur eine Kante ziehen darf und die beiden Orte Würzburg und Passau jeweils nur eine Kante haben? Oder darf man beliebig viele ziehen?


Der Vollständigkeit halber noch meine Lösungen:
a)
Hof: 225
Würzburg: 205
Nürnberg: 90
Regensburg: 90
Deggendorf: 160
Holledau: 20
Passau: 210
München: 70

b)
(Falsch, zuerst mit Prim gemacht statt mit Kruskal)
Ingolstadt Holledau
Holledau München
Holledau Regensburg
Regensburg Deggendorf
Deggendorf Passau
Ingolstadt Nürnberg
Nürnberg Würzburg
Nürnberg Hof

(Richtige Lsg mit Kruskal)
Ingolstadt Holledau
Holledau München
Deggendorf Passau
Holledau Regensburg
Regensburg Deggendorf
Ingolstadt Nürnberg
Würzburg Nürnberg
Hof Nürnberg
This post was edited on 2012-02-08, 13:47 by xlemmingx.
dario
planlos wie immer
Member since May 2011
94 posts
Quote by xlemmingx:
Ein Eulerpfad ist doch ein Pfad in dem man alle Kanten einmal geht, ohne dabei eine doppelt zu laufen oder?
ja.
Quote by xlemmingx:
Ist das nicht unmöglich wenn man nur eine Kante ziehen darf und die beiden Orte Würzburg und Passau jeweils nur eine Kante haben?
nein.
Quote by xlemmingx:
Oder darf man beliebig viele ziehen?
auch nein.

die idee ist (war damals auch in der vorlesung), dass genau dann ein eulerpfad existiert, wenn höchstens zwei knoten ungeraden grad besitzen (grad = anzahl kanten zu diesem knoten). in der gegebenen konstellation sind es vier: passau, würzburg, AD holledau und ak deggendorf. wenn du zwei davon mit einer neuen kante (=autobahn) verbindest, haben sie einen um jeweils 1 höheren grad (also gerade), und die bedingung fuer eulerpfad ist erfüllt.
angeben müsst ihr ihn zwar nicht, aber es hilft zu wissen, dass die beiden verbleibenden ungeraden knoten anfang und ende sein müssen.


hth
mergesort list = foldl merge [] $ map mergesort $ split list     -- haskell <3
knix
Avatar
Member since Oct 2009
242 posts
Quote by dario:
genau dann ein eulerpfad existiert, wenn höchstens zwei knoten ungeraden grad besitzen (grad = anzahl kanten zu diesem knoten).

Das stimmt so nicht ganz.
Ein ungerichteter, zusammenhängender Graph besitzt genau dann einen Eulerpfad, wenn entweder kein Knoten oder genau zwei Knoten von ungeradem Grad sind.
Ein gerichteter, zusammenhängender Graph besitzt genau dann einen Eulerpfad, wenn für höchstens einen Knoten [Ausgangsgrad] - [Eingangsgrad] = 1 und für höchstens einen weiteren Knoten [Eingangsgrad] - [Ausgangsgrad] = 1 gilt, wobei für die restlichen Knoten [Ausgangsgrad] = [Eingangsgrad] gelten muss.
just the BEST theorem: ec(G) = tᵤ(G) ∏(deg(v) - 1)!
This post was edited 2 times, last on 2012-02-08, 16:29 by knix.
heftig
Member since Oct 2011
138 posts
wurd eulerpfad dieses Semester gemacht?
dario
planlos wie immer
Member since May 2011
94 posts
In reply to post #3
ok, du hast rechter als wie ich.

aber wo wir schon dabei sind: die aufgabe meint einen ungerichteten graphen, und für ungerichtete ist "<= 2 mit ungeradem grad" oder "0 oder 2 mit ungeradem grad" afaics gleichwertig
mergesort list = foldl merge [] $ map mergesort $ split list     -- haskell <3
xlemmingx
Member since Jul 2011
35 posts
Ahja, okay, dachte es müssen genau 0 sein, an die 2 hab ich garnichtmehr gedacht. Vielen Dank!
Blubbman
Member since Nov 2011
46 posts
Hat kein Knoten einen ungeraden Grad spricht man von einem Eulerzyklus! Ist auch in einer Prüfungsaufgabe wie man die beiden unterscheidet!
???
Member since Oct 2011
445 posts
In reply to post #4
Quote by heftig on 2012-02-08, 16:58:
wurd eulerpfad dieses Semester gemacht?

das Frag ich mich auch ich hab davon nix in den Vorlesungen gehört....
edisch
Member since Oct 2011
131 posts
Quote by ???:
Quote by heftig on 2012-02-08, 16:58:
wurd eulerpfad dieses Semester gemacht?

das Frag ich mich auch ich hab davon nix in den Vorlesungen gehört....


ich hab nochmal die Folien durchsucht und davon nix gefunden (und gehört hab ich davon auch noch nie was). Deswegen gehe ich davon aus, dass das nicht relevant ist.
Das F
Avatar
Member since Apr 2009
632 posts
In reply to post #7
Quote by Blubbman on 2012-02-10, 12:53:
Hat kein Knoten einen ungeraden Grad spricht man von einem Eulerzyklus! Ist auch in einer Prüfungsaufgabe wie man die beiden unterscheidet!

Ich dachte immer ein Eulerzyklus wäre ein Eulerpfad bei dem End und Anfangsknoten gleich sind xD
"Na całe szczęście wiem jak radę dać bez wiary" - Piotr Rogucki
mk444
Avatar
Member since Nov 2011
69 posts
Hallo,

in welcher Reihenfolge werden denn die Städte hier abgearbeitet?
Stimmt denn meine nachfolgende Überlegung?

1)
Von Ingolstadt kann ich nach Nürnberg(90) oder Holledau(20) -
Ich wähle Holledau weil es am kürzesten ist und packe Nürnberg in die Warteschlange.
2)
Von Holledau kann ich nach Regensburg(90) oder München(70)
Ich wähle München und packe Regensburg in die Schlange
3)
Von München kann ich nur nach Deggendorf (210)
-> Regensburg und Nürnberg sind aber nur 90km entfernt und deswegen Deggendorf vorzuziehen,
da Nürnberg schon länger in der Schlange ist als Regensburg, wähle ich als nächsten Knoten Nürnberg.
bewi1992
Member since Oct 2011
189 posts
Dürft stimmen. Zumindest würde ich es genauso machen.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen