TU Wien:Mathematik 1 VO (Panholzer)/Stoff WS05/19. VO 23.11.2005

$G=\langle V,E,l\rangle$ ist ein gerichteter oder ungerichteter, zusammenhängender Graph mit einer nichtnegativen Bewertungsfunktion.

$l:E\rightarrow R_{0}^{+}$

Algorithmus von Dijkastra und Danzig

Algorithmus zum Auffinden eines (oder aller) kürzesten Wege in einem Graph (zusammenhängend mit nichtnegativer Bewertungsfunktion) von einem beliebigen Ausgangspunkt a zu einem Endpunkt b.

(Graph 1)

$V=U\cup (V\backslash U)$

• U ... endgültig markierte Knoten
• V\U ... vorläufig markierte Knoten

Algorithmus Schritt 1

$l(a):=0,l(v):=\infty \qquad \forall v\in V\backslash \{a\}$

$U=\{a\}$, u = a

• u ... Knoten von dem weiter gemacht wird

Algorithmus Schritt 2

Betrachte alle (u,v) $\in$ E, mi $v\in V\backslash U$. (alle noch nicht endgültg markierten Nachbarn von u)

berechne für alle diese v:

$l(v):=\min\{l(v),l(u)+l(u,v)\}$

Algorithmus Schritt 3

Wähle aus V\U einen Knoten v mit minimaler Bewertung l(v).

$U:=U\cup \{v\}$

$u:=v$

Algorithmus Schritt 4

Wenn u = b, dann ist ist l(b) die Länge eines kürzesten Wegen von a nach b

Falls $a\neq b$ iteriere weiter mit Schritt 2.

Nach höchstens |V| - 1 Schritten wurde die Länge eines kürzesten Wegses von a nach b ermittelt.

Zum Ermiteln aller kürzesten Wege, bestimmt man rekursiv, beginnend mit v = b, alle Vorgänger u, indem man l(u) + l(u,v) = l(v) berücksichtigt, bis u=a erreicht wird.

(Graph Skriptum S. 35)

Iteration	$V_{0}$	$V_{1}$	$V_{2}$	$V_{3}$	$V_{4}$	$V_{5}$	/	Auswahl u	Vorgänger
1	0	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	/	$V_{0}$
2		2	5	$\infty$	$\infty$	$\infty$	/	$V_{1}$	$V_{0}$
3			4	6	5	$\infty$	/	$V_{2}$	$V_{1}$
4				6	5	$\infty$	/	$V_{4}$	$V_{1}$
5				6		11	/	$V_{3}$	$V_{1}$
						10	/	$V_{5}$	$V_{3}$

Länge eines kürzesten Weges: l(b) = 10

Kürzester Weg (eindeutig bester): $V_{0}\rightarrow V_{1}\rightarrow V_{3}\rightarrow V_{5}$

(Graph Skriptum S. 36 - Entfernungsbaum)

Beispiele für Anwendungen der Graphentheorie:

• Maximale Flüsse in Netzwerken (Ford-Fulkerson-Algorithmus)
• Kritische Pfade in Netzplänen
• Planarität von Graphen
• Färbungen von Graphen (Vierfarbensatz) ...

Komplement eines Graphen

Schlichter, gerichteter oder ungerichteter Graph

$G=\langle V,E\rangle$

Komplement: $G'=\langle V,E'\rangle$

mit $E':=\{(u,v),u,v\in V,u\neq v\}$, mit $u,v\notin E$ im ungerichteten Fall; im gerichteten Fall $E':=\{\{u,v\},u,v\in V,u\neq v\}$, mit $u,v\notin E$