Übung 2 - Aufgabe 1

Moderator: Effiziente Graphenalgorithmen

marluwie
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 18. Okt 2005 22:33

Übung 2 - Aufgabe 1

Beitrag von marluwie »

Hallo!

Meiner Meinung nach ist der Hinweis (b) in der ersten Aufgabe falsch. Betrachtet man den Graph D = ({r, v1, v2}, {r -> v1}), so gilt für alle echten Teilmengen von V, die r enthalten, dass die Menge der ausgehenden Kanten nicht leer ist. Einfach, weil r eine ausgehende Kante besitzt.

\($\delta(\lbrace r \rbrace) = \lbrace r \rightarrow v1 \rbrace$\)
\($\delta(\lbrace r, v1 \rbrace) = \lbrace r \rightarrow v1 \rbrace$\)
\($\delta(\lbrace r, v2 \rbrace) = \lbrace r \rightarrow v1 \rbrace$\)

Es existiert jedoch kein Pfad von r nach v2, was das Lemma (b) aber verlangt.
Viele Grüße, Marian!
"You can't change anything by fighting or resisting it. You change something by making it obsolete through superior methods." (Buckminster Fuller)

Benutzeravatar
NedFlanders84
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 3. Nov 2004 10:30
Kontaktdaten:

Re: Übung 2 - Aufgabe 1

Beitrag von NedFlanders84 »

Guten Morgen,

ich denke, dass in dem Graphen {r, v2} die Kante {r -> v1} nicht als ausgehende Kante für den Teilgraphen gilt.

Daraus folgt, dass es in diesem Teilgraphen die Anzahl ausgehender Kanten = 0 ist und damit gibt es keinen r-v-Pfad.

Das ist meinem Verständnis nach die Ausage des Lemmas.

Viele Grüße,

Alex

PS: Ich glaube die Fomulierung der Aufgabe ist schwammig, weil ich jetzt annehmen würde, dass solch ein Graph nicht für diese Aufgabe gültig ist, da man sonst alles widerlegen kann...

EDIT: Noch mal über alles nachgedacht und angepasst...
.
Eisbären sind Linkshänder!!!

marluwie
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 18. Okt 2005 22:33

Re: Übung 2 - Aufgabe 1

Beitrag von marluwie »

Hallo!

Ich denke es gibt einige Inkonsistenzen im Skript. Wahrscheinlich wissen wir alle, was gemeint ist. Aber wenn man etwas beweisen und aufschreiben soll, frage ich mich an welchen Stellen man die Definitionen dann geschickt verbiegen darf.

Beispiel:
Es geht diesmal um die Äquivalenz (b) und (c). In einem Branching mit n-1 Kanten, dessen Wurzel(n) r keine eingehende Kanten hat/haben (was in diesem Zusammenhang r ist, soll sich wahrscheinlich aus (a) ergeben. Ist aber nicht so eindeutig) soll es einen eindeutigen Pfad zwischen Wurzel und einem beliebigen anderen Knoten geben.

ABER: Wenn folgender Graph (nach dem Skript) ein Branching ist, ist die Äquivalenz nicht wahr:
Sei D = ({r, v1, v2}, {v1 -> v2, v2 -> v1}).
Behauptung: D ist ein Branching.
"Beweis":
Das jeder Knoten höchstens eine eingehende Kanten hat, ist klar. Ist der zugrundeliegende Graph ein Wald? - Ja!
Der zugrunde liegende Graph erhält alle Nachbarschaften des Digraphs.
In particular, G [, the underlying graph, ] is simple.
Dadurch entstehen keine parallelen Kanten und somit auch keine Zyklen. Wenn doch parallele Kanten entstehen können, bilden diese aber keinen Zyklus. Ein Zyklus ist ein geschlossener Walk. Ein Walk enthält keine gleichen Kanten. Man kann jetzt nur noch mit antiparallel argumentieren. Aber das ist im ungerichteten Sinne nicht definiert (glaube ich).

EDIT: MEINE ARGUMENTATION IST FLASCH, WENN EIN ZUGRUNDE LIEGENDER GRAPH PARALLELE KANTEN ENTHALTEN DARF. SONST GIBT ES DOCH ZYKLEN, WEIL DIE KANTEN NICHT GLEICH SIND. NUR DIE ENDPUNKTE SIND GLEICH.

EDIT2: VIELLEICHT IST MEINE ARGUMENTATION DOCH RICHTIG, DA MAN FÜR \($e_i \neq e_j$\) DIE TUPEL EINSETZT. ICH ERINNERE MICH, DASS UNGERICHTETE KANTEN ALS MENGEN DEFINIERT WURDEN. DIESE WÄREN GLEICH, WENN IHRE ELEMENTE GLEICH SIND.

Viele Grüße, Marian!
"You can't change anything by fighting or resisting it. You change something by making it obsolete through superior methods." (Buckminster Fuller)

Mspringer
Nerd
Nerd
Beiträge: 555
Registriert: 19. Okt 2006 14:41
Wohnort: Darmstadt / Alzenau
Kontaktdaten:

Re: Übung 2 - Aufgabe 1

Beitrag von Mspringer »

Hat jemand ne Ahnung, was bei Aussage 1 (e) der Begriff Inklusionsminimal bedeutet? Bisher habe ich noch nichts hilfreiches dazu gefunden, oder hab ich was im Skript übersehen?

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Übung 2 - Aufgabe 1

Beitrag von Stille »

marluwie hat geschrieben:Hallo!
\($\delta(\lbrace r \rbrace) = \lbrace r \rightarrow v1 \rbrace$\)
\($\delta(\lbrace r, v1 \rbrace) = \lbrace r \rightarrow v1 \rbrace$\)
\($\delta(\lbrace r, v2 \rbrace) = \lbrace r \rightarrow v1 \rbrace$\)
Falsch. In obigem Beispiel führt keine Kante aus dem durch r und v_1 induzierten Subgraphen heraus. Es gilt folglich
\($\delta^{+}(\lbrace r, v_1 \rbrace) = \emptyset$\).
Daher ist v_2 auch nicht erreichbar.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Übung 2 - Aufgabe 1

Beitrag von Stille »

marluwie hat geschrieben: Ich denke es gibt einige Inkonsistenzen im Skript. Wahrscheinlich wissen wir alle, was gemeint ist. Aber wenn man etwas beweisen und aufschreiben soll, frage ich mich an welchen Stellen man die Definitionen dann geschickt verbiegen darf.
Sie haben recht, die Definition ist an dieser Stelle etwas unpräzise. Natürlich ist die Zyklenfreiheit essentieller Bestandteil der Definitionen von Baum oder Wald bzw. Arboreszenz oder Branching. Generell sollten Definitionen aber nicht verbogen werden. Weil Sie gerade sagen "einige Inkonsistenzen": Für Hinweise auf Inkonsistenzen und Fehler im Skript bin ich jederzeit dankbar. Nobody's perfect.
marluwie hat geschrieben: Dadurch entstehen keine parallelen Kanten und somit auch keine Zyklen. Wenn doch parallele Kanten entstehen können, bilden diese aber keinen Zyklus. Ein Zyklus ist ein geschlossener Walk. Ein Walk enthält keine gleichen Kanten. Man kann jetzt nur noch mit antiparallel argumentieren. Aber das ist im ungerichteten Sinne nicht definiert (glaube ich).


EDIT: MEINE ARGUMENTATION IST FLASCH, WENN EIN ZUGRUNDE LIEGENDER GRAPH PARALLELE KANTEN ENTHALTEN DARF. SONST GIBT ES DOCH ZYKLEN, WEIL DIE KANTEN NICHT GLEICH SIND. NUR DIE ENDPUNKTE SIND GLEICH.
Genau. Betrachten Sie den Graphen G=({v_1, v_2}, {e_1:=(v_1,v_2), e_2:={v_2,v_1}). G enthält den Zyklus v_1 -> e_1 -> v_2 -> e_2 -> v_1, welcher natürlich ein geschlossener Weg ist.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Übung 2 - Aufgabe 1

Beitrag von Stille »

Mspringer hat geschrieben:Hat jemand ne Ahnung, was bei Aussage 1 (e) der Begriff Inklusionsminimal bedeutet? Bisher habe ich noch nichts hilfreiches dazu gefunden, oder hab ich was im Skript übersehen?
Man könnte auch sagen: D ist ein minimaler Graph für den gilt: \(\delta^{+}(X)\neq\emptyset\ldots\)
Das heißt: wenn ich eine beliebige Kante herausnehme, ist o.g. Eigenschaft verletzt.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Übung 2 - Aufgabe 1

Beitrag von Stille »

Es ist vielleicht nicht allen klar geworden, daß sich diese Aufgabe unmittelbar auf das Lemma von Folie 17 bezieht.
Das heißt, Sie dürfen (und sollen) es benutzen ;-)
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Antworten

Zurück zu „Effiziente Graphenalgorithmen“