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 21.02.2008
Es geht um aufgabe 2!
also bei a)
bei 1,2,3, hab ich keine ahnung
bei 4 und 5 sag ich nein.
kann mir das jemand erklären?
bei b) hab ich überall falsch. ist das richtig?
Bei der a) kann ich leider auch nichts sagen. Kann da jemand helfen?
bei der b) hab ich auch überall “nein” angekreuzt
Es ist kein DAG, da es Zyklen gibt.
Man kann auch nicht alle Wege ablaufen, ohne einen davon zweimal zu gehen, weil es mehr als einen Knoten gibt der nur an einem “Weg” angeschlossen ist.
Es ist kein Baum, da die “Richtung” nicht eindeutig ist und es Zyklen gibt.
stark zusammenhängend, nein
Euler-Zyklus, nein, da mehr als 2 Knoten einen ungeraden Grad haben.
zur b):
Kann kein DAG sein, weil der Graph ungerichtet ist.
Stark zusammenhängend müsste er aber doch sein, denn man kann jeden Knoten von jedem anderen Knoten aus erreichen.
a.1: Ja
a.2: Nein (zumindest nach der Definition die ich gefunden habe, die besagt, dass in einem Wurzelgraph die Kanten immer zum Vater zeigen)
a.3: Nein, es ist Tiefensuche
a.4: Nein
a.5: Nein (zumindest das müsste jeder von euch lösen können…)
b.1: Nein, der Graph ist weder gerichtet noch azyklisch
b.2: Nein (die Frage ist äquivalent zu „Gibt es einen Eulerpfad?”)
b.3: Ja (man kann von jedem Knoten aus jeden anderen erreichen)
b.4: Nein (es gibt ja schon keinen Eulerpfad)
bei a.5 hast du recht …
kannst du dir deine Antwort zur b) nochmal anschauen? Bei mir gibt es 5 Fragen…
Huch, da hab ich ne Frage übersprungen, hier die richtige Version:
nur um das klarzustellen, bei a) 5 war ich mir auch sicher!
Da hab ich ja, denn in der Vorlesung stand „Hat ein DAG nur eine Wurzel, so heisst er Wurzelgraph“. Und das muesste doch mit dem Code gehen.
Es ist aber doch garkein DAG :huh:
@knix: bei der 2a) ist nur der Code gegeben und kein Graph - du bist schon bei der 2b).
In den Vorlesungsfolien steht nur, dass ein Wurzelgraph ein DAG mit nur einer Wurzel ist. Über die richtung der kanten hab ich auch nichts gefunden.
Somit müsste der code auch wurzelgraphen durchsuchen können.
Aber eine Wurzel ist im Skript definiert, und zwar als Knoten, der einen Eingangsgrad von 0 hat.
Das wuerde dann doch passen, oder? Es gehen von der Wurzel nur Kanten “weg”, der Algorithmus koennte die dann alle traversieren.
Wisst ihr eigentlich, ob in der Vorlesung (indirekt) gesagt worden ist, in welchem Ausmaß das letzte Kapitel in der Klausur drankommen wird?
Also Graphen kommen auf jeden Fall dran, aber wohl vor allem dort Dijkstra/Prim/Kruskal. Genaueres hat er nicht gesagt.
Oh, sorry.
Ich meine, ein Wurzelgraph ist ein Graph, der es möglich macht, das man alle Knoten von der Wurzel aus erreichen kann. (also auch ein DAG mit nur einer Wurzel)
Dann sollte der Code es eigentlich schaffen, einen solchen Graphen zu durchsuchen.