|
Member since Jul 2011
35 posts
|
2012-02-08, 13:42 #1
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 |
Member since May 2011
94 posts
|
2012-02-08, 16:09 #2
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 |
|
mergesort list = foldl merge [] $ map mergesort $ split list -- haskell <3
|
Member since Oct 2009
242 posts
|
2012-02-08, 16:17 #3
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)!
|
|
Member since Oct 2011
138 posts
|
2012-02-08, 16:58 #4
wurd eulerpfad dieses Semester gemacht?
|
|
Member since May 2011
94 posts
|
2012-02-08, 17:00 #5
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
|
|
Member since Jul 2011
35 posts
|
2012-02-09, 12:44 #6
Ahja, okay, dachte es müssen genau 0 sein, an die 2 hab ich garnichtmehr gedacht. Vielen Dank!
|
|
Member since Nov 2011
46 posts
|
2012-02-10, 12:53 #7
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
|
2012-02-12, 20:08 #8
In reply to post #4
das Frag ich mich auch ich hab davon nix in den Vorlesungen gehört.... |
|
Member since Oct 2011
131 posts
|
2012-02-13, 08:56 #9
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. |
Member since Apr 2009
632 posts
|
2012-02-13, 19:50 #10
In reply to post #7
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
|
Member since Nov 2011
69 posts
|
2012-02-17, 22:09 #11
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. |
|
Member since Oct 2011
189 posts
|
2012-02-18, 09:58 #12
Dürft stimmen. Zumindest würde ich es genauso machen.
|
Datenschutz |
Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev,
© 2003-2011 by Yves Goergen