Not logged in. · Lost password · Register

peck
Member since Jul 2010
16 posts
Subject: 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?
educs
Member since Jul 2010
64 posts
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.
tsch.aei
Member since Jul 2010
57 posts
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.
neverpanic
Member since Sep 2008
1458 posts
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)
educs
Member since Jul 2010
64 posts
bei a.5 hast du recht .....

kannst du dir deine Antwort zur b) nochmal anschauen? Bei mir gibt es 5 Fragen....
neverpanic
Member since Sep 2008
1458 posts
In reply to post #4
Huch, da hab ich ne Frage übersprungen, hier die richtige Version:
Quote by neverpanic:
b.1: Nein, der Graph ist weder gerichtet noch azyklisch
b.2: Nein (die Frage ist äquivalent zu „Gibt es einen Eulerpfad?”)
b.3: Offensichtlich nicht, der Graph strotzt ja geradezu vor Zyklen
b.4: Ja (man kann von jedem Knoten aus jeden anderen erreichen)
b.5: Nein (es gibt ja schon keinen Eulerpfad)
peck
Member since Jul 2010
16 posts
nur um das klarzustellen, bei a) 5 war ich mir auch sicher!
rudis
SPler
(Administrator)
Member since Apr 2010
649 posts
In reply to post #4
Quote by neverpanic on 2010-07-30, 18:35:
a.2: Nein (zumindest nach der Definition die ich gefunden habe, die besagt, dass in einem Wurzelgraph die Kanten immer zum Vater zeigen)
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.
knix
Avatar
Member since Oct 2009
242 posts
Quote by rudis:
Quote by neverpanic on 2010-07-30, 18:35:
a.2: Nein (zumindest nach der Definition die ich gefunden habe, die besagt, dass in einem Wurzelgraph die Kanten immer zum Vater zeigen)
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:
just the BEST theorem: ec(G) = tᵤ(G) ∏(deg(v) - 1)!
Sleepy10
Member since Jul 2010
21 posts
Quote by knix:
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.
tsch.aei
Member since Jul 2010
57 posts
Aber eine Wurzel ist im Skript definiert, und zwar als Knoten, der einen Eingangsgrad von 0 hat.
rudis
SPler
(Administrator)
Member since Apr 2010
649 posts
Das wuerde dann doch passen, oder? Es gehen von der Wurzel nur Kanten "weg", der Algorithmus koennte die dann alle traversieren.
joe
Member since Jul 2010
14 posts
Wisst ihr eigentlich, ob in der Vorlesung (indirekt) gesagt worden ist, in welchem Ausmaß das letzte Kapitel in der Klausur drankommen wird?
rudis
SPler
(Administrator)
Member since Apr 2010
649 posts
Also Graphen kommen auf jeden Fall dran, aber wohl vor allem dort Dijkstra/Prim/Kruskal. Genaueres hat er nicht gesagt.
knix
Avatar
Member since Oct 2009
242 posts
In reply to post #10
Quote by Sleepy10:
Quote by knix:
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.

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.
just the BEST theorem: ec(G) = tᵤ(G) ∏(deg(v) - 1)!
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