Fragen zur ersten Vorlesung

Moderator: Effiziente Graphenalgorithmen

RedNifre
DON'T PANIC
Beiträge: 42
Registriert: 22. Nov 2004 19:29
Wohnort: Hier
Kontaktdaten:

Fragen zur ersten Vorlesung

Beitrag von RedNifre »

Mir sind einige Dinge noch nicht so ganz klar:

Folie 7
EH = {(v , w ) ∈ EG | v , w ∈ VH }
Von der Bedeutung her nehme ich an, es bedeutet man nimmt alle Kanten aus EG, deren beiden Endknoten in VH sind, aber wie spricht man diese Formel korrekt aus, bzw was ist ihre exakte Bedeutung/Aussage?

Folie 8
Ich verstehe die Edge Progression Definition für den Fall k=0 nicht, da in diesem Fall ja nicht existente Knoten referenziert werden.
Welche von folgenden drei Dingen ist die erste gültige Edge Progression?
1. {} (Leere Edge Progression)
2. v1 (Nur auf einem Knoten verweilen)
3. v1,e1,v2 (erste "sinnvolle" Progression?)

Simple Path:
Der zweite Teil der Node Disjointness Definition erscheint mir unnötig (vi != vj for 1 ≤ i < j ≤ k + 1 ). Ist das nicht schon dadurch ausgeschlossen, dass auf Folie 4 ein Graph so definiert ist, dass nur die Menge der Edges ein Multiset sein darf, während die der Vertices auf ein normales Set beschränkt ist? Oder kann die Menge der Vertices bei einem Graph auch ein Multiset sein?
+++++++++[->+++++++++>+>+>+<<<<]>+.>[-<->]<----.-.>>[-<<+>>]<<+.-----.---.>>>[-<<<+>>>]<<<+++.-------------.

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

Re: Fragen zur ersten Vorlesung

Beitrag von Stille »

Hallo,

\(E_H = \{(v , w ) \in E_G | v , w \in V_H \}\) liest sich als die Menge aller Kanten \((v,w)\) aus \(E_G\) für die gilt: sowohl v als auch w sind in \(V_H\) enthalten.

Kantenzug: Hier denke ich ist gesunder Menschenverstand wichtiger als korrekter Formalismus: intuitiv würde ich sagen eine edge progression macht erst ab 2 Kanten Sinn (sonst wäre es einfach nur eine Kante). In der Hoffnung, dass es unmissverständlicher ist, habe den Satz daher geändert in: An edge progression W in G is a sequence \(v_1, e_1, v_2 ... , e_{k−1}, v_k\) such that \(k >2\) and \(e_i =(v_i,v_{i+1}) \in E_G\) for \(i =1,...,k\).

Pfad: Ja, ist im Prinzip unnötig, dient aber durchaus dem Verständnis, oder?!
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Antworten

Zurück zu „Effiziente Graphenalgorithmen“