Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
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
ja.
nein.
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
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 [m][Ausgangsgrad] - [Eingangsgrad] = 1[/m] und für höchstens einen weiteren Knoten [m][Eingangsgrad] - [Ausgangsgrad] = 1[/m] gilt, wobei für die restlichen Knoten [m][Ausgangsgrad] = [Eingangsgrad][/m] gelten muss.
wurd eulerpfad dieses Semester gemacht?
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
Ahja, okay, dachte es müssen genau 0 sein, an die 2 hab ich garnichtmehr gedacht. Vielen Dank!
Hat kein Knoten einen ungeraden Grad spricht man von einem Eulerzyklus! Ist auch in einer Prüfungsaufgabe wie man die beiden unterscheidet!
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.
Ich dachte immer ein Eulerzyklus wäre ein Eulerpfad bei dem End und Anfangsknoten gleich sind xD
Hallo,
in welcher Reihenfolge werden denn die Städte hier abgearbeitet?
Stimmt denn meine nachfolgende Überlegung?
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.
Dürft stimmen. Zumindest würde ich es genauso machen.