Erläuterung Folie 19

Moderator: Effiziente Graphenalgorithmen

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

Erläuterung Folie 19

Beitrag von Stille »

D is minimal by inclusion w.r.t. its edges, with \(\delta^{+}(X) \neq \emptyset\) for all \(X \subset V\) with \(r \in X\).

bedeutet so viel wie: D ist ein minimaler Graph bzgl. seiner Kanten, für den folgendes gilt: \(\delta^{+}(X) \neq \emptyset\) für alle \(\emptyset \neq X \subset V\) mit \(r \in X\).
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

DreamFlasher
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 102
Registriert: 12. Okt 2010 12:44

Re: Erläuterung Folie 19

Beitrag von DreamFlasher »

Danke für die Erläuterung.
Aber ist das Lemma bei (e) nicht falsch?
Der folgende Graph ist aboreszent: A->B. A ist dabei root hat einen indegree von 0 und einen outdegree von 1. B (ist ein Blatt, und) hat einen indegree von 1 und einen outdegree von 0. Letzteres schließt aber das Lemma aus.
Müsste im Lemma (e) daher nicht Delta- (indegree) stehen?

Viele Grüße
Marcel
Marcel Ackermann
http://www.dreamflasher.de
Machine Learning, Natural Language Processing, Algorithms

Interesse an Machine Learning, Artificial Intelligence, Natural Language Processing? Du möchtest deine Skills und Wissen verbessern, an Wettbewerben mit anderen Begeisterten teilnehmen? Mach mit bei unserer Study Group: http://groups.google.com/group/ml-ai

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

Re: Erläuterung Folie 19

Beitrag von Stille »

Hallo Marcel,

nein, die Wurzel ist ja Bestandteil von X (oder A im Beispiel), und X ist eine echte Teilmenge von V (A und B im Beispiel), die Kante(n) führt(en) also aus X (bzw. A) heraus.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Kai.S
Windoof-User
Windoof-User
Beiträge: 38
Registriert: 10. Apr 2010 22:22

Re: Erläuterung Folie 19

Beitrag von Kai.S »

Bei d) bedeuted accessible ebenso wie bei c) "by a directed path", oder? Sonst käme man zwar von allen auf d), aber von d) wenn man einfach ein paar Kanten umdreht nichtmehr zurück, oder?
Verwirrt mich nur, dass einmal "by a directed path" dabei steht, einmal nicht...

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

Re: Erläuterung Folie 19

Beitrag von Stille »

Ja, das ist dasselbe. Wenn ich im gerichteten Fall einen Knoten v von einem Knoten u aus erreichen kann, dann natürlich über einen gerichteten u-v-Pfad. Das mit den Kanten umdrehen verstehe ich nicht...
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

DreamFlasher
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 102
Registriert: 12. Okt 2010 12:44

Re: Erläuterung Folie 19

Beitrag von DreamFlasher »

Danke Herr Stille, vielen Dank, ja so macht das ganze mehr Sinn :)
Marcel Ackermann
http://www.dreamflasher.de
Machine Learning, Natural Language Processing, Algorithms

Interesse an Machine Learning, Artificial Intelligence, Natural Language Processing? Du möchtest deine Skills und Wissen verbessern, an Wettbewerben mit anderen Begeisterten teilnehmen? Mach mit bei unserer Study Group: http://groups.google.com/group/ml-ai

Antworten

Zurück zu „Effiziente Graphenalgorithmen“