Alda - User contributions [en]

Graphen und Graphenalgorithmen

2012-07-24T15:06:29Z

Stephan.meister: fixed depth first search function with parents list

== Einführung zu Graphen ==

=== Motivation -- Königsberger Brückenproblem ===
Leonhard Euler [http://de.wikipedia.org/wiki/Leonhard_Euler] erfand den Graphen-Formalismus 1736, um eine scheinbar banale Frage zu beantworten: Ist es möglich, in Königsberg (siehe Stadtplan von 1809 und die schematische Darstellung) einen Spaziergang zu unternehmen, bei dem jede der 7 Brücken genau einmal überquert wird?

[[Image:Koenigsberg1809.png]] 
[[Image:Koenigsberg.jpg]]

Ein Graph abstrahiert von der Geometrie des Problems und repräsentiert nur die Topologie. Jeder Stadtteil von Königsberg ist ein Knoten des Graphen, jede Brücke eine Kante. Der zum Brückenproblem gehörende Graph sieht also so aus:

O
/| \
\| \
O---O
/| /
\| /
O

Der gesuchte Spaziergang würde existieren, wenn es maximal 2 Knoten gäbe, an denen sich eine ungerade Zahl von Kanten trifft. Die Frage muss für Königsberg also verneint werden, denn hier gibt es vier solche Knoten. Ein leicht modifiziertes Problem ist allerdings lösbar: Im obigen Stadtplan erkennt man eine Fähre, die die Stadtteile Kneiphof und Altstadt verbindet. Bezieht man dieselbe in den Spaziergang ein, ergibt sich folgender Graph, bei dem nur noch zwei Knoten mit ungerader Kantenzahl existieren:

--O
/ /| \
\ \| \
--O---O
/| /
\| /
O

Inzwischen haben Graphen eine riesige Zahl weiterer Anwendungen gefunden. Einige Beispiele:

* Landkarten:
** Knoten: Länder
** Kanten: gemeinsame Grenzen

* Logische Schaltkreise:
** Knoten: Gatter
** Kanten: Verbindungen

* Chemie (Summenformeln):
** Knoten: chemische Elemente
** Kanten: Bindungen

* Soziologie (StudiVZ)
** Soziogramm
*** Knoten: Personen
*** Kanten: Freund von ...

=== Definitionen ===

;Ungerichteter Graph: Ein ungerichteter Graph G = ( V, E ) besteht aus
:* einer endliche Menge V von Knoten (vertices)
:* einer endlichen Menge <math>E \subset V \times V</math> von Kanten (edges)
:Die Paare (u,v) und (v,u) gelten dabei als nur ''eine'' Kante (somit gilt die Symmetriebeziehung: (u,v) ∈ E => (v,u) ∈ E ). Die Anzahl der Kanten, die sich an einem Knoten treffen, wird als ''Grad'' (engl. ''degree'') dieses Knotens bezeichnet:
:::degree(v) = |{v' ∈ V | (v,v') ∈ E}|
:(Die Syntax |{...}| bezeichnet dabei die Mächtigkeit der angegebenen Menge, also die Anzahl der Elemente in der Menge.)

Der Graph des Königsberger Brückenproblems ist ungerichtet. Bezeichnet man die Knoten entsprechend des folgenden Bildes
c
/| \
\| \
b---d
/| /
\| /
a

gilt für die Knotengrade: <tt>degree(a) == degree(c) == degree(d) == 3</tt> und <tt>degree(b) == 5</tt>. Genauer muss man bei diesem Graphen von einem ''Multigraphen'' sprechen, weil es zwischen einigen Knotenpaaren (nämlich (a, b) sowie (b, c)) mehrere Kanten ("Mehrfachkanten") gibt. Wir werden in dieser Vorlesung nicht näher auf Multigraphen eingehen.

;Gerichteter Graph: Ein Graph heißt ''gerichtet'', wenn die Kanten (u,v) und (v,u) unterschieden werden. Die Kante (u,v) ∈ E wird nun als Kante von u nach v (aber nicht umgekehrt) interpretiert. Entsprechend unterscheidet man jetzt den ''eingehenden'' und den ''ausgehenden Grad'' jedes Knotens:
:*out_degree(v) = |{v' ∈ V | (v,v') ∈ E}| 
:*in_degree(v) = |{v' ∈ V| (v',v) ∈ E}|

Das folgende Bild zeigt einen gerichteten Graphen. Hier gilt <tt>out_degree(1) == out_degree(3) == in_degree(2) == in_degree(4) == 2</tt> und
<tt>in_degree(1) == in_degree(3) == out_degree(2) == out_degree(4) == 0</tt>:

[[Image:digraph.png|gerichteter Graph]]

 

;Vollständiger Graph: Ein vollständiger Graph ist ein ungerichteter Graph, bei dem jeder Knoten mit allen anderen Knoten verbunden ist.
:::<math>E = \{ (v,w) | v \in V, w \in V, v \ne w \}</math>
:Ein vollständiger Graph mit |V| Knoten hat <math>|E| = \frac{|V|(|V|-1)}{2}</math> Kanten.

Die folgenden Abbildungen zeigen die vollständigen Graphen mit einem bis fünf Knoten (auch als K1 bis K5 bezeichnet).

{| border="0" cellspacing="0" cellpadding="0" style="margin: 1em auto 1em auto"
|-
| [[Image:k1.png|frame|k1]]
| [[Image:k2.png|frame|k2]]
| [[Image:k3.png|frame|k3]]
|-
| [[Image:k4.png|frame|k4]]
| [[Image:k5.png|frame|k5]]
|
|}

''Rätsel'' 
Auf einer Party sind Leute. Alle stoßen miteinander an. Es hat 78 mal "Pling" gemacht.
Wieviele Leute waren da? Antwort: Jede Person ist ein Knoten des Graphen, jedes Antoßen eine Kante.
Da alle miteinander angestoßen haben, handelt es sich um einen vollständigen Graphen. Mit
|V|(|V|-1)/2 = 78 folgt, dass es 13 Personen waren.

 

;Gewichteter Graph: Ein Graph heißt ''gewichtet'', wenn jeder Kante eine reelle Zahl zugeordnet ist. Bei vielen Anwendungen beschränkt man sich auch auf nichtnegative reelle Gewichte. In einem gerichteten Graphen können die Gewichte der Kanten (u,v) und (v,u) unterschiedlich sein.

Die Gewichte kodieren Eigenschaften der Kanten, die für die jeweilige Anwendung interessant sind. Bei der Berechnung des maximalen Flusses in einem Netzwerk sind die Gewichte z.B. die Durchflusskapazitäten jeder Kante, bei der Suche nach kürzesten Weges kodieren Sie den Abstand zwischen den Endknoten der Kante, bei Währungsnetzwerken (jeder Knoten ist eine Währung) geben sie die Wechselkurse an, usw..

 

;Teilgraphen: Ein Graph G' = (V',E') ist ein Teilgraph eines Graphen G, wenn gilt:
:* V' &sube; V
:* E' ⊂ E
:Er heißt ''(auf)spannender Teilgraph'', wenn gilt:
:* V' = V
:Er heißt ''induzierter Teilgraph'', wenn gilt:
:* e = (u,v) ∈ E' ⊂ E ⇔ u ∈ V' und v ∈ V'
:Den von V' induzierten Teilgraphen erhält man also, indem man aus G alle Knoten löscht, die nicht in V' sind, sowie alle Kanten (und nur diese Kanten), die einen der gelöschten Knoten als Endknoten haben.

 

;Wege, Pfade, Zyklen, Kreise, Erreichbarkeit: Sei G = (V,E) ein Graph (ungerichtet oder gerichteter) Graph. Dann gilt folgende rekursive Definition:
:* Für v ∈ V ist (v) ein Weg der Länge 0 in G
:* Falls <math>(v_0, v_1, ..., v_{n-1})</math> ein Weg ist, und eine Kante <math>(v_{n-1}, v_n)\in E</math> existiert, dann ist auch <math>(v_0, v_1, ..., v_{n-1}, v_n)</math> ein Weg, und er hat die Länge n.
: Ein Weg ist also eine nichtleere Folge von Knoten, so dass aufeinander folgende Knoten stets durch eine Kante verbunden sind. Die Länge des Weges entspricht der Anzahl der Kanten im Weg (= Anzahl der Knoten - 1).
:* Ein ''Pfad'' <math>(v_0, v_1, ..., v_{n-1}, v_n)</math> ist ein Weg, bei dem alle Knoten vi verschieden sind.
:* ''Ein Zyklus'' <math>(v_0, v_1, ..., v_{n-1}, v_n)</math> ist ein Weg, der zum Ausgangspunkt zurückkehrt, wenn also v0 = vn gilt.
:* Ein ''Kreis'' ist ein Zyklus ohne Überkreuzungen. Das heisst, es gilt v0 = vn und <math>(v_0, v_1, ..., v_{n-1})</math> ist ein Pfad.
:* Ein Knoten w ∈ V ist von einem anderen Knoten v ∈ V aus ''erreichbar'' genau dann, wenn ein Weg (v, ..., w) existiert. Wir schreiben dann <math>v \rightsquigarrow w</math>.
In einem ungerichteten Graph ist die Erreichbarkeits-Relation stets symmetrisch, das heisst aus <math>v \rightsquigarrow w</math> folgt <math>w \rightsquigarrow v</math>. In einem gerichteten Graphen ist dies im allgemeinen nicht der Fall.

Bestimmte Wege haben spezielle Namen

;Eulerweg: Ein Eulerweg ist ein Weg, der alle '''Kanten''' genau einmal enthält.

Die eingangs erwähnte Frage des Königsberger Brückenproblems ist equivalent zu der Frage, ob der dazugehörige Graph einen Eulerweg besitzt (daher der Name). Ein anderes bekanntes Beispiel ist das "Haus vom Nikolaus": Wenn man diesen Graphen in üblicher Weise in einem Zug zeichnet, erhält man gerade den Eulerweg.

O
/ \
O----O
| \/ |
| /\ | "Das Haus vom Nikolaus": Alle ''Kanten'' werden nur ''einmal'' passiert
O----O

;Hamiltonweg: Ein Hamiltonweg ist ein Weg, der alle '''Knoten''' genau einmal enthält. Das "Haus vom Nikolaus" besitzt auch einen Hamiltonweg:

O
/
O----O
/
/ Alle ''Knoten'' werden nur ''einmal'' passiert
O----O

;Hamiltonkreis: Ein Hamiltonkreis ist ein Kreis, der alle '''Knoten''' genau einmal enthält. Auch ein solches Gebilde ist im Haus von Nilolaus enthalten:

O
/ \
O O
| | v0 = vn
| | vi != vj Für Alle i,j i !=j; i,j >0; i,j < n
O----O

Die folgende Skizze zeigt hingegen einen Zyklus: Der Knoten rechts unten sowie die untere Kante sind zweimal enthalten (die Kante einmal von links nach rechts und einmal von rechts nach links):

O
/ \
O O
\ |
\ | Zyklus
O====O

 

;Zusammenhang, Zusammenhangskomponenten: Ein ungerichteter Graph G heißt ''zusammenhängend'', wenn für alle v,w ∈ V gilt:
:::<math>v \rightsquigarrow w</math>
:Ein gerichteter Graph G ist zusammenhängend, wenn für alle v,w ∈ V gilt:
:::<math>v \rightsquigarrow w</math> '''oder''' <math>w \rightsquigarrow v</math>.
:Er ist ''stark zusammenhängend'', wenn für alle v,w ∈ V gilt:
:::<math>v \rightsquigarrow w</math> '''und''' <math>w \rightsquigarrow v</math>.
:Entsprechende Definitionen gelten für Teilgraphen G'. Ein Teilgraph G' heisst ''Zusammenhangskomponente'' von G, wenn er ein ''maximaler'' zusammenhängender Teilgraph ist, d.h. wenn G' zusammenhängend ist, und man keine Knoten und Kanten aus G mehr zu G' hinzufügen kann, so dass G' immer noch zusammenhängend bleibt. Entsprechend definiert man ''starke Zusammenhangskomponenten'' in einem gerichteten Graphen.

 

;Planarer Graph, ebener Graph: Ein Graph heißt ''planar'', wenn er so in einer Ebene gezeichnet werden ''kann'', dass sich die Kanten nicht schneiden (außer an den Knoten). Ein Graph heißt ''eben'', wenn er tatsächlich so gezeichnet ''ist'', dass sich die Kanten nicht schneiden. Die Einbettung in die Ebene ist im allgemeinen nicht eindeutig.

'''Beispiele:'''

Der folgende Graph ist planar und eben:

O
/|\
/ O \
/ / \ \
O O

Das "Haus vom Nikolaus" ist ebenfalls planar, wird aber üblicherweise nicht als ebener Graph gezeichnet, weil sich die Diagonalen auf der Wand überkreuzen:

O
/ \
O----O
| \/ |
| /\ |
O----O

Eine ebene Einbettung dieses Graphen wird erreicht, wenn man eine der Diagonalen ausserhalb des Hauses zeichnet. Der Graph (also die Menge der Knoten und Kanten) ändert sich dadurch nicht.

O
/ \
--O----O
/ | / |
| | / |
| O----O Das "Haus vom Nikolaus" als ebener Graph gezeichnet.
\ /
-----

Eine alternative Einbettung erhalten wir, wenn wir die andere Diagonale außerhalb des Hauses zeichnen:

O
/ \
O----O--|
| \ | |
| \ | |
O----O | Alternative Einbettung des "Haus vom Nikolaus".
| |
|-------|

Jede Einbettung eines planaren Graphen (also jeder ebene Graph) definiert eine eindeutige Menge von ''Regionen'':

|----O @
| /@ \
| O----O
| |@ / |
| | / @|
| O----O @ entspricht jeweils einer ''Region''. Auch ausserhalb der Figur ist eine Region (die sogenannte ''unendliche'' Region).
|@ |
|-------|

Der vollständige Graph K5 ist kein planarer Graph, da sich zwangsweise Kanten schneiden, wenn man diesen Graphen in der Ebene zeichnet.

 
;Dualer Graph: Jeder ebene Graph G = (V, E) hat einen ''dualen Graphen'' D = (VD, ED), dessen Knoten und Kanten wie folgt definiert sind:
:* VD enthält einen Knoten für jede Region des Graphen G
:* Für jede Kante e ∈ E gibt es eine duale Kante eD ∈ ED, die die an e angrenzenden Regionen (genauer: die entsprechenden Knoten in D) verbindet.

Die folgende Abbildung zeigt einen Graphen (grau) und seinen dualen Graphen (schwarz). Die Knoten des dualen Graphen sind mit Zahlen gekennzeichnet und entsprechen den Regionen des Originalgraphen. Jeder (grauen) Kante des Originalgraphen entspricht eine (schwarze) Kante des dualen Graphen.

 
[[Image:dual-graphs.png]]
 

Für duale Graphen gilt: Wenn der Originalgraph zusammenhängend ist, enthält jede Region des dualen Graphen genau einen Knoten des Originalgraphen. Deshalb ist der duale Graph des dualen Graphen wieder der Originalgraph. Bei nicht-zusammenhängenden Graphen gilt dies nicht (vgl. das Fenster bei obigem Bild). In diesem Fall hat der duale Graph mehrere mögliche Einbettungen in die Ebene (man kann z.B. die rechte Kante zwischen Knoten 2 und 4 auch links vom Fenster einzeichnen), und man erhält nicht notwendigerweise den Originalgraphen, wenn man den dualen Graphen des dualen berechnet.

;Baum: Ein ''Baum'' ist ein zusammenhängender, kreisfreier Graph.

Beispiel: Binärer Suchbaum

;Spannbaum: Ein ''Spannbaum'' eines zusammenhängenden Graphen G ist ein zusammenhängender, kreisfreier Teilgraph von G, der alle Knoten von G enthält

Beispiel: Spannbaum für das "Haus des Nikolaus"

O
/
O O
| /
| /
O----O

Der Spannbaum eines Graphen mit |V| Knoten hat stets |V| - 1 Kanten.

;Wald: Ein ''Wald'' ist ein unzusammenhängender, kreisfreier Graph.
: Jede Zusammenhangskomponente eines Waldes ist ein Baum.

=== Repräsentation von Graphen ===

Sei G = ( V, E ) gegeben und liege V in einer linearen Sortierung vor. 
:::<math>V = \{ v_1, ...., v_n \}</math>

;Adjazenzmatrix: Ein Graph kann durch eine Adjazenzmatrix repräsentiert werden, die soviele Zeilen und Spalten enthält, wie der Graph Knoten hat. Die Elemente der Adjazenzmatrix sind "1", falls eine Kante zwischen den zugehörigen Knoten existiert:
:::<math>\mathrm{\bold A} = a_{ij} =
\begin{cases}
1 & \mathrm{falls}\quad (v_i, v_j) \in E \\
0 & \mathrm{sonst}
\end{cases}
</math>
:Die Indizes der Matrix entsprechen also den Indizes der Knoten gemäß der gegebenen Sortierung. Im Falle eines ungerichteten Graphen ist die Adjazenzmatrix stets symmetrisch (d.h. es gilt <math>a_{ij}=a_{ji}</math>), bei einem gerichteten Graphen ist sie im allgemeinen unsymmetrisch.

Beispiel für einen ungerichteten Graphen:

v = { a,b,c,d } b d
| \ / |
| \/ |
| /\ |
| / \ |
a c

a b c d
-----------
(0 1 0 1) |a
A = (1 0 1 0) |b
(0 1 0 1) |c
(1 0 1 0) |d

Die Adjazenzmatrixdarstellung eignet sich besonders für dichte Graphen (d.h. wenn die Zahl der Kanten in O(|V|2) ist.

;Adjazenzlisten: In der Adjazenzlistendarstellung wird der Graph als Liste von Knoten repräsentiert, die für jeden Knoten einen Eintrag enthält. Der Eintrag für jeden Knoten ist wiederum eine Liste, die die Nachbarknoten dieses Knotens enthält:
:* graph = {adjazencyList(v) | v ∈ V}
:* adjazencyList(v) = {v' ∈ V | (v, v') ∈ E}

In Python implementieren wir Adjazenzlisten zweckmäßig als Array von Arrays:

graph = [[...],[...],...,[...]]
Adjazenzliste für Knoten => 0 1 n

Wenn wir bei dem Graphen oben die Knoten wie bei der Adjazenzmatrix indizieren (also <tt>a => 0</tt>, <tt>b => 1</tt>, <tt>c => 2</tt>, <tt>d => 3</tt>), erhalten wir die Adjazenzlistendarstellung:

graph = [[b, d], [a, c],[b, d], [a, c]]

Auf die Nachbarknoten eines durch seinen Index <tt>node</tt> gegebenen Knotens können wir also wie folgt zugreifen:

for neighbors in graph[node]:
... # do something with neighbor

Die Adjazenzlistendarstellung ist effizienter, wenn der Graph nicht dicht ist, so dass viele Einträge der Adjazenzmatrix Null wären. In der Vorlesung werden wir nur diese Darstellung verwenden.

;<div id="transposed_graph">Transponierter Graph</div>: Den ''transponierten Graphen'' GT eines gerichteten Graphen G erhält man, wenn man alle Kantenrichtungen umkehrt.

Bei ungerichteten Graphen hat die Transposition offensichtlich keinen Effekt, weil alle Kanten bereits in beiden Richtungen vorhanden sind, so dass GT = G gilt. Bei gerichteten Graphen ist die Transposition einfach, wenn der Graph als Adjazenzmatrix implementiert ist, weil man einfach die transponierte Adjazenzmatrix verwenden muss (beachte, dass sich die Reihenfolge der Indizes umkehrt):
:::AT = aji
Ist der Graph hingegen durch eine Adjazenzliste repräsentiert, muss etwas mehr Aufwand getrieben werden:

def transposeGraph(graph):
gt = [[] for k in graph] # zunächst leere Adjazenzlisten von GT
for node in range(len(graph)):
for neighbor in graph[node]:
gt[neighbor].append(node) # füge die umgekehrte Kante in GT ein
return gt

== Durchlaufen von Graphen (Graph Traversal) ==

Wir betrachten zunächst ungerichtete Graphen mit V Knoten und E Kanten. Eine grundlegende Aufgabe in diesen Graphen besteht darin, alle Knoten in einer bestimmten Reihenfolge genau einmal zu besuchen. Hierbei darf man sich von einem gegebenen Startknoten aus nur entlang der Kanten des Graphen bewegen. Die beim Traversieren benutzen Kanten bilden einen Baum, dessen Wurzel der Startknoten ist und der den gesamten Graphen aufspannt, falls der Graph zusammenhängend ist. (Beweis: Da jeder Knoten nur einmal besucht wird, gibt es für jeden besuchten Knoten [mit Ausnahme des Startknotens] genau eine eingehende Kante. Ist der Graph zusammenhängend, wird jeder Knoten tatsächlich erreicht und es gibt genau (V-1) Kanten, exakt soviele wie für einen Baum mit V Knoten notwendig sind.) Ist der Graph nicht zusammenhängend, wird jeder zusammenhängende Teilgraph (jede Zusammenhangskomponente) getrennt traversiert, und man erhält einen sogenannten Wald mit einem Baum pro Zusammenhangskomponente. Die beiden grundlegenden Traversierungsmethoden Tiefensuche und Breitensuche werden im folgenden vorgestellt.

=== Tiefensuche in Graphen (Depth First Search, DFS) ===

Die Idee der Tiefensuche besteht darin, jeden besuchten Knoten sofort über die erste Kante wieder zu verlassen, die zu einem noch nicht besuchten Knoten führt. Man findet dadurch schnell einen möglichst langen Pfad durch den Graphen, und der Traversierungs-Baum wird zunächst in die Tiefe verfolgt, daher der Name des Verfahrens. Hat ein Knoten keine unbesuchten Nachbarknoten mehr, geht man im Baum zurück (sogenanntes back tracking), bis man einen Knoten findet, der noch eine unbesuchte Nachbarn besitzt, und traversiert diese nach dem gleichen Muster. Gibt es gar keine unbesuchten Knoten mehr, kehrt die Suche zum Startknoten zurück und endet dort.

WDie folgende rekursive Implementation der Tiefensuche erwartet den Graphen in Adjazenzlistendarstellung und beginnt die Suche beim Knoten <tt>startnode</tt>. Die Information, ob ein Knoten bereits besucht wurde, wird im Array <tt>visited</tt> gespeichert. Ein solches Array, das zusätzliche Informationen über die Knoten des Graphen bereitstellt, wir häufig property map genannt.

def dfs(graph, startnode):
visited = [False]*len(graph) # Flags, welche Knoten bereits besucht wurden

def visit(node): # rekursive Hilfsfunktion, die den gegebenen Knoten und dessen Nachbarn besucht
if not visited[node]: # Besuche node, wenn er noch nicht besucht wurde
visited[node] = True # Markiere node als besucht
print node # Ausgabe der Knotennummer - pre-order
for neighbor in graph[node]: # Besuche rekursiv die Nachbarn
visit(neighbor)

visit(startnode)

[[Image:Tiefens.jpg]]

Ausgabe für den Graphen in diesem Bild (es handelt sich um einen ungerichteten Graphen, die Pfeile symbolisieren nur die Suchrichtung beim Traversal):

>>> dfs(graph, 1)
1
2
4
3
6
7
5

<div id="pre_and_post_order">In dieser Version des Algorithmus werden die Knotennummern ausgegeben, bevor die Nachbarknoten besucht werden. Man bezeichnet die resultierende Sortierung der Knoten als pre-order oder als discovery order. Alternativ kann man die Knotennummern erst ausgeben, nachdem alle Nachbarn besucht wurden, also auf dem Rückweg der Rekursion. In diesem Fall spricht man von post-order oder finishing order:</div>

def dfs(graph, startnode):
visited = [False]*len(graph) # Flags, welche Knoten bereits besucht wurden

def visit(node): # rekursive Hilfsfunktion, die den gegebenen Knoten und dessen Nachbarn besucht
if not visited[node]: # Besuche node, wenn er noch nicht besucht wurde
visited[node] = True # Markiere node als besucht
for neighbor in graph[node]: # Besuche rekursiv die Nachbarn
visit(neighbor)
print node # Ausgabe der Knotennummer - post-order

visit(startnode)

Es ergibt sich jetzt die Ausgabe:

>>> dfs(graph, 1)
6
7
3
4
5
2
1

In realem Code ersetzt man die print-Ausgaben natürlich durch anwendungsspezifische Aktionen und Berechnungen. Einige Anwendungen sind uns im Kapitel [[Suchen]] bereits begegnet.
; Anwendungen der Pre-Order Traversierung
* Kopieren eines Graphen: kopiere zuerst den besuchten Knoten, dann seine Nachbarn und die dazugehörigen Kanten (sowie die Kanten zu bereits besuchten Knoten, die in der Grundversion der Tiefensuche ignoriert werden).
* Bestimmen der Zusammenhangskomponenten eines Graphen (siehe unten)
* In einem Zeichenprogramm: fülle eine Region mit einer Farbe ("flood fill"). Dabei ist jedes Pixel ein Knoten des Graphen und wird mit seinen 4 Nachbarpixceln verbunden. Die Tiefensuche startet bei der Mausposition und endet am Rand des betreffendcen Gebiets.
* Falls der Graph ein Baum ist: bestimme den Abstand jedes Knotens von der Wurzel
* Falls der Graph ein Parse-Baum ist, wobei innere Knoten Funktionsaufrufe, Kindknoten Funktionsargumente, und Blattknoten Werte repräsentieren: drucke den zugehörigen Ausdruck aus (also immer zuerst den Funktionsnamen, dann die Argumente, die wiederum geschachtelte Funktionsaufrufe sein können).
; Anwendungen der Post-Order Traversierung
* Löschen eines Graphen: lösche zuerst die Nachbarn, dann den Knoten selbst
* Bestimmen einer topologischen Sortierung eines azyklischen gerichteten Graphens (siehe unten)
* Falls der Graph ein Baum ist: bestimme den Abstand jedes Knotens von den Blättern (also die Tiefe des Baumes, siehe Übung 5)
* Falls der Graph ein Parse-Baum ist: führe die zugehörige Berechnung aus (d.h. berechne zuerst die geschachtelten inneren Funktionen, dann mit diesen Ergebnissen die nächst äußeren usw., siehe Übung 5).
; Anwendungen, die Pre- und Post-Order benötigen
* Weg aus einem Labyrinth: die Pre-Order dokumentiert die Suche nach dem Weg, die Post-Order zeigt den Rückweg aus Sackgassen (siehe Übung 9).
Im Spezialfall, wenn der Graph ein Binärbaum ist, unterscheidet man noch eine dritte Variante der Traversierung, nämlich die in-order Traversierung. In diesem Fall behandelt man den Vaterknoten nach den linken, aber vor den rechten Kindern. Diese Reihenfolge wird beim [[Suchen#Beziehungen zwischen dem Suchproblem und dem Sortierproblem|Tree Sort Algorithmus]] verwendet. Diese Sortierung verwendet man auch, wenn man einen Parse-Baum mit binären Operatoren (statt Funktionsaufrufen) ausgeben will, siehe Übung 5.

Eine nützliche Erweiterung der Tiefensuche besteht darin, in der property map <tt>visited</tt> nicht nur zu dokumentieren, dass ein Knoten bereits besucht wurde, sondern auch, von welchem Knoten aus man den jeweiligen Knoten zuerst erreicht hat. Im entstehenden Tiefensuchbaum ist dies gerade der Vaterknoten, weshalb wir die verbesserte property map zweckmäßigerweise in <tt>parents</tt> umbenennen. Für den Startknoten, also die Wurzel des Baumes, wählen wir die Konvention, dass er sein eigener Vaterknoten ist (die Konvention, dafür den Wert <tt>None</tt> zu verwenden, scheidet aus, weil dies bereits die Tatsache signalisiert, dass ein Knoten noch nicht besucht wurde):

def dfs(graph, startnode):
parents = [None]*len(graph) # Registriere für jeden Knoten den Vaterknoten im Tiefensuchbaum

def visit(node, parent): # rekursive Hilfsfunktion
if parents[node] is None: # Besuche node, wenn er noch nicht besucht wurde
parents[node] = parent # Markiere node als besucht und speichere seinen Vaterknoten
for neighbor in graph[node]: # Besuche rekursiv die Nachbarn ...
visit(neighbor, node) # ... wobei node zu deren Vaterknoten wird

visit(startnode, startnode) # Konvention für Wurzel: startnode ist sein eigener Vater

return parents # Rückgabe des berechneten Tiefensuch-Baums

Die Ausgabe für den obigen Beispielgraphen lautet:
Knotennummer | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
--------------+-----+-----+-----+-----+-----+-----+-----+-----
Vaterknoten | None| 1 | 1 | 4 | 2 | 2 | 3 | 3

Dabei ist die Knotennummer der Index im Array <tt>parents</tt>, und der Vaterknoten ist der dazugehörige Arrayeintrag. Beachte, dass Knoten 0 in diesem Graphen nicht existiert, daher ist sein Eintrag <tt>None</tt>. Per Konvention hat der Wurzelknoten 1 sich selbst als Vater.

=== Breitensuche in Graphen (Breadth First Search, BFS) ===

Im Gegensatz zur Tiefensuche werden bei der Breitensuche alle Nachbarnknoten abgearbeitet, bevor man rekursiv deren Nachbarn besucht. Man betrachtet somit zuerst alle Knoten, die den Abstand 1 von Startknoten haben, dann diejenigen mit dem Abstand 2 usw. Diese Reihenfolge bezeichnet man als level-order. Wir sind ihr beispielsweise in Übung 6 begegnet, als die ersten 7 Ebenen eines Treap ausgegeben werden sollten. Man implementiert Breitensuche zweckmäßig mit Hilfe einer Queue, die die Knoten in First In - First Out - Reihenfolge bearbeitet. Eine geeignete Datenstruktur hierfür ist die Klasse <tt>[http://docs.python.org/library/collections.html#collections.deque deque]</tt> aus dem Python-Modul <tt>[http://docs.python.org/library/collections.html collections]</tt> (eine Deque implementiert sowohl die Funktionalität einer Queue wie auch die eines Stacks, siehe Übung 3):

from collections import deque

def bfs(graph, startnode)
visited = [False]*len(graph) # Flags, welche Knoten bereits besucht wurden

q = deque() # Queue für die zu besuchenden Knoten
q.append(startnode) # Startknoten in die Queue einfügen

while len(q) > 0: # Solange es noch unbesuchte Knoten gibt
node = q.popleft() # Knoten aus der Queue nehmen (first in - first out)
if not visited[node]: # Falls node noch nicht (auf einem anderen Weg) besucht wurde
visited[node] = True # Markiere node als besucht
print node # Drucke Knotennummer
for neighbor in graph[node]: # Füge Nachbarn in die Queue ein
q.append(neighbor)

[[Image:Breitens.jpg]]

Der Aufruf dieser Funktion liefert die Knoten des obigen Graphens ebenenweise, also zufällig genau in der Reihenfolge der Knotennummern:
>>> bfs(graph, 1)
1
2
3
4
5
6
7

Neben der ebenenweisen Ausgabe hat die Breitensuche viele weitere wichtige Anwendungen, z.B. beim Testen, ob ein gegebener Graph bi-partit ist (siehe [http://en.wikipedia.org/wiki/Breadth-first_search#Testing_bipartiteness WikiPedia]), sowie bei der Suche nach kürzesten Wegen (siehe unten) und kürzesten Zyklen.

== Weitere Anwendungen der Tiefensuche ==

Die Tiefensuche hat zahlreiche Anwendungen, wobei der grundlegende Algorithmus immer wieder leicht modifiziert und an die jeweilige Aufgabe angepasst wird. Wir beschreiben im folgenden einige Beispiele.

=== Damenproblem ===

Tiefensuche wird häufig verwendet, um systematisch nach der Lösung eines logischen Rätsels (oder allgemeiner nach der Lösung eines diskreten Optimierungsproblems) zu suchen. Besonders anschaulich hierfür ist das Damenproblem. Die Aufgabe besteht darin, <math>k</math> Damen auf einem Schachbrett der Größe <math>k \times k</math> so zu platzieren, dass sie sich (nach den üblichen Schach-Regeln) nicht gegenseitig schlagen können. Das folgende Diagramm zeigt eine Lösung für den Fall <math>k=4</math>. Die Positionen der Damen werden dabei wie üblich durch die Angabe der Spalte (Linie) mit Buchstaben und der Zeile (Reihe) mit Zahlen kodiert, hier also A2, B4, C1, D3:

---------------
| | X | | | 4
|---|---|---|---|
| | | | X | 3
|---|---|---|---|
| X | | | | 2
|---|---|---|---|
| | | X | | 1
---------------
A B C D

Um das Problem systematisch zu lösen, konstruieren wir einen gerichteten Graphen, dessen Knoten die möglichen Positionen der Damen kodieren. Wir verbinden Knoten, die zu benachbarten Linien gehören, genau dann mit einer Kante, wenn die zugehörigen Positionen kompatibel sind, also wenn sich die dort positionierten Damen nicht schlagen können. Der resultierende Graph für <math>k=4</math> hat folgende Gestalt:

[[Image:damenproblem-graph.png|500px|center]]

Knoten, die zur selben Reihe oder Linie gehören, sind beispielsweise nicht direkt verbunden, weil zwei Damen niemals in derselben Linie oder Reihe stehen dürfen. Um eine erlaubte Konfiguration zu finden, verwenden wir nun eine angepasste Version der Tiefensuche: Wir beginnen die Suche beim Knoten <tt>START</tt>. Sobald wir den Knoten <tt>STOP</tt> erreichen, beenden wir die Suche und lesen die Lösung am gerade gefundenen Weg von Start nach Stop ab. Zwei kleine Modifikationen des Grundalgorithmus stellen sicher, dass die Bedingungen der Aufgabe eingehalten werden: Wir dürfen bei der Tiefensuche nur dann zu einem Nachbarn weitergehen, wenn die betreffende Position mit allen im Pfad bereits gesetzten Positionen kompatibel ist, andernfalls ist diese Kante tabu. Landen wir aufgrund dieser Regel in einer Sackgasse (also in einem Knoten, wo keine der ausgehenden Kanten erlaubt ist), müssen wir zur nächsten erlaubten Abzweigung zurückgehen (Backtracking). Beim Zurückgehen müssen wir das <tt>parent</tt>-Flag wieder auf <tt>None</tt> zurücksetzen, weil der betreffende Knoten ja möglicherweise auf einem anderen erlaubten Weg erreichbar ist.

Der folgende Graph zeigt einen solchen Fall: Wir haben zwei Damen auf die Felder A1 und B3 positioniert (grüne Pfeile). Die einzig ausgehende Kante von B3 führt zum Knoten C1, welcher aber mit der Position A1 inkompatibel ist, so dass diese Kante nicht verwendet werden darf (roter Pfeil). Das Backtracking muss jetzt zu Knoten A1 zurückgehen (dabei wird das <tt>parent</tt>-Flag von B3 wieder auf <tt>None</tt> gesetzt), weil A1 mit der Kante nach B4 eine weitere Option hat, die geprüft werden muss (die allerdings hier auch nicht zum Ziel führt).

[[Image:damenproblem-graph-failure.png|500px|center]]

Nach einigen weiteren Sackgassen findet man schließlich den Pfad A2, B4, C1, D3, der im folgenden Graphen grün markiert ist und der obigen Lösung entspricht:

[[Image:damenproblem-graph-success.png|500px|center]]

=== Test, ob ein ungerichteter Graph azyklisch ist ===

Ein zusammenhängender ungerichteter Graph ist azyklisch (also ein Baum) genau dann, wenn es nur einen möglichen Weg von jedem Knoten zu jedem anderen gibt. (Bei gerichteten Graphen sind die Verhältnisse komplizierter. Wir behandeln dies weiter unten.) Das kann man mittels Tiefensuche leicht feststellen: Die Kante, über die wir einen Knoten erstmals erreichen, ist eine Baumkante des Tiefensuchbaums. Erreichen wir einen bereits besuchten Knoten nochmals über eine andere Kante, haben wir einen Zyklus gefunden. Dabei müssen wir allerdings beachten, dass in einem ungerichteten Graphen jede Baumkante zweimal gefunden wird, einmal in Richtung vom Vater zum Kind und einmal in umgekehrter Richtung. Im zweiten Fall endet die Kante zwar in einem bereits besuchten Knoten (dem Vater), aber es entsteht dadurch kein Zyklus. Den Vaterknoten müssen wir deshalb überspringen, wenn wir über die Nachbarn iterieren:

def undirected_cycle_test(graph): # Annahme: der Graph ist zusammenhängend
# (andernfalls führe den Algorithmus für jede Zusammenhangskomponente aus)
visited = [False]*len(graph) # Flags für bereits besuchte Knoten

def visit(node, from_node): # rekursive Hilfsfunktion: gibt True zurück, wenn Zyklus gefunden wurde
if not visited[node]: # wenn node noch nicht besucht wurde
visited[node] = True # markiere node als besucht
for neighbor in graph[node]: # besuche die Nachbarn ...
if neighbor == from_node: # ... aber überspringe den Vaterknoten
continue
if visit(neighbor, node): # ... signalisiere, wenn rekursiv ein Zyklus gefunden wurde
return True
return False # kein Zyklus gefunden
else:
return True # Knoten schon besucht => Zyklus

startnode = 0 # starte bei beliebigem Knoten (hier: Knoten 0)
return visit(startnode, startnode) # gebe True zurück, wenn ein Zyklus gefunden wurde

Wenn wir einen Zyklus finden, wird das weitere Traversieren das Graphen abgebrochen, denn ein Graph, der einmal zyklisch war, kann später nicht wieder azyklisch werden. Die notwendige Modifikation für unzusammenhängende Graphen erfolgt analog zum Algorithmus für die Detektion von Zusammenhangskomponenten, der im nächsten Abschnitt beschrieben wird.

=== Finden von Zusammenhangskomponenten ===

Das Auffinden und Markieren von Zusammenhangskomponenten (also maximalen zusammenhängenden Teilgraphen) ist eine grundlegende Aufgabe in ungerichteten, unzusammenhängenden Graphen (bei gerichteten Graphen sind die Verhältnisse wiederum komplizierter, siehe unten). Zwei Knoten u und v gehören zur selben Zusammenhangskomponente genau dann, wenn es einen Pfad von u nach v gibt (da der Graph ungerichtet ist, gibt es dann auch einen Pfad von v nach u). Man sagt auch, dass "v von u aus erreichbar" ist. Unzusammenhängende Graphen entstehen in der Praxis häufig, wenn die Kanten gewisse Relationen zwischen den Knoten kodieren:
* Wenn die Knoten Städte sind und die Kanten Straßen, sind diejenigen Städte in einer Zusammenhangskomponente, die per Auto von einander erreichbar sind. Unzusammenhängende Graphen entstehen hier beispielsweise, wenn eine Insel nicht durch eine Brücke erschlossen ist, wenn Grenzen gesperrt sind oder wenn ein Gebirge zu unwegsam ist, um Straßen zu bauen.
* Wenn Knoten Personen sind, und Kanten die Eltern-Kind-Relation beschreiben, so umfasst jede Zusammenhangskomponenten die Verwandten (auch wenn sie nur über viele "Ecken" verwandt sind).
* In der Bildverarbeitung entsprechen Knoten den Pixeln, und dieselben werden durch eine Kante verbunden, wenn sie zum selben Objekt gehören. Die Zusammenhangskomponenten entsprechen somit den Objekten im Bild (siehe Übungsaufgabe).
Die Zusammenhangskomponenten bilden eine Äquivalenzrelation. Folglich kann für jede Komponente ein Reprässentant bestimmt werden, der sogenannte "Anker". Kennt jeder Knoten seinen Anker, ist das Problem der Zusammenhangskomponenten gelöst.

==== Lösung mittels Tiefensuche ====

Unser erster Ansatz ist, den Anker mit Hilfe der Tiefensuche zu finden. Anstelle der property map <tt>visited</tt> verwenden wir diesmal eine property map <tt>anchors</tt>, die für jeden Knoten die Knotennummer des zugehörigen Ankers angibt, oder <tt>None</tt>, wenn der Knoten noch nicht besucht wurde. Dabei verwenden wir wieder die Konvention, dass Anker auf sich selbst zeigen. Für viele Anwendungen ist es außerdem (oder stattdessen) zweckmäßig, die Zusammenhangskomponenten mit einer laufenden Nummer, einem sogenannten Label, durchzuzählen. Dann kann man zusätzliche Informationen zu jeder Komponente (beispielsweise deren Größe) einfach in einem Array speichern, das über die Labels indexiert wird. Die folgende Version der Tiefensuche bestimmt sowohl die Anker als auch die Labels für jeden Knoten:

def connectedComponents(graph):
anchors = [None] * len(graph) # property map für Anker jedes Knotens
labels = [None] * len(graph) # property map für Label jedes Knotens

def visit(node, anchor):
"""anchor ist der Anker der aktuellen ZK"""
if anchors[node] is None: # wenn node noch nicht besucht wurde:
anchors[node] = anchor # setze seinen Anker
labels[node] = labels[anchor] # und sein Label
for neighbor in graph[node]: # und besuche die Nachbarn
visit(neighbor, anchor)

current_label = 0 # Zählung der ZK beginnt bei 0
for node in xrange(len(graph)):
if anchors[node] is None: # Anker noch nicht bekannt => neue ZK gefunden
labels[node] = current_label # Label des Ankers setzen
visit(node, node) # Knoten der neuen ZK rekursiv suchen
current_label += 1 # Label für die nächste ZK hochzählen
return anchors, labels
Interessant ist hier die Schleife über alle Knoten des Graphen am Ende des Algorithmus, die bei den bisherigen Versionen der Tiefensuche nicht vorhanden war. Um ihre Funktionsweise zu verstehen, nehmen wir für den Moment an, dass der Graph zusammenhängend ist. Dann findet diese Schleife den ersten Knoten des Graphen und führt die Tiefensuche mit diesem Knoten als Startknoten aus. Sobald die Rekursion zurückkehrt, sind alle Knoten des Graphen besucht (weil der Graph ja zusammenhängend war), so dass die Schleife alle weiteren Knoten überspringt (die if-Anweisung liefert für keinen weiteren Knoten True). Bei unzusammenhängenden Graphen dagegen erreicht die Tiefensuche nur die Knoten derselben Komponente, die im weiteren Verlauf der Schleife übersprungen werden. Findet die if-Anweisung jetzt einen noch nicht besuchten Knoten, muss dieser folglich in einer neuen Komponente liegen. Wir verwenden diesen Knoten als Anker und bestimmen die übrigen Knoten dieser Komponente wiederum mit Tiefensuche.

* Beispiel: ... under construction 

Man erkennt, dass die Tiefensuche nach dem Anlagerungsprinzip vorgeht: Beginnend vom einem Startknoten (dem Anker) werden die Knoten der aktuellen Komponente nach und nach an den Tiefensuchbaum angehangen. Erst, wenn nichts mehr angelagert werden kann, geht der Algorithmus zur nächsten Komponente über.

==== Lösung mittels Union-Find-Algorithmus ====

Im Gegensatz zum Anlagerungsprinzip sucht der Union-Find-Algorithmus die Zusammenhangskomponenten mit dem Verschmelzungsprinzip: Eingangs wird jeder Knoten als ein Teilgraph für sich betrachtet. Dann iteriert man über alle Kanten und verbindet deren Endknoten jeweils zu einem gemeinsamen Teilgraphen (falls die beiden Enden einer Kante bereits im selben Teilgraphen liegen, wird diese Kante ignoriert). Solange noch Kanten vorhanden sind, werden dadurch immer wieder Teilgraphen in größere Teilgraphen verschmolzen. Am Ende bleiben die maximalen zusammenhängenden Teilgraphen (also gerade die Zusammenhangskomponenten) übrig. Dieser Algorithmus kommt ohne Tiefensuche aus und ist daher in der Praxis oft schneller, allerdings auch etwas komplizierter zu implementieren.

Der Schlüssel des Algorithmus ist eine Funktion <tt>findAnchor()</tt>, die zu jedem Knoten den aktuellen Anker sucht. Der Anker existiert immer, da jeder Knoten von Anfang an zu einem Teilgraphen gehört (anfangs ist jeder Teilgraph trivial und besteht nur aus dem Knoten selbst). Die Verschmelzung wird realisiert, indem der Anker des einen Teilgraphen seine Rolle verliert und stattdessen der Anker des anderen Teilgraphen eingesetzt wird.

Zur Verwaltung der Anker verwenden wir wieder eine property map <tt>anchors</tt> mit der Konvention, dass die Anker auf sich selbst verweisen. Es wäre jedoch zu teuer, wenn man bei jeder Verschmelzung alle Anker-Einträge der beteiligten Knoten aktualisieren müsste, da jeder Knoten im Laufe des Algorithmus mehrmals seinen Anker wechseln kann. Statt dessen definiert man Anker rekursiv: Verweist ein Knoten auf einen Anker, der mittlerweile diese Rolle verloren hat, folgt man dem Verweis von diesem Knoten (dem ehemaligen Anker) weiter, bis man einen tatsächlichen Anker gefunden hat - erkennbar daran, dass er auf sich selbst verweist. Diese Suchfunktion kann folgendermassen implementiert werden:

def findAnchor(anchors, node):
while node != anchors[node]: # wenn node kein Anker ist
node = anchors[node] # ... verfolge die Ankerkette weiter
return node

Allerdings kann diese Kette im Laufe vieler Verschmelzungen sehr lang werden, so dass das Verfolgen der Kette teuer wird. Man vermeidet dies durch die sogenannte Pfadkompression: Immer, wenn man den Anker gefunden hat, aktualisiert man den Eintrag am Anfang der Kette. Die Funktion <tt>findAnchor()</tt> wird dadurch nur wenig komplizierter:

def findAnchor(anchors, node):
start = node # wir merken uns den Anfang der Kette
while node != anchors[node]: # wenn node kein Anker ist
node = anchors[node] # ... verfolge die Ankerkette weiter
anchors[start] = node # Pfadkompression: aktualisiere den Eintrag am Anfang der Kette
return node

Man kann zeigen, dass die Ankersuche mit Pfadkompression zu einer fast konstanten amortisierten Laufzeit pro Aufruf führt.

Um mit jeder Kante des (ungerichteten) Graphen nur maximal einmal eine Verschmelzung durchzuführen, betrachten wir jede Kante nur in der Richtung von der kleineren zur größeren Knotennummer, die umgekehrte Richtung wird ignoriert. Außerdem ist es zweckmäßig, bei jeder Verschmelzung denjenigen Anker mit der kleineren Knotennummer als neuen Anker zu übernehmen. Dann gilt für jede Zusammenhangskomponente, dass gerade der Knoten mit der kleinsten Knotennummer der Anker ist (genau wie bei der Lösung mittels Tiefensuche), was die weitere Analyse vereinfacht, z.B. die Zuordnung der Labels zu den Komponenten am Ende des Algorithmus.

def unionFindConnectedComponents(graph):
anchors = range(len(graph)) # Initialisierung der property map: jeder Knoten ist sein eigener Anker

for node in xrange(len(graph)): # iteriere über alle Knoten
for neighbor in graph[node]: # ... und über deren ausgehende Kanten
if neighbor < node: # ignoriere Kanten, die in falscher Richtung verlaufen
continue
# hier landen wir für jede Kante des Graphen genau einmal
a1 = findAnchor(anchors, node) # finde Anker ...
a2 = findAnchor(anchors, neighbor) # ... der beiden Endknoten
if a1 < a2: # Verschmelze die beiden Teilgraphen
anchors[a2] = a1 # (verwende den kleineren der beiden Anker als Anker des
elif a2 < a1: # entstehenden Teilgraphen. Falls node und neighbor
anchors[a1] = a2 # den gleichen Anker haben, waren sie bereits im gleichen
# Teilgraphen, und es passiert hier nichts.)
# Bestimme jetzt noch die Labels der Komponenten
labels = [None]*len(graph) # Initialisierung der property map für Labels
current_label = 0 # die Zählung beginnt bei 0
for node in xrange(len(graph)):
a = findAnchor(anchors, node) # wegen der Pfadkompression zeigt jeder Knoten jetzt direkt auf seinen Anker
if a == node: # node ist ein Anker
labels[a] = current_label # => beginne eine neue Komponente
current_label += 1 # und zähle Label für die nächste ZK hoch
else:
labels[node] = labels[a] # node ist kein Anker => setzte das Label des Ankers
# (wir wissen, dass labels[a] bereits gesetzt ist, weil
# der Anker immer der Knoten mit der kleinsten Nummer ist)
return anchors, labels

* Beispiel: ... under construction

== Kürzeste Wege (Pfade) ==

Eine weitere grundlegende Aufgabe in Graphen ist die Bestimmung eines kürzesten Weges zwischen zwei gegebenen Knoten. Dies hat offensichtliche Anwendungen bei Routenplanern und Navigationssystemen und ist darüber hinaus wichtiger Bestandteil anderer Algorithmen, z.B. bei der Berechnung eines maximalen Flusses mit der [http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm Methode von Edmonds und Karp].

=== Kürzeste Wege in ungewichteten Graphen mittels Breitensuche ===

Im Fall eines ungewichteten Graphen ist die Länge eines Weges einfach durch die Anzahl der durchlaufenen Kanten definiert. Daraus folgt, dass kürzeste Pfade mit einer leicht angepassten Version der Breitensuche gefunden werden können: Aufgrund des first in-first out-Verhaltens der Queue betrachtet die Breitensuche alle (erreichbaren) Knoten in der Reihenfolge ihres Abstandes vom Startknoten. Wenn wir den Zielknoten zum ersten Mal erreichen, und der gerade gefundene Weg vom Start zum Ziel hat die Länge L, muss dies der kürzeste Weg sein: Alle möglichen Wege der Länge L' < L hat die Breitensuche ja bereits betrachtet, ohne dass dabei der Zielknoten erreicht wurde. Daraus folgt übrigens eine allgemeine Eigenschaft aller Algorithmen für kürzeste Wege: Wenn der kürzeste Weg vom Start zum Ziel die Länge L hat, finden diese Algorithmen als Nebenprodukt auch die kürzesten Wege zu allen Knoten, für die L' < L gilt.

Um den Algorithmus zu implementieren, passen wir die Breitensuche so an, dass anstelle der property map <tt>visited</tt> eine property map <tt>parents</tt> verwendet wird, die für jeden besuchten Knoten den Vaterknoten im Breitensuchbaum speichert. Durch Rückverfolgen der <tt>parent</tt>-Kette können wir den Pfad vom Ziel zum Start rekonstruieren, und durch Umdrehen der Reihenfolge erhalten wir den gesuchten Pfad vom Start zum Ziel. Sobald der Zielknoten erreicht wurde, können wir die Breitensuche abbrechen (<tt>break</tt>-Befehl in der ersten <tt>while</tt>-Schleife). Falls der gegebene Graph unzusammenhängend ist, kann es passieren, dass gar kein Weg gefunden wird, weil Start und Ziel in verschiedenen Zusammenhangskomponenten liegen. Dies erkennen wir daran, dass die Breitensuche beendet wurde, ohne den Zielknoten zu besuchen. Dann gibt die Funktion statt eines Pfades dern Wert <tt>None</tt> zurück:

from collections import deque

def shortestPath(graph, startnode, destination):
parents = [None]*len(graph) # Registriere für jeden Knoten den Vaterknoten im Breitensuchbaum
parents[startnode] = startnode # startnode ist die Wurzel des Baums => verweist auf sich selbst

q = deque() # Queue für die zu besuchenden Knoten
q.append(startnode) # Startknoten in die Queue einfügen

while len(q) > 0: # Solange es noch unbesuchte Knoten gibt
node = q.popleft() # Knoten aus der Queue nehmen (first in - first out)
if node == destination: # Zielknoten erreicht
break # => Suche beenden
for neighbor in graph[node]: # Besuche die Nachbarn von node
if parents[neighbor] is None: # aber nur, wenn sie noch nicht besucht wurden
parents[neighbor] = node # setze node als Vaterknoten
q.append(neighbor) # und füge neighbor in die Queue ein

if parents[destination] is None: # Breitensuche wurde beendet ohne den Zielknoten zu besuchen
return None # => kein Pfad gefunden (unzusammenhängender Graph)

# Pfad durch die parents-Kette zurückverfolgen und speichern
path = [destination]
while path[-1] != startnode:
path.append(parents[path[-1]])
path.reverse() # Reihenfolge umdrehen (Ziel => Start wird zu Start => Ziel)
return path # gefundenen Pfad zurückgeben

=== Gewichtete Graphen ===

Das Problem der Suche nach kürzesten Wegen wird wesentlich interessanter und realistischer, wenn wir zu gewichteten Graphen übergehen:

; Definition - kantengewichteter Graph
: Jeder Kante (s,t) des Graphen ist eine reelle oder natürliche Zahl wst zugeordnet, die üblicherweise als ''Kantengewicht'' bezeichnet wird.

; Definition - knotengewichteter Graph
: Jedem Knoten v des Graphen ist eine reelle oder natürliche Zahl wv zugeordnet, die üblicherweise als ''Knotengewicht'' bezeichnet wird.

Je nach Anwendung benötigt man Knoten- oder Kantengewichte oder auch beides zugleich. Wir beschränken uns in der Vorlesung auf kantengewichtete Graphen. Beispiele für die Informationen, die man durch Kantengewichte ausdrücken kann, sind
* wenn die Knoten Orte sind: Abstand von Anfangs- und Endknoten jeder Kante (z.B. Luftline oder Straßenentfernung), Fahrzeit zwischen den Orten
* wenn der Knoten ein Rohrnetzwerk beschreibt: Durchflusskapazität der einzelnen Rohre (für max-Flussprobleme), analog bei elektrischen Netzwerken: elektrischer Widerstand
* wenn die Knoten Währungen repräsentieren, können deren Wechselkurse durch Kantengewichte angegeben werden.
Bei einigen Beispielen ergeben sich unterschiedliche Kantengewichte, wenn eine Kante von s nach t anstatt von t nach s durchlaufen wird. Beispielsweise können sich die Fahrzeiten erheblich unterscheiden, wenn es in einer Richtung bergauf, in der anderen bergab geht, obwohl die Entfernung in beiden Fällen gleich ist. Hier ergibt sich natürlicherweise ein gerichteter Graph. In anderen Beispielen (z.B. bei Luftlinienentfernungen, in guter Näherung auch bei Straßenentfernungen) sind die Gewichte von der Richtung unabhängig, so dass wir ungerichtete Graphen verwenden können.

Die Repräsentation der Kantengewichte im Programm richtet sich nach der Repräsentation des Graphen selbst. Am einfachsten ist wiederum die Adjazenzmatrix, die aber nur für dichte Graphen (<math>E = O(V^2)</math>, mit E als Anzahl der Kanten und V als Anzahl der Knoten) effizient ist. Bei gewichteten Graphen gibt das Matrixelement aij das Gewicht der Kante i ⇒ j (wobei aij = 0 gesetzt wird, wenn diese Kante nicht existiert). Wie zuvor gilt für ungerichtete Graphen aij = aji (symmetrische Matrix), während dies für gerichtete Graphen nicht gelten muss.

Bei Graphen in Adjazenzlistendarstellung hat es sich bewährt, die Gewichte in einer property map zu speichern. Weiter oben haben wir bereits property maps für Knoteneigenschaften (z.B. <tt>visited</tt> und <tt>anchors</tt>) gesehen. Property maps für Kanten funktionieren ganz analog, allerdings muss man jetzt Paare von Knoten (nämlich Anfangs- und Endknoten der Kante) als Schlüssel verwenden und die Daten entsprechend in einem assoziativen Array ablegen:
w = weights[(i,j)] # Zugriff auf das Gewicht der Kante i ⇒ j
Alternativ könnte man auch die Graph-Datenstruktur selbst erweitern, aber dies ist weniger zu empfehlen, weil jeder Algorithmus andere Erwiterungen benötigt und damit die Datenstruktur sehr unübersichtlich würde.

Der kürzeste Weg ist nun definiert als der Weg, bei dem die Summe der Kantengewichte minimal ist:
;Definition - Problem des kürzesten Weges
: Sei P die Menge aller Wege von u nach v, und <math>p \in P</math> einer dieser Wege. Wenn der Grpah einfach ist (es also keine Mehrfachkanten zwischen denselben Knoten und keine Schleifen gibt), ist der Weg p durch die Folge der besuchten Knoten eindeutig bestimmt:
: <math>p : \ \ u = x_0 \rightarrow x_1 \rightarrow x_2 \rightarrow ... \rightarrow v = x_{n_p}</math>
:wo <math>n_p</math> die Anzahl der Kanten im Weg p ist. Seine Kosten Wp ergeben sich als Summer der Gewichte der einzelnen Kanten
: <math>W_p = \sum_{k=1}^{n_p} w_{x_{k-1}x_k}</math>
: und ein kürzester Weg <math>p^* \in P</math> ist ein Weg mit minimalen Kosten
: <math>p^* = \textrm{argmin}_{p\in P}\ \ W_p</math>
: Das Problem des kürzesten Weges besteht darin, einen optimalen Weg p* zwischen gegebenen Knoten u und v zu finden.
Die Lösung dieses Problems hängt davon ab, ob alle Kantengewichte positiv sind, oder ob es auch negative Kantengewichte gibt. In letzeren Fall ist es möglich, durch eine Verlängerung des Weges die Kosten zu redizieren, während sich im ersteren Fall die Kosten immer erhöhen, wenn man den Weg verlängert.

Negative Gewichte treten z.B. bei den Währungsgraphen auf. Auf den ersten Blick entsprechen diese Graphen nicht den Anforderungen an das Problem des kürzesten Weges, weil Wechselkurse miteinander (und mit Geldbeträgen) multipliziert anstatt addiert werden. Man beseitigt diese Schwierigkeit aber leicht, indem man die Logarithmen der Wechselkurse als Kantengewichte verwendet, wodurch sich die Multiplikation in eine Addition der Logarithmen verwandelt. Wechselkurse < 1 führen nun zu negativen Gewichten.

Interessant werden negative Gewichte vor allem in Graphen mit Zyklen. Dann kann es nämlich passieren, dass die Gesamtkosten eines Zyklus ebenfalls negativ sind. Jeder Weg, der den Zyklus enthält, hat dann Kosten von <math>-\infty</math>, weil man den Zyklus beliebig oft durchlaufen und dadurch die Gesamtkosten immer weiter verkleinern kann:

/\ 1. Durchlauf: Kosten -1
1 / \ -4 2. Durchlauf: Kosten -2
/____\ etc.
2

Um hier nicht in einer Endlosschleife zu landen, benötigt man spezielle Algorithmen, die mit dieser Situation umgehen können. Der [http://de.wikipedia.org/wiki/Bellman-Ford-Algorithmus Algorithmus von Bellmann und Ford] beispielsweise bricht die Suche nach dem kürzesten Weg ab, sobald er einen negativen Zyklus entdeckt, aber andernfalls kann er negative Gewichte problemlos verarbeiten.

Die Detektion negativer Zyklen hat wiederum eine interessante Anwendung bei Währungsgraphen: Ein Zyklus bedeutet hier, dass man Geld über mehrere Stufen von einer Währung in die nächste und am Schluß wieder in die Originalwährung umtauscht, und ein negativer Zyklus führt dazu, dass man am Ende mehr Geld besitzt als am Anfang (damit negative Zyklen wirklich einen Gewinn bedeuten und keinen Verlust, müssen die Wechselkurse vor der Logarithmierung in [http://de.wikipedia.org/wiki/Wechselkurs#Nominaler_Wechselkurs Preisnotierung] angegeben sein). Bei Privatpersonen ist dies ausgeschlossen, weil die Umtauschgebühren den möglichen Gewinn mehr als aufzehren. Banken mit direktem weltweitem Börsenzugang hingegen unternehmen große Anstrengungen, um solche negativen Zyklen möglichst schnell (nämlich vor der Konkurrenz) zu entdecken und auszunutzen. Diese Geschäftsmethode bezeichnet man als [http://de.wikipedia.org/wiki/Arbitrage Arbitrage] und die Existenz eines negativen Zyklus als Arbitragegelegenheit. Durch die Kursschwankungen (und durch die ausgleichende Wirkung der Arbitragegeschäfte selbst) existieren die Arbitragegelegenheiten nur für kurze Zeit, und ihre Detektion erfordert leistungsfähige Echtzeitalgorithmen.

In dieser Vorlesung beschränken wir uns hingegen auf Graphen mit ausschließlich positiven Gewichten. In diesem Fall ist der Algorithmus von Dijkstra die Methode der Wahl, weil er wesentlich schneller arbeitet als der Bellmann-Ford-Algorithmus.

=== Algorithmus von Dijkstra ===

==== Edsger Wybe Dijkstra ====

geb. 11. Mai 1930 in Rotterdam

ges. 06. August 2002

Dijkstra war ein niederländischer Informatiker und Wegbereiter der strukturierten Programmierung. 1972 erhielt er für seine Leistung in der Technik und Kunst der Programmiersprachen den Turing Award, der jährlich von der Association for Computing Machinery (ACM) an Personen verliehen wird, die sich besonders um die Entwicklung der Informatik verdient gemacht haben. Zu seinen Beiträgen zur Informatik gehören unter anderem der Dijkstra-Algorithmus zur Berechnung des kürzesten Weges in einem Graphen sowie eine Abhandlung über den go-to-Befehl und warum er nicht benutzt werden sollte. Der go-to-Befehl war in den 60er und 70er Jahren weit verbreitet, führte aber zu Spaghetti-Code. In seinem berühmten Paper "A Case against the GO TO Statement"[http://www.cs.utexas.edu/users/EWD/ewd02xx/EWD215.PDF], das als Brief mit dem Titel "Go-to statement considered harmful" veröffentlicht wurde, argumentiert Dijkstra, dass es umso schwieriger ist, dem Quellcode eines Programmes zu folgen, je mehr go-to-Befehle darin enthalten sind und zeigt, dass man auch ohne diesen Befehl gute Programme schreiben kann.

==== Algorithmus ====

Der Dijkstra-Algorithmus für kürzeste Wege ist dem oben vorgestellten Algorithmus <tt>shortestPath()</tt> auf der Basis von Breitensuche sehr ähnlich. Insbesondere gilt auch hier, dass neben dem kürzesten Weg vom Start zum Ziel auch alle kürzesten Wege gefunden werden, deren Endknoten dem Start näher sind als der Zielknoten. Aufgrund der Kantengewichte gibt es aber einen wichtigen Unterschied: Der erste gefundene Weg zu einem Knoten ist nicht mehr notwendigerweise der kürzeste. Wir bestimmen deshalb für jeden Knoten mehrere Kandidatenwege und verwenden eine Prioritätswarteschlange (statt einer einfachen First in - First out - Queue), um diese Wege nach ihrer Länge zu sortieren. Die Kandidatenwege für einen gegebenen Knoten werden unterschieden, indem wir auch den Vorgängerknoten im jeweiligen Weg speichern. Wenn ein Knoten erstmals an die Spitze der Prioritätswarteschlange gelangt, haben wir den kürzesten Weg zu diesem Knoten gefunden (das wird weiter unten formal bewiesen), und der Vorgänger des Knotens in diesem Weg wird zu seinem Vaterknoten. Erscheint derselbe Knoten später nochmals an der Spitze der Prioritätswarteschlange, handelt es sich um einen Kandidatenweg, der sich nicht als kürzester erwiesen hat und deshalb ignoriert werden kann. Wir erkennen dies leicht daran, dass der Vaterknoten in der property map <tt>parents</tt> bereits gesetzt ist.

Eine geeignete Datenstruktur für die Prioritätswarteschlange wird durch das Python-Modul [http://docs.python.org/library/heapq.html heapq] realisiert. Es verwendet ein normales Pythonarray als unterliegende Repräsentation für einen Heap und stellt effiziente <tt>heappush</tt> und <tt>heappop</tt>-Funktionen zur Verfügung. Dies entspricht genau unserer Vorgehensweise im Kapitel [[Prioritätswarteschlangen]]. Als Datenelement erwartet die Funktion <tt>heappush</tt> ein Tupel, dessen erstes Element die Priorität sein muss. Die übrigen Elemente des Tupels (und damit auch deren Anzahl) können je nach Anwendung frei festgelegt werden. Wir legen fest, dass das zweite Element den Endknoten des betrachteten Weges und das dritte den Vorgängerknoten speichert.

Die Kantengewichte werden dem Algorithmus in der property map <tt>weights</tt> übergeben:

<code python>
import heapq # heapq implementiert die Funktionen für Heaps

def dijkstra(graph, weights, startnode, destination):
parents = [None]*len(graph) # registriere für jeden Knoten den Vaterknoten im Pfadbaum

q = [] # Array q wird als Heap verwendet
heapq.heappush(q, (0.0, startnode, startnode)) # Startknoten in Heap einfügen

while len(q) > 0: # solange es noch Knoten im Heap gibt:
length, node, predecessor = heapq.heappop(q) # Knoten aus dem Heap nehmen
if parents[node] is not None: # parent ist schon gesetzt => es gab einen anderen, kürzeren Weg
continue # => wir können diesen Weg ignorieren
parents[node] = predecessor # parent setzen
if node == destination: # Zielknoten erreicht
break # => Suche beenden
for neighbor in graph[node]: # die Nachbarn von node besuchen,
if parents[neighbor] is None: # aber nur, wenn ihr kürzester Weg noch nicht bekannt ist
newLength = length + weights[(node,neighbor)] # berechne Pfadlänge zu neighbor
heapq.heappush(q, (newLength, neighbor, node)) # und füge neighbor in den Heap ein

if parents[destination] is None: # Suche wurde beendet ohne den Zielknoten zu besuchen
return None, None # => kein Pfad gefunden (unzusammenhängender Graph)

# Pfad durch die parents-Kette zurückverfolgen und speichern
path = [destination]
while path[-1] != startnode:
path.append(parents[path[-1]])
path.reverse() # Reihenfolge umdrehen (Ziel => Start wird zu Start => Ziel)
return path, length # gefundenen Pfad und dessen Länge zurückgeben
</code>
Die wesentlichen Unterschiede zur Breitensuche sind im Code rot markiert: Anstelle der Queue verwenden wir jetzt einen Heap, und der Startknoten wird mit Pfadlänge 0 als erstes eingefügt. In der Schleife <tt>while len(q) > 0:</tt> wird jeweils der Knoten <tt>node</tt> mit der aktuell kürzesten Pfadlänge aus dem Heap entfernt. Die Pfadlänge vom Start zu diesem Knoten wird in der Variable <tt>length</tt> gespeichert, sein Vorgänger in der Variable <tt>predecessor</tt>. Wenn der aktuelle Weg nicht der kürzeste ist (<tt>parents[node]</tt> war bereits gesetzt), wird dieser Weg ignoriert. Andernfalls werden die property map <tt>parents</tt> aktualisiert und die Nachbarn von <tt>node</tt> besucht. Beim Scannen der Nachbarn berechnen wir zunächst die Länge <tt>newLength</tt> das Weges <tt>startnode => node => neighbor</tt> als Summe von <tt>length</tt> und dem Gewicht der Kante <tt>(node, neighbode)</tt>. Diese Länge wird beim Einfügen des Nachbarknotens in den Heap zur Priorität des aktuellen Weges.

Die wichtigsten Prinzipien des Dijkstra-Algorithmus noch einmal im Überblick:
* Der Dijkstra-Algorithmus ist Breitensuche mit Prioritätswarteschlange (Heap) statt einer einfache Warteschlange (Queue).
* Die Prioritätswarteschlange speichert alle Wege, die bereits gefunden worden sind und ordnet sie aufsteigend nach ihrer Länge.
* Das Sortieren (und damit der ganze Algorithmus) funktioniert nur mit positiven Kantengewichten korrekt.
* Da ein Knoten auf mehreren Wegen erreichbar sein kann, kann er auch mehrmals im Heap sein.
* Wenn ein Knoten erstmals aus der Prioritätswarteschlange entnommen wird, ist der gefundene Weg der kürzeste zu diesem Knoten. Andernfalls wird der Weg ignoriert.
* Wenn der Knoten <tt>destination</tt> aus dem Heap entnommen wird, ist der kürzeste Weg von Start nach Ziel gefunden, und die Suche kann beendet werden.
In unserer Implementation können, wie gesagt, mehrere Wege zum selben Knoten gleichzeitig in der Prioritätswarteschlange sein. Im Prinzip wäre es auch möglich, immer nur den besten zur Zeit bekannten Weg zu jedem Enknoten in der Prioritätswarteschlange zu halten - sobald ein besserer Kandidat gefunden wird, ersetzt er den bisherigen Kandidaten, anstatt zusätzlich eingefügt zu werden. Dies erfordert aber eine wesentlich kompliziertere Prioritätswarteschlange, die eine effiziente <tt>updatePriority</tt>-Funktion anbietet, ohne dass dadurch eine signifikante Beschleunigung erreicht wird. Deshalb verfolgen wir diesen Ansatz nicht.

==== Beispiel ====

under construction

[[Image:Bsp.jpg]]

==== Komplexität von Dijkstra ====

Zur Analyse der Komplexität nehmen wir an, dass der Graph V Knoten und E Kanten hat. Die Initialisierung der property map <tt>parents</tt> am Anfang der Funktion hat offensichtlich Komplexität O(V), weil Speicher für V Knoten allokiert wird. Der Code am Ende der Funktion, der aus der property map <tt>parents</tt> den Pfad extrahiert, hat ebenfalls die Komplexität O(V), weil der Pfad im ungünstigen Fall sämtliche Knoten des Graphen umfasst. Beides wird durch die Komplexität der Hauptschleife dominiert, zu deren Analyse wir den folgenden Codeausschnitt genauer anschauen wollen:

while len(q) > 0:
... # 1
if parents[node] is not None:
continue
parents[node] = predecessor
... # 2
Wir erkennen, dass der Codeabschnitt <tt># 2</tt> für jeden Knoten höchstens einmal erreicht werden kann: Da <tt>parents[node]</tt> beim ersten Durchlauf gesetzt wird, kann die <tt>if</tt>-Abfrage beim gleichen Knoten nie wieder <tt>False</tt> liefern, und das nachfolgende <tt>continue</tt> bewirkt, dass der Abschnitt <tt># 2</tt> dann übersprungen wird. Man sagt auch, dass jeder Knoten höchstens einmal expandiert wird, auch wenn er mehrmals im Heap war.

Der Codeabschnitt <tt># 2</tt> selbst enthält eine Schleife über alle ausgehenden Kanten des Knotens <tt>node</tt>. Im ungünstigsten Fall iterieren wir bei allen Knoten über alle ausgehenden Kanten, aber das sind gerade alle Kanten des Graphen je einmal in den beiden möglichen Richtungen. Die Funktion <tt>heappush</tt> wird sogar höchstens E Mal aufgerufen, weil eine Kante nur in den Heap eingefügt wird, wenn der kürzeste Weg der jeweiligen Endknotens noch nicht bekannt ist (siehe die <tt>if</tt>-Abfrage in der <tt>for</tt>-Schleife), und das ist nur ein einer Richtung möglich. Dies hat zwei Konsequenzen:
* Die Schleife <tt>while len(q) > 0:</tt> wird nur so oft ausgeführt, wie Elemente im Heap sind, also höchstens E Mal. Das gleiche gilt für den Codeabschnitt <tt># 1</tt>, der das <tt>heappop</tt> enthält.
* Die Operationen <tt>heappush</tt> und <tt>heappop</tt> haben logarithmische Komplexität in der Größe des Heaps, sind also in <math>O(\log\,E)</math>. In einfachen Graphen gilt aber <math>E = O(V^2)</math>, so dass sich die Komplexität der Heapoperationen vereinfacht zu <math>O(\log\,E)=O(\log\,V^2)=O(2\log\,V)=O(\log\,V)</math>.
Zusammenfassend gilt: <tt>heappush</tt> und <tt>heappop</tt> werden maximal E Mal aufgerufen und haben eine Komplexität in <math>O(\log\,V)</math>. Folglich hat der Algorithmus von Dijkstra die Komplexität:
:<math>O(E\,\log\,V)</math>

==== Vergleich mit Breitensuche und Tiefensuche ====

Der Dijkstra-Algorithmus ist eng mit der Breiten- und Tiefensuche verwandt - man kann diese Algorithmen aus dem Dijkstra-Algorithmus gewinnen, indem man einfach die Regel zur Festlegung der Prioritäten ändert. Anstelle der Länge des Pfades verwenden wir als Priorität den Wert eine Zählvariable <tt>count</tt>, die nach jeder Einfügung in den Heap (also nach jedem Aufruf von <tt>heappush</tt>) aktualisiert wird. Zählen wir die Variable hoch, haben die zuerst eingefügten Kanten die höchste Priorität, der Heap verhält sich also wie eine Queue (First in-First out), und wir erhalten eine Breitensuche. Zählen wir die Variable hingegen (von E beginnend) herunter, haben die zuletzt eingefügten Kanten höchste Priorität. Der Heap verhält sich dann wie ein Stack (Last in-First out), und wir bekommen Tiefensuche. Statt eines Heaps plus Zählvariable kann man jetzt natürlich direkt eine Queue bzw. einen Stack verwenden. Dadurch fällt der Aufwand <math>O(\log\,V)</math> für die Heapoperationen weg und wird durch die effizienten O(1)-Operationen von Queue bzw. Stack ersetzt. Damit erhalten wir für Breiten- und Tiefensuche die schon bekannte Komplexität O(E).

==== Korrektheit von Dijkstra ====

Wir beweisen mittels vollständiger Induktion die Schleifen-Invariante: Falls <tt>parents[node]</tt> gesetzt (also ungleich <tt>None</tt>) ist, dann liefert das Zurückverfolgen des Weges von <tt>node</tt> nach <tt>startnode</tt> den kürzesten Weg.
;Induktionsanfang: <tt>parents[startnode]</tt> ist als einziges gesetzt. Zurückverfolgen liefert den trivialen Weg <tt>[startnode]</tt>, der mit Länge 0 offensichtlich der kürzeste Pfad ist → die Bedingung ist erfüllt.
;Induktionsschritt: Wir zeigen mit einem indirektem Beweis, dass wir immer einen kürzesten Weg bekommen, wenn <tt>parents[node]</tt> gesetzt wird.
:Sei <math>S</math> = <tt>{v | parents[v] is not None}</tt> die Menge aller Knoten, von denen wir den kürzesten Weg schon kennen (Induktionsvoraussetzung), und <tt>node</tt> der Knoten, der sich gerade an der Spitze des Heaps befindet. Dann ist <tt>predecessor</tt> der Vorgänger von <tt>node</tt> im aktuellen Weg, und es muss <tt>predecessor</tt><math>\in S</math> gelten, weil die Nachbarn von <tt>predecessor</tt> (und damit auch der aktuelle <tt>node</tt>) erst in den Heap eingefügt werden, wenn der kürzeste Weg für <tt>predecessor</tt> gefunden wurde. Man beachte auch, dass alle Knoten, die noch nicht in <math>S</math> enthalten sind, weiter vom Start entfernt sind als alle Knoten in <math>S</math>, weil alle neu in den Heap eingefügten Wege länger sind als der kürzeste Weg des jeweiligen Vorgängers.
:Der indirekte Beweis nimmt jetzt an, dass der Weg <tt>node</tt> → <tt>predecessor</tt> → <tt>startnode</tt> nicht der kürzeste Weg ist. Dann muss es einen anderen, kürzeren Weg <tt>node</tt> → <tt>x</tt> → <tt>startnode</tt> geben. Für den Vorgänger <tt>x</tt> in diesem Weg unterscheiden wir zwei Fälle:
:* <tt>x</tt><math>\in S</math>: In diesem Fall ist die Länge des Weges <tt>node</tt> → <tt>x</tt> → <tt>startnode</tt> bereits bekannt, und dieser Weg ist in der Prioritätswarteschlange enthalten. Dann kann er aber nicht der kürzeste sein, denn an der Spitze der Warteschlange war nach Voraussetzung der Weg <tt>node</tt> → <tt>predecessor</tt> → <tt>startnode</tt>.
:* <tt>x</tt><math>\notin S</math>: Die Kosten des Weges <tt>node</tt> → <tt>x</tt> → <tt>startnode</tt> berechnen sich als <tt>Kosten(x → startnode) + weight[(x, node)]</tt>, und die Kosten des Weges <tt>node</tt> → <tt>predecessor</tt> → <tt>startnode</tt> sind analog <tt>Kosten(predecessor → startnode) + weight[(predecessor, node)]</tt>. Aufgrund der Induktionsvoraussetzung gilt aber <tt>predecessor</tt><math>\in S</math>, und somit <tt>Kosten(predecessor → startnode) < Kosten(x → startnode)</tt>, weil <tt>x</tt> andernfalls vor <tt>predecessor</tt> an der Spitze des Heaps gewesen wäre, was mit der Annahme <tt>x</tt><math>\notin S</math> unverträglich ist. Damit der Weg <tt>node</tt> → <tt>x</tt> → <tt>startnode</tt> trotzdem der kürzeste Weg sein kann, müsste <tt>Kosten(x → startnode) < Kosten(node → startnode)</tt> gelten, denn durch die Kante <tt>(x, node)</tt> kommen ja noch Kosten hinzu. Das wäre aber nur möglich, wenn der Knoten <tt>x</tt> vor dem Knoten <tt>node</tt> an die Spitze des Heaps gelangt, im Widerspruch zur Annahme, dass <tt>node</tt> sich gerade an der Spitze des Heaps befindet. Somit kann die Behauptung, dass der Weg <tt>node</tt> → <tt>x</tt> → <tt>startnode</tt> der kürzeste Weg ist, nicht stimmen.
In beiden Fällen erhalten wir einen Widerspruch, und die Behauptung ist somit bewiesen. Da die Invariante insbesondere für den Weg zum Zielknoten <tt>destination</tt> erfüllt ist, folgt daraus auch die Korrektheit des Algorithmus von Dijkstra.

=== A*-Algorithmus - Wie kann man Dijkstra noch verbessern? ===

Eine wichtige Eigenschaft des Dijkstra-Algorithmus ist, dass neben dem kürzesten Weg vom Start zum Ziel auch die kürzesten Wege zu allen Knoten berechnet werden, die näher am Startknoten liegen als das Ziel, obwohl uns diese Wege gar nicht interessieren. Sucht man beispielsweise in einem Graphen mit den Straßenverbindungen in Deutschland den kürzesten Weg von Frankfurt (Main) nach Dresden (ca. 460 km), werden auch die kürzesten Wege von Frankfurt nach Köln (190 km), Dortmund (220 km) und Stuttgart (210 km) und vielen anderen Städten gefunden. Aufgrund der geographischen Lage dieser Städte ist eigentlich von vornherein klar, dass sie mit dem kürzesten Weg nach Dresden nicht das geringste zu tun haben. Anders sieht es mit Erfurt (260 km) oder Suhl (210 km) aus - diese Städte liegen zwischen Frankfurt und Dresden und kommen deshalb als Zwischenstationen des gesuchten Weges in Frage.

Damit Dijkstra korrekt funktioniert, würde es im Prinzip ausreichen, wenn man die kürzesten Wege nur für diejenigen Knoten ausrechnet, die auf dem kürzesten Weg vom Start zum Ziel liegen, denn nur diese Knoten braucht man, um den gesuchten Weg über die <tt>parent</tt>-Kette zurückzuverfolgen. Das Problem ist nur, dass man diese Knoten erst kennt, wenn der Algorithmus fertig durchgelaufen ist. Schließt man Knoten zu früh von der Betrachtung aus, kommt am Ende möglicherweise nicht der korrekte kürzeste Weg heraus.

Der A*-Algorithmus löst dieses Dilemma mit folgender Idee: Ändere die Prioritäten für den Heap so ab, dass unwichtige Knoten nur mit geringerer Wahscheinlichkeit expandiert werden, aber stelle gleichzeitig sicher, dass alle wichtigen Knoten (also diejenigen auf dem korrekten kürzesten Weg) auf jeden Fall expandiert werden. Es zeigt sich, dass man diese Idee umsetzen kann, wenn eine Schätzung für den Restweg (also für die noch verbleibende Entfernung von jedem Knoten zum Ziel) verfügbar ist:
rest = guess(neighbor, destination)
Diese Schätzung addiert man einfach zur wahren Länge des Weges <tt>startnode → node</tt> dazu, um die verbesserte Priorität zu erhalten:
priority = newLength + guess(neighbor, destination)
(Im originalen Dijkstra-Algorithmus wird als Priorität nur <tt>newLength</tt> allein verwendet. Man beachte, dass man <tt>newLength</tt> jetzt zusätzlich im Heap speichern muss, weil man es für die Expansion des Knotens später noch benötigt.)

Damit sicher gestellt ist, dass der A*-Algorithmus immer noch die korrekten kürzesten Wege findet, darf die Schätzung den wahren Restweg niemals überschätzen. Es muss immer gelten:
0 <= guess(node, destination) <= trueDistance(node, destination)
Damit gilt insbesondere <tt>guess(destination, destination) = trueDistance(destination, destination) = 0</tt>, an der Priorität des Knotens <tt>destination</tt> ändert sich also nichts. Die Prioritäten aller anderen Knoten veschlechtern sich hingegen, weil zur bisherigen Priorität noch atwas addiert wird. Für die wichtigen Knoten auf dem kürzesten Weg vom Start nach Ziel gilt jedoch, dass deren neue Priorität immer noch besser ist als die Priorität des Zielknotens selbst. Für diese Knoten gilt nämlich
falls node auf dem kürzesten Weg von startnode nach destination liegt:
trueDistance(startnode, node) + guess(node, destination) <= trueDistance(startnode, destination)
weil der Weg von Start nach <tt>node</tt> ein Teil des kürzesten Wegs von Start nach Ziel ist und die Restschätzung die wahre Entfernung immer unterschätzt. Diese Knoten werden deshalb stets vor dem Zielknoten expandiert, so dass wir die <tt>parent</tt>-Kette immer noch korrekt zurückverfolgen können. Für alle anderen Knoten gilt idealerweise, dass die neue Priorität schlechter ist als die Priorität von <tt>destination</tt>, so dass man sich diese irrelevanten Knotenexpansionen sparen kann.

Für das Beispiel eines Straßennetzwerks bietet sich als Schätzung die Luftlinienentfernung an, weil Straßen nie kürzer sein können als die Luftlinie. Damit erreicht man in der Praxis deutliche Einsparungen. Generell gilt, dass der A*-Algorithmus im typischen Fall schneller ist als der Algorithmus von Dijkstra, aber man kann immer pathologische Fälle konstruieren, wo die Änderung der Prioritäten nichts bringt. Die Komplexität des A*-Algorithmus im ungünstigen Fall ist deshalb nach wie vor <math>O(E\,\log\,V)</math>.

=='''Minimaler Spannbaum'''==
'''(engl.: minimum spanning tree; abgekürzt: MST)'''

[[Image:Minimum_spanning_tree.png‎ |thumb|200px|right|Ein minimal aufspannender Baum verbindet alle Punkte eines Graphen bei minimaler Kantenlänge ([http://de.wikipedia.org/wiki/Spannbaum Quelle])]]

:''gegeben'': gewichteter Graph G, zusammenhängend 
:''gesucht'': Untermenge <math>E'\subseteq E</math> der Kanten, so dass die Summe der Kantengewichte <math>\sum_{e\in E'} w_e</math> minimal und der entstehende Graph G' zusammenhängend ist. 
* G' definiert immer einen Baum, denn andernfalls könnte man eine Kante weglassen und dadurch die Summe <math>\sum_{e\in E'} w_e</math> verringern, ohne dass sich am Zusammenhang von G' etwas ändert. 
* Wenn der Graph G nicht zusammenhängend ist, kann man den Spannbaum für jede Zusammenhangskomponente getrennt ausrechnen. Man erhält dann einen aufspannenden Wald.
* Der MST ist ähnlich wie der Dijkstra-Algorithmus: Dort ist ein Pfad gesucht, bei dem die Summe der Gewichte über den Pfad minimal ist. Beim MST suchen wir eine Lösung, bei der die Summe der Gewichte über den ganzen Graphen minimal ist.
* Das Problem des MST ist nahe verwandt mit der Bestimmung der Zusammenhangskomponente, z.B. über den Tiefensuchbaum. Für die Zusammenhangskomponenten genügt allerdings ein beliebiger Baum, während beim MST ein minimaler Baum gesucht ist.

=== Anwendungen ===
==== Wie verbindet man n gegebene Punkte mit möglichst kurzen Straßen (Eisenbahnen, Drähten [bei Schaltungen] usw.)?====

 
{| class="wikitable" style="text-align:center" border="0" cellpadding="5" cellspacing="0"
|MST minimale Verbindung (Abb.1)
|MST = 2 (Länge = Kantengewicht)(Abb.2)
|- valign="top"
| [[Image:mst.png]]
| [[Image:Gleichseitigesdreieck.png]]
|}
*In der Praxis: Die Festlegung, dass man nur die gegebenen Punkte verwenden darf, ist eine ziemliche starke Einschränkung.

* Wenn man sich vorstellt, es sind drei Punkte gegeben, die als gleichseitiges Dreieck angeordnet sind, dann ist der MST (siehe Abb.2, schwarz gezeichnet) und hat die Länge 2. Man kann hier die Länge als Kantengewicht verwenden.

* Wenn es erlaubt ist zusätzliche Punkte einzufügen, dann kann man in der Mitte einen neuen Punkt setzen <math>\rightarrow</math> neuer MST (siehe Abb.2, orange gezeichnet). 

* Höhe = <math>\frac{1}{2}\sqrt{3}</math>, Schwerpunkt: teilt die Höhe des Dreiecks im Verhältnis 2:1; der Abstand von obersten Punkt bis zum neu eingeführten Punkt: <math>\frac{2}{3}h = \frac{\sqrt{3}}{3}</math>, davon insgesamt 3 Stück, damit (gilt für den MST in orange eingezeichnet): MST = <math>3\left(\frac{1}{3}\right) \sqrt{3} = \sqrt{3} \approx 1,7</math><br\>

* Damit ist der MST in orange kürzer als der schwarz gezeichnete MST. <br\>
<math>\Rightarrow</math>Folgerung: MST kann kürzer werden, wenn man einen Punkt dazu nimmt.
* Umgekehrt kann der MST auch kürzer werden, wenn man einen Punkt aus dem Graphen entfernt, aber wie das Beipiel des gleichseitigen Dreiecks zeigt, ist dies nicht immer der Fall.

[[Image: bahn.png|Bahnstrecke Verbindung (Abb.3)]]

* Methode der zusätzlichen Punkteinfügung hat man früher beim Bahnstreckenbau verwendet. Durch Einführung eines Knotenpunktes kann die Streckenlänge verkürzt werden (Dreiecksungleichung).

==== Bestimmung von Datenclustern ====

[[Image:cluster.png]]

* Daten (in der Abb.: Punkte) bilden Gruppen.

* In der Abbildung hat man 2 verschiedene Messungen gemacht (als x- und y-Achse aufgetragen), bspw. Größe und Gewicht von Personen. Für jede Person i wird ein Punkt an der Koordinate (Größei, Gewichti) gezeichnet (siehe Bild a). Dies bezeichnet man als ''Scatter Plot''. Wenn bestimmte Wertkombinationen häufiger auftreten als andere, bilden sich mitunter Gruppen aus, bspw. eine Gruppe für "klein und schwer" etc.

* Durch Verbinden der Punkte mittels eines MST (siehe Abbildung (b)) sieht man, dass es kurze (innerhalb der Gruppen) und lange Kanten (zwischen den Gruppen) gibt.

* Wenn man geschickt eine Schwelle einführt und alle Kanten löscht, die länger sind als die Schwelle, dann bekommt man als Zusammenhangskomponente die einzelnen Gruppen.

=== Algorithmen ===

Genau wie bei der Bestimmung von Zusammenhangskomponenten kann man auch das MST-Problem entweder nach dem Anlagerungsprinzip oder nach dem Verschmelzungsprinzip lösen (dazu gibt es noch weitere Möglichkeiten, z.B. den [http://de.wikipedia.org/wiki/Algorithmus_von_Bor%C5%AFvka Algorithmus von Boruvka]). Der Anlagerungsalgorithmus für MST wurde zuerst von Prim beschrieben und trägt deshalb seinen Namen, der Verschmelzungsalgorithmus stammt von Kruskal. Im Vergleich zu den Algorithmen für Zusammenhangskomponenten ändert sich im wesentlichen nur die Reihenfolge, in der die Kanten betrachtet werden: Eine Prioritätswarteschlange stellt jetzt sicher, dass am Ende wirklich der Baum mit den geringstmöglichen Kosten herauskommt.

====Algorithmus von Prim====
[http://de.wikipedia.org/wiki/Algorithmus_von_Prim Wikipedia (de)]
[http://en.wikipedia.org/wiki/Prim%27s_algorithm (en)]

Der Algorithmus von Prim geht nach dem Anlagerungsprinzip vor (vgl. den Abschnitt [[Graphen_und_Graphenalgorithmen#Lösung mittels Tiefensuche|Zusammenhangskomponenten mit Tiefensuche]]): Starte an der Wurzel (ein willkürlich gewählter Knoten) und füge jeweils die günstigste Kante an die aktuellen Teillösung an, die keinen Zyklus verursacht. Die Sortierung der Kanten nach Priorität erfolgt analog zum Dijsktra-Algorithmus, aber die Definitionen, welche Kante die günstigste ist, unterscheiden sich. Die Konvention für die Bedeutung der Elemente des Heaps ist ebenfalls identisch: ein Tupel mit <tt>(priority, node, predecessor)</tt>. Die folgende Implementation verdeutlicht sehr schön die Ähnlichkeit der beiden Algorithmen. Das Ergebnis wird als property map <tt>parents</tt> zurückgegeben, in der für jeden Knoten sein Vorgänger im MST steht, wobei die Wurzel wie üblich auf sich selbst verweist.

import heapq

def prim(graph, weights): # Kantengewichte wie bei Dijkstra als property map
sum = 0.0 # wird später das Gewicht des Spannbaums sein
start = 0 # Knoten 0 wird willkürlich als Wurzel gewählt

parents = [None]*len(graph) # property map, die den resultierenden Baum kodiert
parents[start] = start # Wurzel zeigt auf sich selbst

heap = [] # Heap für die Kanten des Graphen
for neighbor in graph[start]: # besuche die Nachbarn von start
heapq.heappush(heap, (weights[(start, neighbor)], neighbor, start)) # und fülle Heap

while len(heap) > 0:
w, node, predecessor = heapq.heappop(heap) # hole billigste Kante aus dem Heap
if parents[node] is not None: # die Kante würde einen Zyklus verursachen
continue # => ignoriere diese Kante
parents[node] = predecessor # füge Kante in den MST ein
sum += w # und aktualisiere das Gesamtgewicht
for neighbor in graph[node]: # besuche die Nachbarn von node
if parents[neighbor] is None: # aber nur, wenn kein Zyklus entsteht
heapq.heappush(heap, (weights[(node,neighbor)], neighbor, node)) # füge Kandidaten in Heap ein

return parents, sum # MST und Gesamtgewicht zurückgeben

====Algorithmus von Kruskal====
[http://de.wikipedia.org/wiki/Algorithmus_von_Kruskal Wikipedia (de)]
[http://en.wikipedia.org/wiki/Kruskal%27s_algorithm (en)]

Die alternative Vorgehensweise ist das Verschmelzungsprinzip (vgl. den Abschnitt [[Graphen_und_Graphenalgorithmen#Lösung mittels Union-Find-Algorithmus|Zusammenhangskomponenten mit Union-Find-Algorithmus]]), das der Algorithmus von Kruskal verwendet. Jeder Knoten wird zunächst als trivialer Baum mit nur einem Knoten betrachtet, und alle Kanten werden aufsteigend nach Gewicht sortiert. Dann wird die billigste noch nicht betrachtete Kante in den MST eingefügt, falls sich dadurch kein Zyklus bildet (erkennbar daran, dass die Endknoten in verschiedenen Zusammenhangskomponenten liegen, das heisst verschiedene Anker haben). Da der fertige Baum (V-1) Kanten haben muss, wird dies (V-1) Mal zutreffen. Andernfalls wird diese Kante ignoriert. Anders ausgedrückt: Der Algorithmus beginnt mit ''V'' Bäumen; in (''V''-1) Verschmelzungsschritten kombiniert er jeweils zwei Bäume (unter Verwendung der kürzesten möglichen Kante), bis nur noch ein Baum übrig bleibt. Der einzige Unterschied zum einfachen Union-Find besteht darin, dass die Kanten in aufsteigender Reihenfolge betrachtet werden müssen, was wir hier durch eine Prioritätswarteschlange realisieren. Der Algorithmus von J.Kruskal ist seit 1956 bekannt.

def kruskal(graph, weights):
anchors = range(len(graph)) # Initialisierung der property map: jeder Knoten ist sein eigener Anker
results = [] # result wird später die Kanten des MST enthalten

heap = [] # Heap zum Sortieren der Kanten nach Gewicht
for edge, w in weights.iteritems(): # alle Kanten einfügen
heapq.heappush(heap, (w, edge))

while len(heap) > 0: # solange noch Kanten vorhanden sind
w, edge = heapq.heappop(heap) # billigste Kante aus dem Heap nehmen
a1 = findAnchor(anchors, edge[0]) # Anker von Startknoten der Kante
a2 = findAnchor(anchors, edge[1]) # ... und Endknoten bestimmen
if a1 != a2: # wenn die Knoten in verschiedenen Komponenten sind
anchors[a2] = a1 # Komponenten verschmelzen
result.append(edge) # ... und Kante in MST einfügen

return result # Kanten des MST zurückgeben

Die Funktion <tt>findAnchor()</tt> wurde im Abschnitt [[Graphen_und_Graphenalgorithmen#Lösung mittels Union-Find-Algorithmus|Zusammenhangskomponenten mit Union-Find-Algorithmus]] implementiert. Im Unterschied zum Algorithmus von Prim geben wir hier nicht die property map <tt>parents</tt> zurück, sondern einfach eine Liste der Kanten im MST.

Der Algorithmus eignet sich insbesondere für das Clusteringproblem, da der Schwellwert von vornerein als maximales Kantengewicht an den Algorithmus übergeben werden kann. Man hört mit dem Vereinigen auf, wenn das Gewicht der billigste Kante im Heap den Schwellwert überschreitet. Beim Algorithmus von Kruskal kann dann keine bessere Kante als der Schwellwert mehr kommen, da die Kanten vorher sortiert worden sind.

Komplexität: wie beim Dijkstra-Algorithmus, weil jede Kante genau einmal in den Heap kommt. Der Aufwand für das Sortieren ist somit <math>O\left(E\log E\right)</math>, was sich zu <math>O \left(E\,\log\,V\right)</math> reduziert, falls keine Mehrfachkanten vorhanden sind.

=> geeignet für Übungsaufgabe

== Algorithmen für gerichtete Graphen ==
under construction

Zur Erinnerung: in einem gerichteten Graphen sind die Kanten (i → j) und (j → i) voneinander verschieden, und eventuell existiert nur eine der beiden Richtungen. Im allgemeinen unterscheidet sich der [[Graphen_und_Graphenalgorithmen#transposed_graph|transponierte Graph]] GT also vom Originalgraphen G. Beim Traversieren des Graphen und bei der Pfadsuche dürfen Kanten nur in passender Richtung verwendet werden. Bei gewichteten Graphen tritt häufig der Fall auf, dass zwar Kanten in beiden Richtungen existieren, diese aber unterschiedliche Gewichte haben.

Gerichtete Graphen ergeben sich in natürlicher Weise aus vielen Anwendungsproblemen:
* Routenplanung
** Bei Straßennetzwerken enstehen gerichtete Graphen, sobald es Einbahnstraßen gibt.
** Verwendet man Gewichte, um die erwarteten Fahrzeiten entlang einer Straße zu kodieren, gibt es Asymmetrien z.B. dann, wenn Straßen in einer Richtung bergab, in der anderen bergauf befahren werden. Hier existieren zwar Kanten in beiden Richtungen, sie haben aber unterschiedliche Gewichte. Ähnliches gilt für Flüge: Durch den Gegenwind des Jetstreams braucht man von Frankfurt nach New York länger als umgekehrt von New York nach Frankfurt.
* zeitliche oder kausale Abhängigkeiten
** Wenn die Knoten Ereignissen repräsentieren, von denen einige die Ursache von anderen sind, diese wiederum die Ursache der nächsten usw., verbindet man die Knoten zweckmäßig durch gerichtete Kanten, die die Kausalitätsbeziehungen kodieren. Handelt es sich um logische "wenn-dann"-Regeln, erhält man einen Implikationengraph (siehe unten). Handelt es sich hingegen um Wahrscheinlichkeitsaussagen ("Wenn das Wetter schön ist, haben Studenten tendenziell gute Laune, wenn eine Prüfung bevorsteht eher schlechte usw."), erhält man ein [http://de.wikipedia.org/wiki/Bayessches_Netz Bayessches Netz].
** Wenn bestimmte Aufgaben erst begonnen werden können, nachdem andere Aufgaben erledigt sind, erhält man einen Abhängigkeitsgraphen. Beispielsweise dürfen Sie erst an der Klausur teilnehmen, nachdem Sie die Übungsaufgaben gelöst haben, und Sie dürfen erst die Abschlussarbeit beginnen, nachdem Sie bestimmte Prüfungen bestanden haben. Ein anderes schönes Beispiel liefern die Regeln für das Anziehen weiter unten.
** Gerichtete Graphen kodieren die Abhängigkeiten zwischen Programmbibliotheken. Beispielsweise benötigt das Pythonmodul <tt>json</tt> die internen Submodule <tt>json.encoder</tt> und <tt>json.decode</tt> sowie das externe Modul <tt>decimal</tt>. Die Submodule benötigen wiederum die externen Module <tt>re</tt> und <tt>sys</tt>, das Modul <tt>decimal</tt> braucht <tt>copy</tt> und <tt>collections</tt> usw.
** Das Internet kann als gerichteter Graph dargestellt werden, wobei die Webseiten die Knoent, und die Hyperlinks die Kanten sind.
* Squence Alignment
** Eine gute Rechtschreibprüfung markiert nicht nur fehlerhafte Wörter, sondern macht auch plausible Vorschläge, was eigentlich gemeint gewesen sein könnte. Dazu muss sie das gegebene Wort mit den Wörtern eines Wörterbuchs vergleichen und die Ähnlichkeit bewerten. Ein analoges Problem ergibt sich, wenn man DNA Fragmente mit der Information in einer Genomdatenbank abgleichen will.

=== Anwendung: Sequence Alignment / Edit Distance ===

:gegeben: zwei Wörter (allgemein: beliebige Zeichenfolgen)
:gesucht: Wie kann man die Buchstaben am besten in Übereinstimmung bringen?

:Beispiel: WORTE – NORDEN

Zwei mögliche Alignments sind

WORTE. W.ORTE
NORDEN NORDEN

wobei der Punkt anzeigt, dass der untere Buchstabe keinen Partner hat, und rote Buchstaben oben und unten übereinstimmen. Jede Nicht-Übereinstimmung verursacht nun gewisse Kosten. Dabei unterscheiden wir zwei Fälle:
# Matche a[i] mit b[j]. Falls a[i] == b[j], ist das gut (rote Buchstaben), und es entstehen keine Kosten. Andernfalls entstehen Kosten U (schwarze Buchstaben).
# Wir überspringen a[i] oder b[j] (Buchstabe vs. Punkt). Dann entstehen Kosten V. (Manchmal unterscheidet man auch noch Kosten Va und Vb, wenn das Überspringen bei a und b unterschieldiche Signifikanz hat.)

Gesucht ist nun das Alignment mit minimalen Kosten

Diese Aufgabe kann man sehr schön als gerichteten Graphen darstellen: Wir definieren ein rechteckiges Gitter und schreiben das erste Wort über das Gitter und das andere links davon. Die Gitterpunkte verbinden wir mit Pfeilen (gerichteten Kanten), wobei ein Pfeil nach rechts bedeutet, dass wir beim oberen Wort einen Buchstaben überspringen, ein Pfeil nach unten, dass wir beim linken Wort einen Buchstaben überspringen, und ein diagonaler Pfeil, dass wir zwei Buchstaben matchen (und zwar die am Pfeilende). Die Farben der Pfeile symbolisieren die Kosten: rot für das Überspringen eines Buchstabens (Kosten V), blau für das Matchen, wenn die Buchstaben nicht übereinstimmen (Kosten U), und grün, wenn die Buchstaben übereinstimmen (keine Kosten).

[[Image:sequence-alignment.png|300px]]

Lösung:
:Suche den kürzesten Pfad vom Knoten "START" (oben links) nach unten rechts. Dazu kann der [[Graphen und Graphenalgorithmen#Algorithmus von Dijkstra|Algorithmus von Dijkstra]] verwendet werden, der auf gerichteten Graphen genauso funktioniert wie auf ungerichteten.

Für unser Beispiel von oben erhalten wir die folgenden Pfade:

[[Image:sequence-alignment-weg1.png|400px]]     [[Image:sequence-alignment-weg2.png|400px]]

Durch Addieren der Kosten entsprechend der Farben sieht man, dass der erste Weg die Kosten 2U+V und der zweite die Kosten 5U+V hat. Der erste Weg ist offensichtlich günstiger und entspricht dem besten Alignment.

=== Anwendung: Abhängigkeitsgraph ===

Beispiel: Wie erklärt man einem zerstreuten Professor, wie er sich morgens anziehen soll? Der folgende Graph enthält einen Knoten für jede Aktion, und eine Kante (i → j) bedeutet, dass die Aktion i vor der Aktion j abgeschlossen werden muss.

[[Image:anziehen-graph.png|600px]]

In derartigen Abhängigkeitsgraphen ist die wichtigste Frage immer, ob der Graph azyklisch ist. Wäre dies nämlich nicht der Fall, kann es keine Reihenfolge der Aktionen geben, die alle Abhängigkeiten erfüllt. Dies sieht man leicht, wenn man den einfachsten möglichen Zyklus betrachtet: es gibt sowohl eine Kante (i → j) als auch eine (j → i). Dann müsste man i vor j erledigen, aber ebenso j vor i, was offensichtlich unmöglich ist - das im Graph kodierte Problem ist dann unlösbar. Wegen ihrer Wichtigkeit wird für gerichtete azyklische Graphen oft die Abkürzung DAG (von directed acyclic graph) verwendet. Ein Graph ist genau dann ein DAG, wenn es eine topologische Sortierung gibt:
;topologische Sortierung: Zeichne die Knoten so auf eine Gerade, dass alle Kanten (Pfeile) nach rechts zeigen.
Arbeitet man die Aktionen nach einer (beliebigen) topologischen Sortierung ab, werden automatisch alle Abhängigkeiten eingehalten: Da alle Pfeile nach rechts zeigen, werden abhängige Aktionen immer später ausgeführt. Die topologische Sortierung ist im allgemeinen nicht eindeutig. Die folgende Skizze zeigt eine mögliche topologische Sortierung für das Anziehen:

[[Image:anziehen-topologische-sortierung.png|600px]]

Eine solche fest vorgegebene Reihenfolge ist für den zerstreuten Professor sicherlich eine größere Hilfe als der ursprüngliche Graph. Man erkennt, dass die Sortierung nicht eindeutig ist, beispielsweise bei der Uhr: Da für die Uhr keine Abhängigkeiten definiert sind, kann man diese Aktion an beliebiger Stelle einsortieren. Hier wurde willkürlich die letzte Stelle gewählt.

==== Zwei Algorithmen zum Finden der topologischen Sortierung ====

Die folgenden Algorithmen finden entweder eine topologische Sortierung, oder signalisieren, dass der Graph zyklisch ist.

===== Algorithmus 1 =====
# Suche einen Knoten mit Eingangsgrad 0 (ohne eingehende Pfeile) => in einem gerichteten azyklischen Graphen gibt es immer einen solchen Knoten
# Platziere diesen Knoten auf der Geraden (beliebig)
# Entferne den Knoten aus dem Graphen zusammen mit den ausgehenden Kanten
# Gehe zu 1., aber platziere in 2. immer rechts der Knoten, die schon auf der Geraden vorhanden sind.
: => Wenn noch Knoten übrig sind, aber keiner Eingangsgrad 0 hat, muss der Graph zyklisch sein.

[[Image:bild6.JPG]]

Beispiel für einen zyklischen Graphen: kein Knoten hat Eingangsgrad 0.

Um den Algorithmus zu implementieren, verwenden wir eine property map <tt>in_degree</tt>, die wir in einem ersten Durchlauf durch den Graphen füllen und die dann für jeden Knoten die Anzahl der eingehenden Kanten speichert. Dann gehen wir sukzessive zu allen Knoten mit <tt>in_degree == 0</tt>. Anstatt sie aber tatsächlich aus dem Graphen zu entfernen wie im obigen Pseudocode, dekrementieren wir nur den <tt>in_degree</tt> ihrer Nachbarn. Wird der <tt>in_degree</tt> eines Nachbarn dadurch 0, wird er ebenfalls in das Array der zu scannenden Knoten aufgenommen. Wenn der Graph azyklisch ist, enthält das Array am Ende alle Knoten des Graphen, und die Reihenfolge der Einfügungen definiert eine topologische Sortierung. Andernfalls ist das Array zu kurz, und wir signalisieren durch Zurückgeben von <tt>None</tt>, dass der Graph zyklisch ist:

def topological_sort(graph): # ein gerichteter Graph
in_degree = [0]*len(graph) # property map für den Eingangsgrad jeden Knotens
for node in xrange(len(graph)): # besuche alle Knoten
for neighbor in graph[node]: # ... und deren Nachbarn
in_degree[neighbor] += 1 # ... und inkrementiere den Eingangsgrad

result = [] # wird später die topologische Sortierung enthalten
for node in xrange(len(graph)):
if in_degree[node] == 0:
result.append(node) # füge alle Knoten mit Eingangsgrad 0 in result ein

k = 0
while k < len(result): # besuche alle Knoten mit Eingangsgrad 0
node = result[k]
k += 1
for neighbor in graph[node]: # besuche alle Nachbarn
in_degree[neighbor] -= 1 # entferne 'virtuell' die eingehende Kante
if in_degree[neighbor] == 0: # wenn neighbor jetzt Eingangsgrad 0 hat
result.append(neighbor) # ... füge ihn in result ein

if len(result) == len(graph): # wenn alle Knoten jetzt Eingangsgrad 0 haben
return result # ... ist result eine topologische Sortierung
else:
return None # andernfalls ist der Graph zyklisch

===== Algorithmus 2 =====
Der obige Algorithmus hat den Nachteil, dass er jeden Knoten zweimal expandiert. Man kann eine topologische Sortierung stattdessen auch mit Tiefensuche bestimmen. Es gilt nämlich der folgende
;Satz: Wird ein DAG mittels Tiefensuche traversiert, definiert die reverse post-order eine topologische Sortierung.
Zur Erinnerung: die post-order erhält man, indem man jeden Knoten ausgibt, nachdem die Rekursion zu allen seinen Nachbarn beendet ist, siehe unsere [[Graphen_und_Graphenalgorithmen#pre_and_post_order|Diskussion weiter oben]]. Die reverse post-order ist gerade die Umkehrung dieser Reihenfolge. Die folgende Implementation verwendet die rekursive Version der Tiefensuche, in der Praxis wird man meist die iterative Version mit Stack bevorzugen, weil bei großen Graphen die Aufruftiefe sehr große werden kann:

def reverse_post_order(graph): # gerichteter Graph
result = [] # enthält später die reverse post-order
visited = [False]*len(graph) # Flags für bereits besuchte Knoten

def visit(node): # besuche node
if not visited[node]: # aber nur, wenn er noch nicht besucht wurde
visited[node] = True # markiere ihn als besucht
for neighbor in graph[node]: # und besuche die Nachbarn
visit(neighbor)
result.append(node) # alle Nachbarn besucht => Anhängen an result liefert post-order

for node in xrange(len(graph)): # besuche alle Knoten
visit(node)

result.reverse() # post-order => reverse post-order
return result

Die Tatsache, dass die reverse post-order tatsächlich eine topologische Sortierung liefert, leuchtet wahrscheinlich nicht unmittelbar ein. Bevor wir diese Tatsache beweisen. wollen wir uns anhand des Ankleidegraphen klar machen, dass die pre-order (die man intuitiv vielleicht eher wählen würde) keine topologische Sortierung ist. Startet man die Tiefensuche beim Knoten "Unterhemd", werden die Knoten in der Reihenfolge "Unterhemd", "Oberhemd", "Schlips", "Jackett", "Gürtel" gefunden. Da dann alle von "Unterhemd" erreichbaren Knoten erschöpft sind, startet man die Tiefensuche als nächstes bei "Unterhose" und erreicht von dort aus "Hose" und "Schuhe". Man erkennt sofort, dass diese Reihenfolge nicht funktioniert: "Hose" kommt nach "Gürtel", und "Jackett" kommt vor "Gürtel". Bei dieser Anordnung gibt es Pfeile nach links, die Abhängigkeitsbedingungen sind somit verletzt.

Damit die reverse post-order eine zulässige Sortierung sein kann, muss stets gelten, dass Knoten u vor Knoten v einsortiert wurde, wenn die Kante (u → v) existiert. Das ist aber äquivalent zur Forderung, dass in der ursprünglichen post-order (vor dem <tt>reverse</tt>) u hinter v stehen muss. Wir betrachten den <tt>visit</tt>-Aufruf, bei dem u expandiert wird. Gelangt man jetzt zu u's Nachbarn v, gibt es zwei Möglichkeiten: Wenn v bereits expandiert wurde, befindet es sich bereits im Array <tt>result</tt> und <tt>visit</tt> kehrt sofort zurück. Andernfalls wird v ebenfalls expandiert und damit in <tt>result</tt> eingetragen, bevor der rekursive Aufruf <tt>visit(v)</tt> zurückkehrt. Knoten u wird aber erst in <tt>result</tt> eingefügt, nachdem alle rekursiven <tt>visit</tt>-Aufrufe seiner Nachbarn zurückgekehrt sind. In beiden Fällen steht u in der post-order wie gefordert hinter v, und daraus folgt die Behauptung.

Der obige Algorithmus liefert natürlich nur dann eine topologische Sortierung, wenn der Graph wirklich azyklisch ist (man kann ihn aber auch anwenden, um die reverse post-order für einen zyklischen Graphen zu bestimmen, siehe Abschnitt "[[Graphen_und_Graphenalgorithmen#Transitive Hülle und stark zusammenhängende Komponenten|Stark zusammenhängende Komponenten]]"). Dieser Fall tritt in der Praxis häufig auf, weil zyklische Graphen bei vielen Anwendungen gar nicht erst entstehen können. Weiß man allerdings nicht, ob der Graph azyklisch ist oder nicht, muss man einen zusätzlichen Test auf Zyklen in den Algorithmus einbauen.

Zyklische Graphen sind dadurch gekennzeichnet, dass es im obigen Beweis eine dritte Möglichkeit gibt: Während der Expansion von u wird rekursiv v expandiert, und es gibt eine Rückwärtskante (v → u). (Es spielt dabei keine Rolle, ob v von u aus direkt oder indirekt erreicht wurde.) Ein Zyklus wird also entdeckt, wenn die Tiefensuche zu u zurückkehrt, solange u noch aktiv ist, d.h. wenn die Rekursion von u aus gestartet und noch nicht beendet wurde. Dies kann man leicht feststellen, wenn man in der property map <tt>visited</tt> drei Werte zulässt: 0 für "noch nicht besucht", 1 für "aktiv" und 2 für "beendet". Wir signalisieren einen Zyklus, sobald <tt>visit</tt> für einen Knoten aufgerufen wird, der gerade aktiv ist:

def topological_sort_DFS(graph): # gerichteter Graph
result = [] # enthält später die topologische Sortierung

not_visited, active, finished = 0, 1, 2 # drei Zustände für visited
visited = [not_visited]*len(graph) # Flags für aktive und bereits besuchte Knoten

def visit(node): # besuche node (gibt "True" zurück, wenn Zyklus gefunden wurde)
if not visited[node]: # ... aber nur, wenn er noch nicht besucht wurde
visited[node] = active # markiere ihn als aktiv
for neighbor in graph[node]: # und besuche die Nachbarn
if visit(neighbor): # wenn rekursiv ein Zyklus gefunden wurde
return True # ... brechen wir ab und signalisieren den Zyklus
visited[node] = finished # Rekursion beendet, node ist nicht mehr aktiv
result.append(node) # alle Nachbarn besucht => Anhängen an result liefert post-order
return False # kein Zyklus gefunden
elif visited[node] == active: # Rekursion erreicht einen noch aktiven Knoten
return True # => Zyklus gefunden

for node in xrange(len(graph)): # besuche alle Knoten
if visit(node): # wenn Zyklus gefunden wurde
return None # ... gibt es keine topologische Sortierung

result.reverse() # post-order => reverse post-order (=topologische Sortierung)
return result

Man macht sich leicht klar, dass kein Zyklus vorliegt, wenn die Rekursion einen Knoten erreicht, der bereits auf <tt>finished</tt> gesetzt ist. Nehmen wir an, dass u gerade expandiert wird, und sein Nachbar v ist bereits <tt>finished</tt>. Wenn es einen Zyklus gäbe, müsste es einen Weg von v nach u geben. Dann wäre u aber bereits während der Expansion von v gefunden worden. Da v nicht mehr im Zustand <tt>active</tt> ist, muss die Expansion von v schon abgeschlossen gewesen sein, ohne dass u gefunden wurde. Folglich kann es keinen solchen Zyklus geben.

=== Transitive Hülle und stark zusammenhängende Komponenten ===

Auch bei gerichteten Graphen ist die Frage, welche Knoten miteinander zusammenhängen, von großem Interesse. Wir betrachten dazu wieder die Relation "Knoten v ist von Knoten u aus erreichbar", die anzeigt, ob es einen Weg von u nach v gibt oder nicht. In ungerichteten Graphen ist diese Relation immer symmetrisch, weil jeder Weg in beiden Richtungen benutzt werden kann. In gerichteten Graphen gilt dies nicht. Man muss hier zwei Arten von Zusammenhangskomponenten unterscheiden:
;Transitive Hülle: Die transitive Hülle eines Knotens u ist die Menge aller Knoten, die von u aus erreichbar sind:
:<math>T(u) = \{v\ |\ u \rightsquigarrow v\}</math>
;Stark zusammenhängende Komponenten: Die stark zusammenhängende Komponenten <math>C_i</math> eines gerichteten Graphen sind maximale Teilgraphen, so dass alle Knoten innerhalb einer Komponente von jedem anderen Knoten der selben Komponente aus erreichbar sind
:<math>u,v \in C_i\ \ \Leftrightarrow\ \ u \rightsquigarrow v \wedge v \rightsquigarrow u</math>
Die erste Definition betrachtet den Zusammenhang asymmetrisch, ohne Beachtung der Frage, ob es auch einen Rückweg von Knoten v nach u gibt, die zweite hingegen symmetrisch.

Die transitive Hülle benötigt man, wenn man Fragen der Erreichbarkeit besonders effizient beantworten will. Wir hatten bespielsweise oben erwähnt, dass das Python-Modul <tt>json</tt> direkt und indirekt von mehreren anderen Module abhängt, die vorher installiert werden müssen, damit <tt>json</tt> funktioniert. Bittet man den Systemadministrator, das <tt>json</tt>-Paket zu installieren, will er diese Abhängigkeiten wahrscheinlich nicht erst mühsam rekursiv heraussuchen, sonder er verlangt eine Liste aller Pakete, die installiert werden müssen. Dies ist gerade die transitive Hülle von <tt>json</tt> im Abhängigkeitsgraphen. Damit man diese nicht manuell bestimmen muss, verwendet man Installationsprogrammen wie z.B. [http://pypi.python.org/pypi/pip/ pip], die die Abhängigkeiten automatisch herausfinden und installieren.

Bei der Bestimmung der transitiven Hülle modifiziert man den gegebenen Graphen, indem man jedesmal eine neue Kante (u → v) einfügt, wenn diese Kante noch nicht existiert, aber v von u aus erreichbar ist. Dies gelingt mit einer sehr einfachen Variation der Tiefensuche: Wir rufen <tt>visit(k)</tt> für jeden Knoten k auf, aber setzen die property map <tt>visited</tt> zuvor auf <tt>False</tt> zurück. Alle Knoten, die während der Rekursion erreicht werden, sind im modifizierten Graphen Nachbarn von k. Ein etwas effizienterer Ansatz ist der [http://de.wikipedia.org/wiki/Algorithmus_von_Floyd_und_Warshall Algorithmus von Floyd und Warshall].

Die Bestimmung der stark zusammenhängenden Komponenten ist etwas schwieriger. Es existieren eine ganze Reihe von effizienten Algorithmen (siehe [http://en.wikipedia.org/wiki/Strongly_connected_component WikiPedia]), deren einfachster der Algorithmus von Kosaraju ist:

gegeben: gerichteter Graph

# Bestimme die reverse post-order (mit der Funktion <tt>reverse_post_order</tt>)
# Bilde den transponierten Graphen <math>G^T</math> (mit der Funktion <tt>transposeGraph</tt>)
# Bestimme die Zusammenhangskomponenten von <math>G^T</math> mittels Tiefensuche, aber betrachte die Knoten dabei in der reverse post-order aus Schritt 1 (dies kann mit einer minimalen Modifikation der Funktion <tt>connectedComponents</tt> geschehen, indem man die Zeile <tt>for node in xrange(len(graph)):</tt> einfach nach <tt>for node in ordered:</tt> abändert, wobei <tt>ordered</tt> das Ergebnis der Funktion <tt>reverse_post_order</tt> ist, also ein Array, das die Knoten in der gewünschten Reihenfolge enthält).
Die Zusammenhangskomponenten, die man in Schritt 3 findet, sind gerade die stark zusammenhängenden Komponenten des Originalgraphen G. Die folgende Skizze zeigt diese in grün für den schwarz gezeichneten gerichteten Graphen.

[[Image:strongly-connected-components.png|400px]]

Zum Beweis der Korrektheit des Algorithmus von Kosaraju zeigen wir zwei Implikationen: 1. Wenn die Knoten u und v in der selben stark zusammenhängenden Komponente liegen, werden sie in Schritt 3 des Algorithmus auch der selben Komponente zugewiesen. 2. Wenn die Knoten u und v in Schritt 3 der selben Komponente zugewiesen wurden, müssen sie auch in der selben stark zusammenhängenden Komponente liegen.
# Knoten u und v gehören zur selben stark zusammenhängenden Komponente von G. Per Definition gilt, dass u von v aus erreichbar ist und umgekehrt. Dies muss auch im transponierten Graphen GT gelten (der Weg <math>u \rightsquigarrow v</math> wird jetzt zum Weg <math>v \rightsquigarrow u</math> und umgekehrt). Wird u bei der Tiefensuche in Schritt 3 vor v expandiert, ist v von u aus erreichbar und gehört somit zur selben Komponente. Das umgekehrte gilt, wenn v vor u expandiert wird. Daraus folgt die Behauptung 1.
# Knoten u und v werden in Schritt 3 der selben Komponente zugewiesen: Sei x der Anker dieser Komponente. Da u in der gleichen Komponente wie x liegt, muss es in GT einen Weg <math>x \rightsquigarrow u</math>, und demnach in G einen Weg <math>u \rightsquigarrow x</math> geben. Da x der Anker seiner Komponente ist, wissen wir aber auch, dass x in der reverse post-order vor u liegt (denn der Anker ist der Knoten, mit dem eine neue Komponente gestartet wird; er muss deshalb im Array <tt>ordered</tt> als erster Konten seiner Komponente gefunden worden sein). Wir unterscheiden jetzt im Schritt 1 des Algorithmus zwei Fälle:
## u wurde bei der Bestimmung der post-order vor x expandiert. Dann kann x nur dann in der reverse post-order vor u liegen (oder, einfacher ausgedrückt, x kann nur dann in der post-order hinter u liegen), wenn x im Graphen G nicht von u aus erreichbar war. Das ist aber unmöglich, weil wir ja schon wissen, dass es in G einen Weg <math>u \rightsquigarrow x</math> gibt.
## Folglich wurde u bei der Bestimmung der post-order nach x expandiert. Da x in der post-order hinter u liegt, muss u während der Expansion von x erreicht worden sein. Deshalb muss es in G auch einen Weg <math>x \rightsquigarrow u</math> geben.
#:Somit sind x und u in der selben stark zusammenhängenden Komponente. Die gleiche Überlegung gilt für x und v. Wegen der Transitivität der relation "ist erreichbar" folgt daraus, dass auch u und v in der selben Komponente liegen, also die Behauptung 2.

Die folgende Skizze illustriert, dass der Komponentengraph stets azyklisch ist. Den Komponentengraph erhält man, indem man für jede Komponente <math>C_i</math> einen Knoten erzeugt (grün), und die Knoten i und j durch eine gerichtete Kante verbindet (rot), wenn es im Originalgraphen eine Kante (u → v) mit <math>u \in C_i</math> und <math>v \in C_j</math> gibt. Es ist dann garantiert, dass es keine Kante in umgekehrter Richtung geben kann. Daraus folgt insbesondere, dass ein DAG nur triviale stark verbundene Komponenten haben kann, die aus einzelnen Knoten bestehen.

[[Image:strongly-connected-components-graph.png|400px]]

=== Anwendung: Das Erfüllbarkeitsproblem in Implikationengraphen ===

Das Erfüllbarkeitsproblem hat auf den ersten Blick nichts mit Graphen zu tun, denn es geht um Wahrheitswerte logischer Ausdrücke. Man kann logische Ausdrücke jedoch unter bestimmten Bedingungen in eine Graphendarstellung überführen und somit das ursprüngliche Problem auf ein Problem der Graphentheorie reduzieren, für das bereits ein Lösungsverfahren bekannt ist. In diesem Abschnitt wollen wir dies für die sogenannten Implikationengraphen zeigen, ein weiteres Beispiel findet sich im Kapitel [[NP-Vollständigkeit]].

==== Das Erfüllbarkeitsproblem ====

(vgl. [http://de.wikipedia.org/wiki/Erfüllbarkeitsproblem_der_Aussagenlogik WikiPedia (de)])

Das Erfüllbarkeitsproblem (SAT-Problem, von satisfiability) befasst sich mit logischen (oder Booleschen) Funktionen: Gegeben sei eine Menge <math>\{x_1, ... ,x_n\}</math> Boolscher Variablen (d.h., die <math>x_i</math> können nur die Werte True oder False annehmen), sowie eine logische Formel, in der die Variablen mit den üblichen logischen Operatoren
:<math>\neg\quad</math>: Negation ("nicht", in Python: <tt>not</tt>)
:<math>\vee\quad</math>: Disjunktion ("oder", in Python: <tt>or</tt>)
:<math>\wedge\quad</math>: Konjuktion ("und", in Python: <tt>and</tt>)
:<math>\rightarrow\quad</math>: Implikation ("wenn, dann", in Python nicht als Operator definiert)
:<math>\leftrightarrow\quad</math>: Äquivalenz ("genau, dann wenn", in Python: <tt>==</tt>)
:<math>\neq\quad</math>: exklusive Disjunktion ("entweder oder", in Python: <tt>!=</tt>)
verknüpft sind. Klammern definieren die Reihenfolge der Auswertung der Operationen. Für jede Belegung der Variablen <math>x_i</math> mit True oder False liefert die Formel den Wert der Funktion, der natürlich auch nur True oder False sein kann. Wenn Formel und Belegung gegeben sind, ist die Auswertung der Funktion ein sehr einfaches Problem: Man transformiert die Formel in einen Parse-Baum (siehe Übungsaufgabe "Taschenrechner) und wertet jeden Knoten mit Hilfe der üblichen Wertetabellen für logische Operatoren aus, die wir hier zur Erinnerung noch einmal angeben:
{| cellspacing="0" border="1"
|- style="text-align:center;background-color:#ffffcc;width:50px"
|width="70px"| <math>a</math>
|width="70px"| <math>b</math>
|width="70px"| <math>a \vee b </math>
|width="70px"| <math>a \wedge b</math>
|width="70px"| <math>a \rightarrow b</math>
|width="70px"| <math>b \rightarrow a</math>
|width="70px"| <math>a \leftrightarrow b</math>
|width="70px"| <math>a \neq b</math>
|- align="center"
| 0 || 0 || 0 || 0 || 1 || 1 || 1 || 0
|- align="center"
| 0 || 1 || 1 || 0 || 1 || 0 || 0 || 1
|- align="center"
| 1 || 0 || 1 || 0 || 0 || 1 || 0 || 1
|- align="center"
| 1 || 1 || 1 || 1 || 1 || 1 || 1 || 0
|}

Beim Erfüllbarkeitsproblem wird die Frage umgekehrt gestellt:
:Gegeben sei eine logische Funktion. Ist es möglich, dass die Funktion jemals den Wert True annimmt?
Das heisst, kann man die Variablen <math>x_i</math> so mit True oder False belegen, dass die Formel am Ende wahr ist? Im Prinzip kann man diese Frage durch erschöpfende Suche leicht beantworten, indem man die Funktion für alle <math>2^n</math> möglichen Belegungen einfach ausrechnet, aber das dauert für große n (ab ca. <math>n\ge 40</math>) viel zu lange. Erstaunlicherweise ist es aber noch niemanden gelungen, einen Algorithmus zu finden, der für beliebige logische Funktionen schneller funktioniert. Im Gegenteil wurde gezeigt, dass das Erfüllbarkeitsproblem [[NP-Vollständigkeit|NP-vollständig]] ist, so dass wahrscheinlich kein solcher Algorithmus existiert. Trotz (oder gerade wegen) seiner Schwierigkeit hat das Erfüllbarkeitsproblem viele Anwendungen gefunden, vor allem beim Testen logischer Schaltkreise ("Gibt es eine Belegung der Eingänge, so dass am Ausgang der verbotene Wert X entsteht?") und bei der Planerstellung in der künstlichen Intelligenz ("Kann man ausschließen, dass der generierte Plan Konflikte enthält?"). Es ist außerdem ein beliebtes Modellproblem für die Erforschung neuer Ideen und Algorithmen für schwierige Probleme.

==== Normalformen für logische Ausdrücke ====

Um die Beschreibung von Erfüllbarkeitsproblemen zu vereinfachen und zu vereinheitlichen, hat man verschiedene Normalformen für logische Ausdrücke eingeführt. Die wichtigste ist die Konjuktionen-Normalform (CNF - conjunctive normal form). Ein Ausdruck in Konjuktionen-Normalform ist eine UND-Verknüpfung von M Klauseln:
(CLAUSE1) <math>\wedge</math> (CLAUSE2) <math>\wedge</math> ... <math>\wedge</math> (CLAUSEM)
Jede Klausel ist wiederum ein logischer Ausdruck, der aber sehr einfach sein muss: Er darf nur noch k Variablen enthalten, die nur mit den Operatoren NICHT und ODER verknüpft werden dürfen, z.B.
CLAUSE1 := <math>x_1 \vee \neg x_3 \vee x_8</math>
Je nachdem, wie viele Variablen pro Klausel erlaubt sind, spricht man von k-CNF und entsprechend von einem k-SAT Problem. Es ist außerdem üblich, die Menge der Variablen und die Menge der negierten Variablen zusammen als Menge der Literale zu bezeichnen:
LITERALS := <math>\{x_1,...,x_n\} \cup \{\neg x_1,...,\neg x_n\}</math>
Formal definiert man die k-Konjunktionen-Normalform (k-CNF) am besten durch eine Grammatik in [http://de.wikipedia.org/wiki/Backus-Naur-Form Backus-Naur-Form]:
k_CNF ::= CLAUSE | k_CNF <math>\wedge</math> CLAUSE
CLAUSE ::= (LITERAL <math>\vee</math> ... <math>\vee</math> LITERAL) # genau k Literale pro Klausel
LITERAL ::= VARIABLE | <math>\neg</math>VARIABLE
VARIABLE ::= <math>x_1</math> | ... | <math>x_n</math>
Beispiele:
* 3-CNF: <math>(x_1 \vee \neg x_2 \vee x_4) \wedge (x_2 \vee x_3 \vee \neg x_4) \wedge (\neg x_1 \vee x_4 \vee \neg x_5)</math>
* 2-CNF: <math>(x_1 \vee \neg x_2) \wedge (x_3 \vee x_4)</math> ...
Gesucht ist eine Belegung der Variablen mit True und False, so dass der Ausdruck den Wert True hat. Aus den Eigenschaften der UND- und ODER-Verknüpfungen folgt, dass ein Ausdruck in k-CNF genau dann True ist, wenn jede einzelne Klausel True ist. In jeder Klausel wiederum hat man k Chancen, die Klausel True zu machen, indem man eins der Literale zu True macht. Eventuell werden dadurch aber andere Klauseln wieder zu False, was die Aufgabe so schwierig macht. Die Bedeutung der k-CNF ergibt sich aus folgendem
;Satz: Jeder logische Ausdruck kann effizient nach 3-CNF transformiert werden, jedoch im allgemeinen nicht nach 2-CNF.
Man kann sich also auf Algorithmen für 3-SAT-Probleme konzentrieren, ohne dabei an Ausdrucksmächtigkeit zu verlieren.

Leider gilt der entsprechende Satz nicht für k=2: Ausdrücke in 2-CNF sind weit weniger mächtig, weil man in jeder Klausel nur noch zwei Wahlmöglichkeiten hat. Dafür haben sie den Vorteil, dass es effiziente Algorithmen für das 2-SAT-Problem gibt, die wir jetzt kennenlernen wollen. Es zeigt sich, dass man Ausdrücke in 2-CNF als Graphen repräsentieren kann, indem man sie zunächst in die Implikationen-Normalform (INF für implicative normal form) überführt. Die Implikationen-Normalform besteht ebenfalls aus einer Menge von Klauseln, die durch UND-Operationen verknüpft sind, aber jede Klausel ist jetzt eine Implikation.
Die Grammatik der Implikationen-Normalform (INF) lautet:
INF ::= CLAUSE | INF <math>\wedge</math> CLAUSE
CLAUSE ::= (LITERAL <math>\rightarrow</math> LITERAL) # genau 2 Literale pro Implikation
LITERAL ::= VARIABLE | <math>\neg</math>VARIABLE
VARIABLE ::= <math>x_1</math> | ... | <math>x_n</math>
und ein gültiger Ausdruck wäre z.B.
<math>(x_1 \to x_2) \wedge (x_2 \to \neg x_3) \wedge (x_4 \to x_3)</math>
Die Umwandlung von 2-CNF nach INF beruht auf folgender Äquivalenz, die man sich aus der obigen Wahrheitstabelle leicht herleitet:
:<math>(x \vee y) \equiv (\neg x \rightarrow y) \equiv (\neg y \rightarrow x)</math>
Aus dieser Äquivalenz folgt der
;Satz: Ein Ausdruck in 2-CNF kann nach INF transformiert werden, indem man jede Klausel <math>(x \vee y)</math> durch das Klauselpaar <math>(\neg x \rightarrow y) \wedge (\neg y \rightarrow x)</math> ersetzt.
Man beachte, dass man für jede ODER-Klausel des ursprünglichen Ausdrucks zwei Implikationen (eine für jede Richtung des "wenn, dann") einfügen muss, um die Symmetrie des Problems zu erhalten.

==== Lösung des 2-SAT-Problems mit Implikationgraphen ====

Jeder Ausdruck in INF kann als gerichteter Graph dargestellt werden:
# Für jedes Literal wird ein Knoten in den Graphen eingefügt. Es gibt also für jede Variable und für ihre Negation jeweils einen Knoten, d.h. 2n Knoten insgesamt.
# Jede Implikation ist eine gerichtete Kante.
Implikationengraphen eignen sich, um Ursache-Folge-Beziehungen oder Konflikte zwischen Aktionen auszudrücken. Beispielsweise kann man die Klausel <math>(x \rightarrow \neg y)</math> als "wenn man x tut, darf man y nicht tun" interpretieren. Ein anderes schönes Beispiel findet sich in Übung 12.

Für die Implementation eines Implikationengraphen in Python empfiehlt es sich, die Knoten geschickt zu numerieren: Ist die Variable <math>x_i</math> dem Knoten i zugeordnet, so sollte die negierte Variable <math>\neg x_i</math> dem Knoten (i+n) zugeordnet werden. Zu jedem gegebenen Knoten i findet man dann den Partnerknoten j leicht durch die Formel <tt>j = (i + n ) % (2*n)</tt>.

Die Aufgabe besteht jetzt darin, folgende Fragen zu beantworten:
# Ist der durch den Implikationengraphen gegebene Ausdruck erfüllbar?
# Finde eine geeignete Belegung der Variablen, wenn der Ausduck erfüllbar ist.
Die erste Frage beantwortet man leicht, indem man die die stark zusammenhängenden Komponenten des Implikationengraphen bildet. Dann gilt folgender
;Satz: Seien u und v zwei Literale, die sich in der selben stark zusammenhängenden Komponente befinden. Dann müssen u und v stets den selben Wert haben, damit der Ausdruck erfüllt sein kann.
Die Korrektheit des Satzes folgt aus der Definition der stark zusammenhängenden Komponenten: Da u und v in der selben Komponente liegen, gibt es im Implikationengraphen einen Weg <math>u \rightsquigarrow v</math> sowie einen Weg <math>v \rightsquigarrow u</math>. Wegen der Transitivität der "wenn, dann" Relation kann man die Wege zu zwei Implikationen verkürzen, die gleichzeitig gelten müssen: <math>(u \rightarrow v) \wedge (v \rightarrow u)</math> (die Verkürzung von Wegen zu direkten Kanten entspricht gerade der Bildung der transitiven Hülle für die Knoten u und v). In der obigen Wertetabelle für logische Operatoren erkennt mann, dass dies äquivalent zur Bedingung <math>(u \leftrightarrow v)</math> ist. Dies ist aber gerade die Behauptung des Satzes.

Die Erfüllbarkeit des Ausdrucks ist nun ein einfacher Spezialfall dieses Satzes.
;Korrolar: Der gegebene Ausdruck ist genau dann erfüllbar, wenn die Literale <math>x_i</math> und <math>\neg x_i</math> sich für kein i in derselben stark zusammenhängenden Komponente befinden.
Setzt man nämlich im Satz <math>u = x_i</math> und <math>v = \neg x_i</math>, und beide Knoten befinden sich in der selben Komponente, dann müsste gelten <math>x_i \leftrightarrow\neg x_i</math>, was offensichtlich ein Widerspruch ist. Damit kann der Ausdruck nicht erfüllbar sein. Umgekehrt gilt, dass der Ausdruck immer erfüllbar ist, wenn <math>x_i</math> und <math>\neg x_i</math> stets in verschiedenen Komponenten liegen, weil der folgende Algorithmus von Aspvall, Plass und Tarjan in diesem Fall stets eine gültige Belegung aller Variablen liefert:
# Bestimme die stark zusammenhängenden Komponenten und bilde den Komponentengraphen. Ordne die Knoten des Komponentengraphen (also die stark zusammenhängenden Komponenten des Originalgraphen) in topologische Sortierung an.
# Betrachte die Komponenten in der topologischen Sortierung von hinten nach vorn und weise ihnen einen Wert nach folgenden Regeln zu (zur Erinnerung: alle Literale in der selben Komponente haben den selben Wert):
#* Wenn die Komponente noch nicht betrachtet wurde, setze ihren Wert auf True, und den Wert der komplementären Komponente (derjenigen, die die negierten Literale enthält) auf False.
#* Andernfalls, gehe zur nächsten Komponente weiter.
Der Algorithmus beruht auf der Symmetrie des Implikationengraphen: Weil Kanten immer paarweise <math>(\neg u \rightarrow v) \wedge (\neg v \rightarrow u)</math> eingefügt werden, ist der Graph schiefsymmetrisch (skew symmetric): die eine Hälfte das Graphen ist die transponierte Spiegelung der anderen Hälfte. Enthält eine stark zusammenhängende Komponente <math>C_i</math> die Knoten <tt>i1, i2, ...</tt>, so gibt es stets eine komplementäre Komponente <math>C_j = \neg C_i</math>, die die komplementären Knoten <tt>j1 = (i1 + n) % (2*n), j2 = (i2 + n) % (2*n), ...</tt> enthält. Gilt <math>C_i = \neg C_i</math> für irgendein i, so ist der Ausdruck nicht erfüllbar. Den Beweis für die Korrektheit des Algorithmus findet man im [http://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2007WS/2SAT.pdf Originalartikel]. Leider funktioniert dies nicht für k-SAT-Probleme mit <math>k > 2</math>.

Will man nur die Erfüllbarkeit prüfen, vereinfacht sich der Algorithm zu:
# Bestimme die stark zusammenhängenden Komponenten.
# Teste für alle <tt>i = 0,...,n-1</tt>, dass Knoten <tt>i</tt> und Knoten <tt>(i+n)</tt> in unterschiedlichen Komponenten liegen.
Ist der Ausdruck erfüllbar, kann man eine gültige Belegung der Variablen jetzt mit dem randomisierten Algorithmus bestimmen, den wir im Kapitel [[Randomisierte Algorithmen]] behandeln.

== Weitere wichtige Graphenalgorithmen ==

Eins der wichtigsten Einsatzgebiete für Graphen ist die Optimierung, also die Suche nach der besten Lösung für ein gegebenes Problem:
* Das interval scheduling befasst sich damit, aus einer gegebenen Menge von Aufträgen die richtigen auszuwählen und sie geschickt auf die zur Verfügung stehenden Ressourcen aufzuteilen. Damit beschäftigen wir uns im Kapitel [[Greedy-Algorithmen und Dynamische Programmierung]].
* Beim Problem des Handlungsreisenden sucht man nach der kürzesten Rundreise, die alle gegebenen Städte genau einmal besucht. Dieses Problem behandeln wir im Kapitel [[NP-Vollständigkeit]].
* Viele weitere Anwendungen können wir leider in der Vorlesung nicht mehr behandeln, z.B.
** Algorithmen für den [http://en.wikipedia.org/wiki/Maximum_flow_problem maximalen Fluss] beantworten die Frage, wie man die Durchflussmenge durch ein Netzwerk (z.B. von Ölpipelines) maximiert.
** Beim [http://en.wikipedia.org/wiki/Assignment_problem Problem der optimalen Paarung] ("matching problem" oder "assignment problem") sucht man nach einer Teilmenge der Kanten (also nach einem Teilgraphen), so dass jeder Knoten in diesem Teilgraphen höchstens den Grad 1 hat. Im neuen Graphen gruppieren die Kanten also je zwei Knoten zu einem Paar, und die Paarung soll nach jeweils anwendungsspezifischen Kriterien optimal sein. Dies benötigt man z.B. bei der optimalen Zuordnung von Gruppen, etwas beim Arbeitsamt (Zuordnung Arbeitssuchender - Stellenangebot) und in der Universität (Zuordnung Studenten - Übungsgruppen).
** In Statistik und maschinellem Lernen haben in den letzten Jahren die [http://en.wikipedia.org/wiki/Graphical_model graphischen Modelle] große Bedeutung erlangt.
* usw. usf.

[[Randomisierte Algorithmen|Nächstes Thema]]

Graphen und Graphenalgorithmen

2012-07-10T20:34:01Z

Stephan.meister:

Main Page

2012-05-29T12:20:45Z

Stephan.meister:

== Vorlesung Algorithmen und Datenstrukturen ==

Dr. Ullrich Köthe, Universität Heidelberg, Sommersemester 2012

Die Vorlesung findet '''dienstags''' und '''donnerstags''' jeweils um 14:15 Uhr in INF 227 (KIP), HS 2 statt.

=== Klausur und Nachprüfung ===

Die '''Abschlussklausur''' findet am Dienstag, dem 31.7.2012 von 9:30 bis 12:30 Uhr im HS 1 in INF 306 statt. Zur Klausur wird zugelassen, wer mindestens 50% der Übungspunkte erreicht. (Hinweis: Sie benötigen einen Lichtbildausweis, um sich bei der Klausur zu indentifizieren!)


=== Leistungsnachweise ===
Für alle Leistungsnachweise ist die erfolgreiche Teilnahme an den Übungen erforderlich. Für Leistungspunkte bzw. den Klausurschein muss außerdem die schriftliche Prüfung bestanden werden. Einzelheiten werden noch bekanntgegeben.


=== Übungsbetrieb ===
* Termine und Räume:
** Mo 14:00 - 16:00 Uhr, INF 227 (KIP), Seminarraum 2.402 (Tutor: Sven Ebser [mailto:sven@ebsers.de sven AT ebsers.de])
** Di 9:00 - 11:00 Uhr, INF 227 (KIP), Seminarraum 2.403 (Tutor: Christoph Koke [mailto:koke@kip.uni-heidelberg.de koke AT kip.uni-heidelberg.de])
** Di 11:00 - 13:00 Uhr, INF 227 (KIP), Seminarraum 2.403 (Tutor: Kai Karius [mailto:kai.karius@googlemail.com kai.karius AT googlemail.com])
** Mi 14:00 - 16:00 Uhr, INF 227 (KIP), Seminarraum 2.401 (Tutor: Stephan Meister [mailto:stephan.meister@iwr.uni-heidelberg.de stephan.meister AT iwr.uni-heidelberg.de])
* Die Übungsgruppen werden über [https://www.mathi.uni-heidelberg.de/muesli/lecture/view/169 MÜSLI] verwaltet. Dort erfolgt auch die Anmeldung.

* [[Main Page#Übungsaufgaben|Übungsaufgaben]] (Übungszettel mit Abgabetermin, Musterlösungen). Lösungen bitte per Email an den jeweiligen Übungsgruppenleiter.
* Zur Klausur wird zugelassen, wer mindestens 50% der Übungspunkte erreicht. Außerdem muss jeder Teilnehmer eine Lösung (bzw. einen Teil davon) in der Übungsgruppe vorrechnen.
* Durch das Lösen von Bonusaufgaben und gute Mitarbeit in den Übungen können Sie Zusatzpunkte erlangen. Zusatzpunkte werden auch vergeben, wenn Sie größere Verbesserungen an diesem Wiki vornehmen. Damit solche Verbesserungen der richtigen Person zugeordnet werden, sollten Sie dafür ein eigenes Wiki-Login verwenden, das Ihnen Stephan Meister oder Ullrich Köthe auf Anfrage gerne einrichten.

=== Prüfungsvorbereitung ===

Zur Hilfe bei der Prüfungsvorbereitung hat Andreas Fay [http://de.neemoy.com/quizcategories/31/ Quizfragen] erstellt.

=== Literatur ===

* R. Sedgewick: Algorithmen (empfohlen für den ersten Teil, bis einschließlich Graphenalgorithmen)
* J. Kleinberg, E.Tardos: Algorithm Design (empfohlen für den zweiten Teil, einschließlich Graphenalgorithmen)
* T. Cormen, C. Leiserson, R.Rivest: Algorithmen - eine Einführung (empfohlen zum Thema Komplexität)
* Wikipedia und andere Internetseiten (sehr gute Seiten über viele Algorithmen und Datenstrukturen)

=== Gliederung der Vorlesung ===

# [[Einführung]] (17.4.2012)
#* Definition von Algorithmen und Datenstrukturen, Geschichte
#* Fundamentale Algorithmen: create, assign, copy, swap, compare etc.
#* Fundamentale Datenstrukturen: Zahlen, Container, Handles
#* Python-Grundlagen

# [[Container]] (19.4.2012)
#* Anforderungen von Algorithmen an Container
#* Einteilung der Container
#* Grundlegende Container: Array, verkettete Liste, Stack und Queue
#* Sequenzen und Intervalle (Ranges)

# [[Sortieren]] (24. und 26.4.2012)
#* Spezifikation des Sortierproblems
#* Selection Sort und Insertion Sort
#* Merge Sort
#* Quick Sort und seine Varianten
#* Vergleich der Anzahl der benötigten Schritte
#* Laufzeitmessung in Python

# [[Korrektheit]] (3. und 8.5.2012)
#* Definition von Korrektheit, Algorithmen-Spezifikation
#* Korrektheitsbeweise versus Testen
#* Vor- und Nachbedingungen, Invarianten, Programming by contract
#* Testen, Execution paths, Unit Tests in Python
#* Ausnahmen (exceptions) und Ausnahmebehandlung in Python

# [[Effizienz]] (10. und 15.5.2012)
#* Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference
#* Laufzeit versus Komplexität
#* Landausymbole (O-Notation, <math>\Omega</math>-Notation, <math>\Theta</math>-Notation), Komplexitätsklassen
#* Bester, schlechtester, durchschnittlicher Fall
#* Amortisierte Komplexität

# [[Suchen]] (22. und 24.5.2012)
#* Lineare Suche
#* Binäre Suche in sortierten Arrays, Medianproblem
#* Suchbäume, balancierte Bäume
#* selbst-balancierende Bäume, Rotationen
#* Komplexität der Suche

# [[Prioritätswarteschlangen]] (29.5.2012)
#* Heap-Datenstruktur
#* Einfüge- und Löschoperationen
#* Heapsort
#* Komplexität des Heaps

# [[Hashing und assoziative Arrays]] (31.5.und 5.6.2012)
#* Implementation assoziativer Arrays mit Bäumen
#* Hashing und Hashfunktionen
#* Implementation assoziativer Arrays als Hashtabelle mit linearer Verkettung bzw. mit offener Adressierung
#* Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus

# [[Iteration versus Rekursion]] (12.6.2012)
#* Typen der Rekursion und ihre Umwandlung in Iteration
#* Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode

# [[Generizität]] (14.6.2012)
#* Abstrakte Datentypen, Typspezifikation
#* Required Interface versus Offered Interface
#* Adapter und Typattribute, Funktoren
#* Beispiel: Algebraische Konzepte und Zahlendatentypen
#* Operator overloading in Python

# [[Graphen und Graphenalgorithmen]] (19. bis 28.6.2012)
#* Einführung
#* Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen
#* Gerichtete und ungerichtete Graphen
#* Vollständige Graphen
#* Planare Graphen, duale Graphen
#* Pfade, Zyklen
#* Tiefensuche und Breitensuche
#* Zusammenhang, Komponenten
#* Gewichtete Graphen
#* Minimaler Spannbaum
#* Kürzeste Wege, Best-first search (Dijkstra)
#* Most-Promising-first search (A*)
#* Problem des Handlungsreisenden, exakte Algorithmen (erschöpfende Suche, Branch-and-Bound-Methode) und Approximationen
#* Erfüllbarkeitsproblem, Darstellung des 2-SAT-Problems durch gerichtete Graphen, stark zusammenhängende Komponenten












# [[Randomisierte Algorithmen]] (3. und 5.7.2012)
#* Zufallszahlen, Zyklenlänge, Pitfalls
#* Zufallszahlengeneratoren: linear congruential generator, Mersenne Twister
#* Randomisierte vs. deterministische Algorithmen
#* Las Vegas vs. Monte Carlo Algorithmen
#* Beispiel für Las Vegas: Randomisiertes Quicksort
#* Beispiele für Monte Carlo: Randomisierte Lösung des k-SAT Problems
#* RANSAC-Algorithmus, Erfolgswahrscheinlichkeit, Vergleich mit analytischer Optimierung (Methode der kleinsten Quadrate)

# [[Greedy-Algorithmen und Dynamische Programmierung]] (10. und 12.7.2012)
#* Prinzipien, Aufwandsreduktion in Entscheidungsbäumen
#* bereits bekannte Algorithmen: minimale Spannbäume nach Kruskal, kürzeste Wege nach Dijkstra
#* Beispiel: Interval Scheduling Problem und Weighted Interval Scheduling Problem
#* Beweis der Optimalität beim Scheduling Problem: "greedy stays ahead"-Prinzip, Directed Acyclic Graph bei dynamischer Programmierung

# [[NP-Vollständigkeit]] (17. und 19.7.2012)
#* die Klassen P und NP
#* NP-Vollständigkeit und Problemreduktion

# Reserve und/oder Wiederholung (24. und 26.7.2012)

== Übungsaufgaben ==

(im PDF Format). Die Abgabe erfolgt am angegebenen Tag bis 14:00 Uhr per Email an den jeweiligen Übungsgruppenleiter. Bei Abgabe bis zum folgenden Montag 11:00 Uhr werden noch 50% der erreichten Punkte angerechnet. Danach wird die Musterlösung freigeschaltet.

# [[Media:Übung-1.pdf|Übung]] (Abgabe 24.4.2012) und [[Media:Uebung-1-Musterloesung.pdf|Musterlösung]]
#* Python-Tutorial
#* Sieb des Eratosthenes
#* Wert- und Referenzsemantik
#* Dynamisches Array
# [[Media:Uebung-2.pdf|Übung]] (Abgabe 3.5.2012) und [[Media:Uebung-2-Musterloesung.pdf|Musterlösung]]
#* Sortieren: Implementation und Geschwindigkeitsvergleich (Diagramme in Abhängigkeit von der Problemgröße)
#* Entwicklung eines Gewinnalgorithmus für ein Spiel
#* Bonus: Dynamisches Array mit verringertem Speicherverbrauch
# [[Media:Uebung-3.pdf|Übung]] (Abgabe 10.5.2012) und [[Media:Uebung-3-Musterlösung.pdf|Musterlösung]]
#* Experimente zur Effektivität von Unit Tests
#* Bestimmung von Pi mit dem Algorithmus von Archimedes
#* Deque-Datenstruktur: Vor- und Nachbedingungen der Operationen, Implementation und Unit Tests
# [[Media:Uebung-4.pdf|Übung]] (Abgabe '''Montag''' 21.5.2012) 
#* Theoretische Aufgaben zur Komplexität
#* Amortisierte Komplexität von array.append()
#* Optimierung der Matrizenmultiplikation
# [[Media:Uebung-5.pdf|Übung]] (31.5.2012) 
#* Implementation und Analyse eines Binärbaumes
#* Anwendung: einfacher Taschenrechner


== Sonstiges ==
* [[Gnuplot| Gnuplot Kurztutorial]]
* [[Git Kurztutorial]]
* [[neue Startseite|mögliche neue Startseite]]

Git Kurztutorial

2012-05-29T12:20:04Z

Stephan.meister: Kurztoturial angelegt

= Anleitung zur Abgabe der Übungszettel über Git und Bitbucket =

Übungszettel können in Zukunft auch das Online Repository Bitbucket (https://bitbucket.org/) abgegeben werden.
Dazu nutzen wir das Versionverwaltungstool Git (http://git-scm.com/).

= Terminologie =
Die genauen Bezeichnungen können sich zwischen den verschiedenen Versionsverwaltungssystemem unterscheiden (z.B. Git, Bazaar, SVN, etc.)
; Revision : Eine konkrekte Version einer Datei, eines Ordners oder einer ganzen Ordnerstruktur die im Versionsverwaltungssystem enthalten ist
; Branch : i.d.R. die aktuellste Revision. In der Softwareentwicklung nutz man häufig mehrere branches parallel, z.B. einen Hauptentwicklungszweig (branch) und mehrere Nebenzweige für Experimente oder neue Programfeatures.
; working copy : Die Dateien und Ordner die man gerade bearbeitet und deren Änderungen i.d.R. noch nicht im Versionsverwaltungssystem enthalten sind
; Repository : Eine Sammlung an Revisionen mit zeitlicher und/oder logischer Ordnung.
; commit : Das einpflegen der aktuellen working copy in das Repository (dabei wird eine neue Revision erzeugt)

= Kurzanleitung =
# Anlegen eines Accounts bei Bitbucket
# Erzeugen eines Repositories (Repositories -> create Repository)
## Sinnvollen Namen für das Repository wählen, z.B. ALDA
## Repository Type: Git
## Language: Python
# Setzen der Zugriffsrechte
## (Repository -> <eigenes Repository> -> Admin -> Access Managment)
## Hier kann man dem Übungspartner Schreibrechte zuweisen, bzw. dem Übungsgruppenleiter Leserechte
# Klonen des Repositories auf den eigenen Rechner (damit erzeugt man auch eine working copy)
## In der Kommandozeile: <nowiki>git clone https://<nutzername>@bitbucket.org/<nutzername>/<repository>.git</nowiki>
# Übungszettel lösen
# Für die Übung relevante Dateien einchecken
## Es empfiehlt sich Unterordner für die verschiedenen Übungszettel anzulegen, z.b. 01,02,etc.
## <nowiki>git add <dateiname></nowiki> bzw. git add <ordnername> (fügt den ordner und alle enthaltenen Dateien hinzu)
## <nowiki>git commit -a -m "Statusnachricht"</nowiki> (Erzeugt eine neue Revision mit allen hinzugefügten neuen Dateien sowie den Änderungen an bereits bestehenden Dateien)
## <nowiki>git push -u origin master</nowiki> (Übertragen der Daten zum Server)

* Erst nach diesem letzem Schritt können die Übungsleiter auch die Lösungen einsehen. Es empfiehlt sich auf der bitbucket Homepage im eigenen Repository unter "Code" zu überprüfen ob alle wichtigen Dateien vorhanden sind.
* Es genügt ein Repository pro Team. Einzelne Übungszettel sollten in Unterordnern organisiert sein.

= Nützliche Links =
* Bitbucket Tutorial[https://confluence.atlassian.com/display/BITBUCKET/Create+an+Account+and+a+Git+Repo 1], [https://confluence.atlassian.com/display/BITBUCKET/Clone+Your+Git+Repo+and+Add+Source+Files 2]

Main Page

2012-05-08T11:43:11Z

Stephan.meister:

== Vorlesung Algorithmen und Datenstrukturen ==

Dr. Ullrich Köthe, Universität Heidelberg, Sommersemester 2012

Die Vorlesung findet '''dienstags''' und '''donnerstags''' jeweils um 14:15 Uhr in INF 227 (KIP), HS 2 statt.

=== Klausur und Nachprüfung ===

Die '''Abschlussklausur''' findet am Dienstag, dem 31.7.2012 von 9:30 bis 12:30 Uhr im HS 1 in INF 306 statt. Zur Klausur wird zugelassen, wer mindestens 50% der Übungspunkte erreicht. (Hinweis: Sie benötigen einen Lichtbildausweis, um sich bei der Klausur zu indentifizieren!)


=== Leistungsnachweise ===
Für alle Leistungsnachweise ist die erfolgreiche Teilnahme an den Übungen erforderlich. Für Leistungspunkte bzw. den Klausurschein muss außerdem die schriftliche Prüfung bestanden werden. Einzelheiten werden noch bekanntgegeben.


=== Übungsbetrieb ===
* Termine und Räume:
** Mo 14:00 - 16:00 Uhr, INF 227 (KIP), Seminarraum 2.402 (Tutor: Sven Ebser [mailto:sven@ebsers.de sven AT ebsers.de])
** Di 9:00 - 11:00 Uhr, INF 227 (KIP), Seminarraum 2.403 (Tutor: Christoph Koke [mailto:koke@kip.uni-heidelberg.de koke AT kip.uni-heidelberg.de])
** Di 11:00 - 13:00 Uhr, INF 227 (KIP), Seminarraum 2.403 (Tutor: Kai Karius [mailto:kai.karius@googlemail.com kai.karius AT googlemail.com])
** Mi 14:00 - 16:00 Uhr, INF 227 (KIP), Seminarraum 2.401 (Tutor: Stephan Meister [mailto:stephan.meister@iwr.uni-heidelberg.de stephan.meister AT iwr.uni-heidelberg.de])
* Die Übungsgruppen werden über [https://www.mathi.uni-heidelberg.de/muesli/lecture/view/169 MÜSLI] verwaltet. Dort erfolgt auch die Anmeldung.

* [[Main Page#Übungsaufgaben|Übungsaufgaben]] (Übungszettel mit Abgabetermin, Musterlösungen). Lösungen bitte per Email an den jeweiligen Übungsgruppenleiter.
* Zur Klausur wird zugelassen, wer mindestens 50% der Übungspunkte erreicht. Außerdem muss jeder Teilnehmer eine Lösung (bzw. einen Teil davon) in der Übungsgruppe vorrechnen.
* Durch das Lösen von Bonusaufgaben und gute Mitarbeit in den Übungen können Sie Zusatzpunkte erlangen. Zusatzpunkte werden auch vergeben, wenn Sie größere Verbesserungen an diesem Wiki vornehmen. Damit solche Verbesserungen der richtigen Person zugeordnet werden, sollten Sie dafür ein eigenes Wiki-Login verwenden, das Ihnen Stephan Meister oder Ullrich Köthe auf Anfrage gerne einrichten.

=== Prüfungsvorbereitung ===

Zur Hilfe bei der Prüfungsvorbereitung hat Andreas Fay [http://de.neemoy.com/quizcategories/31/ Quizfragen] erstellt.

=== Literatur ===

* R. Sedgewick: Algorithmen (empfohlen für den ersten Teil, bis einschließlich Graphenalgorithmen)
* J. Kleinberg, E.Tardos: Algorithm Design (empfohlen für den zweiten Teil, einschließlich Graphenalgorithmen)
* T. Cormen, C. Leiserson, R.Rivest: Algorithmen - eine Einführung (empfohlen zum Thema Komplexität)
* Wikipedia und andere Internetseiten (sehr gute Seiten über viele Algorithmen und Datenstrukturen)

=== Gliederung der Vorlesung ===

# [[Einführung]] (17.4.2012)
#* Definition von Algorithmen und Datenstrukturen, Geschichte
#* Fundamentale Algorithmen: create, assign, copy, swap, compare etc.
#* Fundamentale Datenstrukturen: Zahlen, Container, Handles
#* Python-Grundlagen

# [[Container]] (19.4.2012)
#* Anforderungen von Algorithmen an Container
#* Einteilung der Container
#* Grundlegende Container: Array, verkettete Liste, Stack und Queue
#* Sequenzen und Intervalle (Ranges)

# [[Sortieren]] (24. und 26.4.2012)
#* Spezifikation des Sortierproblems
#* Selection Sort und Insertion Sort
#* Merge Sort
#* Quick Sort und seine Varianten
#* Vergleich der Anzahl der benötigten Schritte
#* Laufzeitmessung in Python

# [[Korrektheit]] (3. und 8.5.2012)
#* Definition von Korrektheit, Algorithmen-Spezifikation
#* Korrektheitsbeweise versus Testen
#* Vor- und Nachbedingungen, Invarianten, Programming by contract
#* Testen, Execution paths, Unit Tests in Python
#* Ausnahmen (exceptions) und Ausnahmebehandlung in Python

# [[Effizienz]] (10. und 15.5.2012)
#* Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference
#* Laufzeit versus Komplexität
#* Landausymbole (O-Notation, <math>\Omega</math>-Notation, <math>\Theta</math>-Notation), Komplexitätsklassen
#* Bester, schlechtester, durchschnittlicher Fall
#* Amortisierte Komplexität

# [[Suchen]] (22. und 24.5.2012)
#* Lineare Suche
#* Binäre Suche in sortierten Arrays, Medianproblem
#* Suchbäume, balancierte Bäume
#* selbst-balancierende Bäume, Rotationen
#* Komplexität der Suche

# [[Prioritätswarteschlangen]] (29.5.2012)
#* Heap-Datenstruktur
#* Einfüge- und Löschoperationen
#* Heapsort
#* Komplexität des Heaps

# [[Hashing und assoziative Arrays]] (31.5.und 5.6.2012)
#* Implementation assoziativer Arrays mit Bäumen
#* Hashing und Hashfunktionen
#* Implementation assoziativer Arrays als Hashtabelle mit linearer Verkettung bzw. mit offener Adressierung
#* Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus

# [[Iteration versus Rekursion]] (12.6.2012)
#* Typen der Rekursion und ihre Umwandlung in Iteration
#* Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode

# [[Generizität]] (14.6.2012)
#* Abstrakte Datentypen, Typspezifikation
#* Required Interface versus Offered Interface
#* Adapter und Typattribute, Funktoren
#* Beispiel: Algebraische Konzepte und Zahlendatentypen
#* Operator overloading in Python

# [[Graphen und Graphenalgorithmen]] (19. bis 28.6.2012)
#* Einführung
#* Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen
#* Gerichtete und ungerichtete Graphen
#* Vollständige Graphen
#* Planare Graphen, duale Graphen
#* Pfade, Zyklen
#* Tiefensuche und Breitensuche
#* Zusammenhang, Komponenten
#* Gewichtete Graphen
#* Minimaler Spannbaum
#* Kürzeste Wege, Best-first search (Dijkstra)
#* Most-Promising-first search (A*)
#* Problem des Handlungsreisenden, exakte Algorithmen (erschöpfende Suche, Branch-and-Bound-Methode) und Approximationen
#* Erfüllbarkeitsproblem, Darstellung des 2-SAT-Problems durch gerichtete Graphen, stark zusammenhängende Komponenten












# [[Randomisierte Algorithmen]] (3. und 5.7.2012)
#* Zufallszahlen, Zyklenlänge, Pitfalls
#* Zufallszahlengeneratoren: linear congruential generator, Mersenne Twister
#* Randomisierte vs. deterministische Algorithmen
#* Las Vegas vs. Monte Carlo Algorithmen
#* Beispiel für Las Vegas: Randomisiertes Quicksort
#* Beispiele für Monte Carlo: Randomisierte Lösung des k-SAT Problems
#* RANSAC-Algorithmus, Erfolgswahrscheinlichkeit, Vergleich mit analytischer Optimierung (Methode der kleinsten Quadrate)

# [[Greedy-Algorithmen und Dynamische Programmierung]] (10. und 12.7.2012)
#* Prinzipien, Aufwandsreduktion in Entscheidungsbäumen
#* bereits bekannte Algorithmen: minimale Spannbäume nach Kruskal, kürzeste Wege nach Dijkstra
#* Beispiel: Interval Scheduling Problem und Weighted Interval Scheduling Problem
#* Beweis der Optimalität beim Scheduling Problem: "greedy stays ahead"-Prinzip, Directed Acyclic Graph bei dynamischer Programmierung

# [[NP-Vollständigkeit]] (17. und 19.7.2012)
#* die Klassen P und NP
#* NP-Vollständigkeit und Problemreduktion

# Reserve und/oder Wiederholung (24. und 26.7.2012)

== Übungsaufgaben ==

(im PDF Format). Die Abgabe erfolgt am angegebenen Tag bis 14:00 Uhr per Email an den jeweiligen Übungsgruppenleiter. Bei Abgabe bis zum folgenden Montag 11:00 Uhr werden noch 50% der erreichten Punkte angerechnet. Danach wird die Musterlösung freigeschaltet.

# [[Media:Übung-1.pdf|Übung]] (Abgabe 24.4.2012) und [[Media:Uebung-1-Musterloesung.pdf|Musterlösung]]
#* Python-Tutorial
#* Sieb des Eratosthenes
#* Wert- und Referenzsemantik
#* Dynamisches Array
# [[Media:Uebung-2.pdf|Übung]] (Abgabe 3.5.2012) 
#* Sortieren: Implementation und Geschwindigkeitsvergleich (Diagramme in Abhängigkeit von der Problemgröße)
#* Entwicklung eines Gewinnalgorithmus für ein Spiel
#* Bonus: Dynamisches Array mit verringertem Speicherverbrauch
# [[Media:Uebung-3.pdf|Übung]] (Abgabe 10.5.2012) 
#* Experimente zur Effektivität von Unit Tests
#* Bestimmung von Pi mit dem Algorithmus von Archimedes
#* Deque-Datenstruktur: Vor- und Nachbedingungen der Operationen, Implementation und Unit Tests


== Sonstiges ==
* [[Gnuplot| Gnuplot Kurztutorial]]

Gnuplot

2012-05-08T11:41:00Z

Stephan.meister: Created page with '= Gnuplot Kurztutorial = == Plotten von Daten aus einer Datei == Bsp. data.txt mit 4 x/y1/y2 Wertepaaren: 1 2.0 1.0 2 3.0 4.0 3 5.5 7.9 4 3.1 16.1 Plot…'

= Gnuplot Kurztutorial =

== Plotten von Daten aus einer Datei ==

Bsp. data.txt mit 4 x/y1/y2 Wertepaaren:
1 2.0 1.0
2 3.0 4.0
3 5.5 7.9
4 3.1 16.1

Plotten der Punkte x/y1:
plot 'data.txt' using 1:2 # 1:2 gibt die 1. und 2. Spalte in der Datei an
Plotten der Punkte x/y2 mit Verbindungslinien und Legendeneintrag:
plot 'data.txt' using 1:3 with lines title 'some Data'

== Fitten einer Funktion ==
f(x) = a*x**2+b*x+c #Definieren der Funktion:
fit f(x) 'data.txt' using 1:3 via a,b,c #Fit der x/y2 Daten:
plot 'data.txt' using 1:3, f(x)

== Speichern des Plots als Bilddatei ==
set term png size 800,600 #Ausgabeformat auf png Bilddatei mit 800x600 pixeln umstellen
set output 'plot.png' #Dateiname für Ausgabe festlegen
replot #vorherigen plotbefehl wiederholen
set output #offene Bilddatei schließen
set term wxt #Ausgabe wieder auf Bildschirmausgabe zurückschalten, Alternativ auch: set term x11 oder set term windows

== Nützliche Kommandos ==
set xlabel 'Something' #Setzen der Achsenbeschriftung
set title 'Bla' #Plot Überschrift
set logscale y #Y-Achse logarithmisch skalieren
set xrange [0:10] #Plotbereich auf der X-Achse festlegen
set grid #Raster anzeigen
pwd #Anzeige des aktuellen Arbeitsverzeichnisses
cd 'pfad' #wechsel des aktuellen Arbeitsverzeichnisses

== Hinweise ==
* Gnuplot benutzt entweder . oder , als Dezimaltrennzeichen (Abhängig von der Spracheinstellung des Systems). Wenn die Werte abgeschnitten werden muss in der Datei mit den Werten . durch , oder anders herum ersetzt werden.
* Alle Plotbefehle können auch in eine Datei (z.B. plot.txt) geschrieben und dann mit load('plot.txt') ausgeführt werden.
* Weitere Informationen und Tipps findet man z.B. bei [http://t16web.lanl.gov/Kawano/gnuplot/index-e.html Gnuplot Not-so-FAQ] oder [http://www.gnuplot.info/documentation.html]
* Lange Plotbefehle (mit mehreren Kurven/Datensätzen in einem Graph) können mit \ in mehrere Zeilen aufgebrochen werden