Graphen und Graphenalgorithmen

Einführung zu Graphen

Motivation -- Königsberger Brückenproblem

Leonhard Euler [1] 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?

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: degree(a) == degree(c) == degree(d) == 3 und degree(b) == 5. 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 out_degree(1) == out_degree(3) == in_degree(2) == in_degree(4) == 2 und in_degree(1) == in_degree(3) == out_degree(2) == out_degree(4) == 0:

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 K₁ bis K₅ bezeichnet).

k1	k2	k3
k4	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' ⊆ 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 v_i 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 v₀ = v_n gilt.
• Ein Kreis ist ein Zyklus ohne Überkreuzungen. Das heisst, es gilt v₀ = v_n 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 = (V_D, E_D), dessen Knoten und Kanten wie folgt definiert sind:

• V_D enthält einen Knoten für jede Region des Graphen G
• Für jede Kante e ∈ E gibt es eine duale Kante e_D ∈ E_D, 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.

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|²) 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 a => 0, b => 1, c => 2, d => 3), erhalten wir die Adjazenzlistendarstellung:

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

Auf die Nachbarknoten eines durch seinen Index node 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.

Transponierter Graph

Den transponierten Graphen G^T 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 G^T = G gilt. Bei gerichteten Graphen ist die Transposition dann einfach, wenn der Graph als Adjazenzmatrix implementiert ist, weil man einfach die transponierte Adjazenzmatrix verwenden muss (beachte, dass sich die Reihenfolge der Indizes umkehrt):

A^T = a_ji

Ist der Graph hingegen durch eine Adjazenzliste repräsentiert, muss etwas mehr Aufwand getrieben werden:

def transpose(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 startnode. Die Information, ob ein Knoten bereits besucht wurde, wird im Array visited 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 = [None]*len(graph)   # Flags, welche Knoten bereits besucht wurden
    
    def visit(node):              # rekursive Hilfsfunktion, die den gegebenen Knoten und dessen Nachbarn besucht
        if visited[node] is None: # 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)

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

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:

def dfs(graph, startnode):
    visited = [None]*len(graph)   # Flags, welche Knoten bereits besucht wurden
    
    def visit(node):              # rekursive Hilfsfunktion, die den gegebenen Knoten und dessen Nachbarn besucht
        if visited[node] is None: # 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 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 visited 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 parents 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 None 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 visited[node] is None:   # Besuche node, wenn er noch nicht besucht wurde
            visited[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 parents, und der Vaterknoten ist der dazugehörige Arrayeintrag. Beachte, dass Knoten 0 in diesem Graphen nicht existiert, daher ist sein Eintrag None. 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 deque aus dem Python-Modul collections (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 = [None]*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 visited[node] is None:  # 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)

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 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:

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 START. Sobald wir den Knoten STOP 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 parent-Flag wieder auf None 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 parent-Flag von B3 wieder auf None 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).

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:

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 = [None]*len(graph)           # Flags für bereits besuchte Knoten
    
    def visit(node, from_node):           # rekursive Hilfsfunktion: gibt True zurück, wenn Zyklus gefunden wurde
        if visited[node] is None:         # 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 visited verwenden wir diesmal eine property map anchors, die für jeden Knoten die Knotennummer des zugehörigen Ankers angibt, oder None, 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 findAnchor(), 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 anchors 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 findAnchor() 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 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 visited eine property map parents verwendet wird, die für jeden besuchten Knoten den Vaterknoten im Breitensuchbaum speichert. Durch Rückverfolgen der parent-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 (break-Befehl in der ersten while-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 None 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 w_st zugeordnet, die üblicherweise als Kantengewicht bezeichnet wird.

Definition - knotengewichteter Graph

Jedem Knoten v des Graphen ist eine reelle oder natürliche Zahl w_v 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 a_ij das Gewicht der Kante i ⇒ j (wobei a_ij = 0 gesetzt wird, wenn diese Kante nicht existiert). Wie zuvor gilt für ungerichtete Graphen a_ij = a_ji (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. visited und anchors) 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 W_p 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 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 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 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"[2], 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 shortestPath() 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 parents bereits gesetzt ist.

Eine geeignete Datenstruktur für die Prioritätswarteschlange wird durch das Python-Modul heapq realisiert. Es verwendet ein normales Pythonarray als unterliegende Repräsentation für einen Heap und stellt effiziente heappush und heappop-Funktionen zur Verfügung. Dies entspricht genau unserer Vorgehensweise im Kapitel Prioritätswarteschlangen. Als Datenelement erwartet die Funktion heappush 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 weights übergeben:

 
   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
 

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 while len(q) > 0: wird jeweils der Knoten node mit der aktuell kürzesten Pfadlänge aus dem Heap entfernt. Die Pfadlänge vom Start zu diesem Knoten wird in der Variable length gespeichert, sein Vorgänger in der Variable predecessor. Wenn der aktuelle Weg nicht der kürzeste ist (parents[node] war bereits gesetzt), wird dieser Weg ignoriert. Andernfalls werden die property map parents aktualisiert und die Nachbarn von node besucht. Beim Scannen der Nachbarn berechnen wir zunächst die Länge newLength das Weges startnode => node => neighbor als Summe von length und dem Gewicht der Kante (node, neighbode). 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 destination 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 updatePriority-Funktion anbietet, ohne dass dadurch eine signifikante Beschleunigung erreicht wird. Deshalb verfolgen wir diesen Ansatz nicht.

Beispiel

under construction

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 parents 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 parents 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 # 2 für jeden Knoten höchstens einmal erreicht werden kann: Da parents[node] beim ersten Durchlauf gesetzt wird, kann die if-Abfrage beim gleichen Knoten nie wieder False liefern, und das nachfolgende continue bewirkt, dass der Abschnitt # 2 dann übersprungen wird. Man sagt auch, dass jeder Knoten höchstens einmal expandiert wird, auch wenn er mehrmals im Heap war.

Der Codeabschnitt # 2 selbst enthält eine Schleife über alle ausgehenden Kanten des Knotens node. 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 heappush 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 if-Abfrage in der for-Schleife), und das ist nur ein einer Richtung möglich. Dies hat zwei Konsequenzen:

• Die Schleife while len(q) > 0: wird nur so oft ausgeführt, wie Elemente im Heap sind, also höchstens E Mal. Das gleiche gilt für den Codeabschnitt # 1, der das heappop enthält.
• Die Operationen heappush und heappop 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: heappush und heappop 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 count, die nach jeder Einfügung in den Heap (also nach jedem Aufruf von heappush) 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 parents[node] gesetzt (also ungleich None) ist, dann liefert das Zurückverfolgen des Weges von node nach startnode den kürzesten Weg.

Induktionsanfang

parents[startnode] ist als einziges gesetzt. Zurückverfolgen liefert den trivialen Weg [startnode], 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 parents[node] gesetzt wird.

Sei <math>S</math> = {v | parents[v] is not None} die Menge aller Knoten, von denen wir den kürzesten Weg schon kennen (Induktionsvoraussetzung), und node der Knoten, der sich gerade an der Spitze des Heaps befindet. Dann ist predecessor der Vorgänger von node im aktuellen Weg, und es muss predecessor<math>\in S</math> gelten, weil die Nachbarn von predecessor (und damit auch der aktuelle node) erst in den Heap eingefügt werden, wenn der kürzeste Weg für predecessor 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 node → predecessor → startnode nicht der kürzeste Weg ist. Dann muss es einen anderen, kürzeren Weg node → x → startnode geben. Für den Vorgänger x in diesem Weg unterscheiden wir zwei Fälle:

• x<math>\in S</math>: In diesem Fall ist die Länge des Weges node → x → startnode 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 node → predecessor → startnode.
• x<math>\notin S</math>: Die Kosten des Weges node → x → startnode berechnen sich als Kosten(x → startnode) + weight[(x, node)], und die Kosten des Weges node → predecessor → startnode sind analog Kosten(predecessor → startnode) + weight[(predecessor, node)]. Aufgrund der Induktionsvoraussetzung gilt aber predecessor<math>\in S</math>, und somit Kosten(predecessor → startnode) < Kosten(x → startnode), weil x andernfalls vor predecessor an der Spitze des Heaps gewesen wäre, was mit der Annahme x<math>\notin S</math> unverträglich ist. Damit der Weg node → x → startnode trotzdem der kürzeste Weg sein kann, müsste Kosten(x → startnode) < Kosten(node → startnode) gelten, denn durch die Kante (x, node) kommen ja noch Kosten hinzu. Das wäre aber nur möglich, wenn der Knoten x vor dem Knoten node an die Spitze des Heaps gelangt, im Widerspruch zur Annahme, dass node sich gerade an der Spitze des Heaps befindet. Somit kann die Behauptung, dass der Weg node → x → startnode 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 destination 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 parent-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 startnode → node dazu, um die verbesserte Priorität zu erhalten:

priority = newLength + guess(neighbor, destination)

(Im originalen Dijkstra-Algorithmus wird als Priorität nur newLength allein verwendet. Man beachte, dass man newLength 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 guess(destination, destination) = trueDistance(destination, destination) = 0, an der Priorität des Knotens destination ä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 node 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 parent-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 destination, 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)

Ein minimal aufspannender Baum verbindet alle Punkte eines Graphen bei minimaler Kantenlänge (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.)?

MST minimale Verbindung (Abb.1)	MST = 2 (Länge = Kantengewicht)(Abb.2)

• 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.

• 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

• 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öße_i, Gewicht_i) 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 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

Wikipedia (de) (en)

Der Algorithmus von Prim geht nach dem Anlagerungsprinzip vor (vgl. den Abschnitt 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 (priority, node, predecessor). Die folgende Implementation verdeutlicht sehr schön die Ähnlichkeit der beiden Algorithmen. Das Ergebnis wird als property map parents 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

Wikipedia (de) (en)

Die alternative Vorgehensweise ist das Verschmelzungsprinzip (vgl. den Abschnitt 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 findAnchor() wurde im Abschnitt Zusammenhangskomponenten mit Union-Find-Algorithmus implementiert. Im Unterschied zum Algorithmus von Prim geben wir hier nicht die property map parents 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

Problem des Handlungsreisenden

(engl.: Traveling Salesman Problem; abgekürzt: TSP)<br\> Wikipedia (de) (en)

Optimaler Reiseweg eines Handlungsreisenden(Quelle)

• Eine der wohl bekanntesten Aufgabenstellungen im Bereich der Graphentheorie ist das Problem des Handlungsreisenden.
• Hierbei soll ein Handlungsreisender nacheinander n Städte besuchen und am Ende wieder an seinem Ausgangspunkt ankommen. Dabei soll jede Stadt nur einmal besucht werden und der Weg mit den minimalen Kosten gewählt werden.
• Alternativ kann auch ein Weg ermittelt werden, dessen Kosten unter einer vorgegebenen Schranke liegen.

gegeben: zusammenhängender, gewichteter Graph (oft vollständiger Graph)

gesucht: kürzester Weg, der alle Knoten genau einmal (falls ein solcher Pfad vorhanden) besucht (und zum Ausgangsknoten zurückkehrt)<br\>

auch genannt: kürzester Hamiltonkreis

- durch psychologische Experimente wurde herausgefunden, dass Menschen (in 2D) ungefähr proportionale Zeit zur Anzahl der Knoten brauchen, um einen guten Pfad zu finden, der typischerweise nur <math>\lesssim 5%</math> länger als der optimale Pfad ist<br\>

vorgegeben: Startknoten (kann willkürlich gewählt werden), vollständiger Graph

=> v-1 Möglichkeiten für den ersten Nachfolgerknoten => je v-2 Möglichkeiten für dessen Nachfolger...

also <math>\frac{(v-1)!}{2}</math> mögliche Wege in einem vollständigen Graphen

• Ein naiver Ansatz zur Lösung des TSP Problems ist das erschöpfende Durchsuchen des Graphen, auch "brute force" Algorithmus ("mit roher Gewalt"), indem alle möglichen Rundreisen betrachtet werden und schließlich die mit den geringsten Kosten ausgewählt wird.
• Dieses Verfahren versagt allerdings bei größeren Graphen, aufgrund der hohen Komplexität.

Approximationsalgorithmus

Für viele Probleme in der Praxis sind keine effizienten Algorithmen bekannt (NP-schwer). Diese (z.B. TSP) werden mit Approximationsalgorithmen berechnet, die effizient berechenbar sind, aber nicht unbedingt die optimale Lösung liefern. Beispielsweise ist es relativ einfach, eine Tour zu finden, die höchstens um den Faktor zwei länger ist als die optimale Tour. Die Methode beruht darauf, dass einfach der minimale Spannbaum ermittelt wird.

Approximationsalgorithmus für TSP<br\>

• TSP für n Knoten sei durch Abstandsmatrix D = <math>(d_{ij}) 1 \le i, j \le n</math>

gegeben (vollständiger Graph mit n Knoten, <math>d_{ij}</math> = Kosten der Kante (i,j)) <br\>

gesucht: Rundreise mit minimalen Kosten. Dies ist NP-schwer!<br\>

• D erfüllt die Dreiecksungleichung <math> \Leftrightarrow d_{ij} + d_{jk} \geq d_{ik} \text{ fuer } \forall{i, j, k} \in \lbrace 1, ..., n \rbrace</math> <br\>
• Dies ist insbesondere dann erfüllt, wenn D die Abstände bezüglich einer Metrik darstellt oder D Abschluss einer beliebigen Abstandsmatrix C ist, d.h. :<math>d_{ij}</math> = Länge des kürzesten Weges (bzgl. C) von i nach j.

• Die ”Qualität”der Lösung mit einem Approximationsalgorithmus ist höchstens um einen konstanten Faktor schlechter ist als die des Optimums.

Systematisches Erzeugen aller Permutationen

• Allgemeines Verfahren, wie man von einer gegebenen Menge verschiedene Schlüssel - in diesem Fall: Knotennummern - sämtliche Permutationen systematisch erzeugen kann. <br\>
• Trick: interpretiere jede Permutation als Wort und betrachte dann deren lexikographische ("wie im Lexikon") Ordnung.<br\>
• Der erste unterschiedliche Buchstabe unterscheidet. Wenn die Buchstaben gleich sind, dann kommt das kürzere Wort zuerst.

gegeben: zwei Wörter a, b der Länge n=len(a) bzw. m=len(b). Sei k = min(n,m) (im Spezialfall des Vergleichs von Permutationen gilt k = n = m)<br\> Mathematische Definition, wie die Wörter im Wörterbuch sortiert sind: <br\>

<math>a<b \Leftrightarrow

\begin{cases} n < m & \text{ falls fuer } 0 \le i \le k-1 \text{ gilt: } a[i] = b[i] \\ a[j] < b[j] & \text{ falls fuer } 0 \le i \le j-1 \text{ gilt: } a[i] = b[i], \text{ aber fuer ein } j<k: a[j] \ne b[j] \end{cases}</math><br\>

Algorithmus zur Erzeuguung aller Permutationen:

1. beginne mit dem kleinsten Wort bezüglich der lexikographischen Ordnung => das ist das Wort, wo a aufsteigend sortiert ist
2. definiere Funktion "next_permutation", die den Nachfolger in lexikographischer Ordnung erzeugt

Beispiel: Die folgenden Permutationen der Zahlen 1,2,3 sind lexikographisch geordnet

1 2 3    6 Permutationen, da 3! = 6
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
-----
0 1 2 Position

Die lexikographische Ordnung wird deutlicher, wenn wir statt dessen die Buchstaben a,b,c verwenden:

abc
acb
bac
bca
cab
cba

Eine Funktion, die aus einer gegebenen Permutation die in lexikographischer Ordnung nächst folgende erzeugt, kann wie folgt implementiert werden:

def next_permutation(a):
	i = len(a) -1  #letztes Element; man arbeitet sich von hinten nach vorne durch
	while True:  # keine Endlosschleife, da i dekrementiert wird und damit irgendwann 0 wird
		if i <= 0: return False  # a ist letzte Permutation
		i -= 1
		if a[i]<a[i+1]: break
	#lexikogr. Nachfolger hat größeres a[i]
	j = len(a)
	while True:
		j -= 1
		if a[i] < a[j]: break
	a[i], a[j] = a[j], a[i] #swap a[i], a[j]
	#sortiere aufsteigend zwischen a[i] und Ende
	#zur Zeit absteigend sortiert => invertieren
	i += 1
	j = len(a) -1
	while i < j:
		a[i], a[j] = a[j], a[i]
		i += 1
		j-= 1
	return True  # eine weitere Permutation gefunden
 	
 def naiveTSP(graph):
	start = 0
	result = range(len(graph))+[start]
	rest = range(1,len(graph))
	c = pathCost(result, graph)
	while next_permutation(rest):
		r = [start]+rest+[start]
		cc = pathCost(r, graph)
		if cc < c:
			c = cc
			result = r
		return c, result

Komplexität: <math>(v-1)!</math> Schleifendurchläufe (=Anzahl der Permutationen, da die Schleife abgebrochen wird, sobald es keine weiteren Permutationen mehr gibt), also <math>O(v!) = O(v^v)</math>

Beispiel

i = 0			j = 3
↓			↓
1	4	3	2	#input für next_permutation
	i = 2		j = 3
	↓		↓
2	4	3	1	# vertauschen der beiden Elemente
		i = 2
		j = 2
		↓
2	1	3	4	#absteigend sortiert

Stirling'sche Formel

Wikipedia (de) (en)

Die Stirling-Formel ist eine mathematische Formel, mit der man für große Fakultäten Näherungswerte berechnen kann. Die Stirling-Formel findet überall dort Verwendung, wo die exakten Werte einer Fakultät nicht von Bedeutung sind. Damit lassen sich durch die Stirling'sche Formel z.T. starke Vereinfachungen erzielen. <math>v! \approx \sqrt{2 \pi v} \left(\frac{v}{e}\right)^v</math>

<math>O(v!) = O\left(\sqrt{v}\left(\frac{v}{e}\right)^v\right) \approx O(v^v)</math>

Erfüllbarkeitsproblem

geg.:

• n Boolsche Variablen <math>x_i \in \{True,False\}</math> und deren Negation <math>\neg x_i (i=1..n)</math>
• Logischer Ausdruck in <math>x_i,\neg x_i</math>
  • zB <math>(x_1 \vee x_2) \wedge (x_3 \vee x_4)</math> ...

   Grammatik eines logischen Ausdrucks(in BNF):
   <EXP>  ::= <DISJ>
   <DISJ> ::= <CONJ> | <DISJ> <math>\vee</math> <CONJ>
   <CONJ> ::= <TERM> | <CONJ> <math>\wedge</math> <TERM>
   <TERM> ::= ( <EXPR> ) | ¬( <EXPR> ) | <VAR> | ¬<VAR>
   <VAR>  ::= <math>x_1</math> | ... | <math>x_n</math>

ges.: Eine Belegung der <math>x_i</math>, so dass der gegebene Ausdruck "True" wird

Naive Lösung

Probiere alle Bedingungen aus <math>\to</math> Komplexität <math>\mathcal{O}(2^{n}) \!</math>
Im Allgemeinen ist das der effizienteste bekannte Algorithmus

Normalformen von logischen Ausdrücken

k-Konjunktionen-Normalform(k-CNF)

• ein "Literal" ist eine Variable <math>x_i</math> oder deren Negation
• jeweils k Literale werden mit <math>\vee</math> in einer Disjunktion verknüpft
• Disjunktionen werden mit <math>\wedge</math> in einer Konjunktion verbunden

   Grammatik eines Ausdrucks in k-CNF(wieder in BNF):
   <EXP>  ::= <CONJ>
   <CONJ> ::= <DISJ> | <CONJ> <math>\wedge</math> <DISJ>
   <DISJ> ::= ( <LIT> <math>\vee</math> ... <math>\vee</math> <LIT> ) <!-- k Literale -->
   <LIT>  ::=  <VAR> | <math>\neg</math><VAR> 
   <VAR>  ::= <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> ...

Satz:

• Jeder logische Ausdruck kann in polynomieller Zeit in 3-CNF umgewandelt werden
• Im Allgemeinen kann ein logischer Ausdruck nicht in 2-CNF umgeschrieben werden

Implikationen-Normalform(INF)

Konjunktionen von Implikationen:

• zB <math>(x_1 \to x_2) \wedge (x_2 \to \neg x_3) \wedge (x_4 \to x_3)</math>

   Grammatik eines Ausdrucks in INF(you know the drill ;)):
   <EXP>  ::= <CONJ>
   <CONJ> ::= <IMPL> | <CONJ> <math>\wedge</math> <IMPL>
   <IMPL> ::= ( <LIT> <math>\to</math> <LIT> )
   <LIT>  ::=  <VAR> | <math>\neg</math><VAR> 
   <VAR>  ::= <math>x_1</math> | ... | <math>x_n</math> 

Satz:

• jeder Ausdruck in 2-CNF kann in INF umgewandelt werden (siehe z.B. hier):

  <math> (x_i \vee x_j) \Leftrightarrow (\neg x_i \to x_j) \Leftrightarrow (\neg x_j \to x_i) </math>

Beachten Sie, dass beide Implikationen in die Normalform eingefügt werden müssen, um die Symmetrie des Problems zu erhalten. Aus <math>(x_i \vee x_j)</math> wird also <math>(\neg x_i \to x_j) \wedge (\neg x_j \to x_i)</math>.

Außerdem kann jeder Ausdruck in INF als gerichteter Graph dargestellt werden

1. Jede Variable und ihre Negation sind jeweils 1 Knoten (d.h. 2n Knoten insgesamt).
2. Jede Implikation ist eine gerichtete Kante.

Stark zusammenhängende Komponenten

geg.: gerichteter Graph

   1. Bestimme die post Order Time (mit Tiefensuche)
   2. Transponieren des Graphen <math>G^T</math>
   3. Bestimme ConnComp <math>G^T</math> mit bekannten CC Algorithmen, aber so, dass Knoten in absteigender post Order behandelt werden

Beweis: 1.Bilde Komponentengraphen:

   Knoten: jede SCC <math>C_i</math> ist ein Knoten
   Kanten: <math>C_i \rightarrow C_j \Leftrightarrow U_k \rightarrow U_l</math> mit <math>U_k \in C_i</math> und <math>U_l \in C_j</math>

   *Eigenschaft 1: der Komponentengraph ist :azyklisch:
    <math>pot \left(C_i\right) = max_{U_k \in C_i}  pot\left(U_k\right)</math>
   
   *Eigenschaft 2: falls <math>C_i \rightsquigarrow C_j</math> dann <math>pot \left(C_i\right) > pot \left(C_j\right)</math>
    (ausserdem gilt: es gibt keinen Weg <math>C_j \rightsquigarrow C_i</math> )
    aber: in transponierten Graphen sind alle Kanten umgedreht
   
   *Eigenschaft 3: falls <math>{C_j}^T \rightsquigarrow {C_i}^T</math> , dann gilt <math>pot \left({C_i}^T\right) > pot \left({C_j}^T\right)</math>

Eigenschaft 2-3 <math>\Longrightarrow</math> im transponierten Graphen gibt es nie einen Pfad <math>{C_i}^T \rightsquigarrow {C_j}^T</math>

Falls <math>pot \left({C_i}^T\right) > pot \left({C_j}^T\right)</math>

<math>\Longrightarrow</math> Schritt 3 des Algorithmus kann von einem geg. Startknoten nur die Knoten derselben SCC erreichen

q.e.d.

postOrderTime

   ## In einem Baum: besuche erst die Kinder, dann die Wurzel
   def postOrderTime(graph):
       visited = [None] * len(graph) 
       def visit(node, count):
           #markiert, dass 'node' besucht wurde, aber noch nicht fertig ist
           visited[node] = -1
           for  neighbor in graph[node]:
               if visited[neighbor] is not None: continue
               count = visit(neighbor, count)
           visited[node] = count
           count += 1
           return count
       count = 0
       for node in range(len(graph)):
           if visited[node] is not None: continue
           count = visit(node, count)
       return visited

transpose

   ## Kehre die Richtung der Pfeile in einem Graphen um (tut nichts fuer ungerichtete Pfeile und Graphen).
   def transpose(graph):
       grapht = [[] for k in range(len(graph))]
       for node in range(len(graph)):
           for neighbor in graph[node]:
               grapht[neighbor].append(node)
       return grapht

strongCC

   ## Jede Komponente durch e. Ankerknoten repräsentiert
   ## Jedes SCC ist die Menge aller Knoten mit identischem Ankterknoten
   def strongCC(graph):
       # Prinzip: Tiefensuche mit absteigender Post-Order-Time
       postOrder = postOrderTime(graph)
       # ordered = [(knotenindex, POT), ...]
       ordered = zip(range(len(graph)), postOrder)
       ordered.sort(key=lambda x: x[1], reverse=True)
       
       grapht = transpose(graph)
       anchors = [None] * len(graph)
       def visit(node, anchor):
           if anchors[node] is not None: return
           anchors[node] = anchor
           for neighbor in grapht[node]:
               visit(neighbor, anchor)
       
       for node in ordered:
           visit(node[0], node[0])
       return anchors

Anwendung auf 2-SAT Problem

geg.: Implikationen-Normalform, dargestellt als gerichteter Graph.

Eigenschaft: alle Variablen in derselben SCC müssen den gleichen Wert haben, weil

<math>\underbrace{x_i \rightsquigarrow x_j \stackrel{\wedge}{=} x_i \rightarrow x_j; \;\;\; x_j \rightsquigarrow x_i \stackrel{\wedge}{=} x_j \rightarrow x_i}</math>

<math>\;\;\;x_i == x_j</math>

<math>\rightarrow \; x_i \; und \; \neg x_i</math> dürfen nie in derselben SCC sein, weil <math>x_i == \neg x_i</math> ein Widerspruch ist

<math>\Longrightarrow</math> Algorithmus für Erfüllbarkeit von INF: teste diese Eigenschaft für jede stark zusammenhängende Komponente des Implikationengraphen

Das funktioniert leider nicht für k-SAT mit <math>k>2</math>

Wichtige Algorithmen, die in der Vorlesung nicht behandelt werden

• Max Flow (zur Bestimmung des maximalen Flusses durch ein Netzwerk, z.B. bei Ölpipelines)
• Matching (auch Paarung genannt): Teilmenge der Kanten eines Graphen, wobei keine zwei Kanten einen gleichen Knoten besitzen

  Anwendungsbereiche: Zuordnung von Gruppen, z.B. Arbeitsamt (Zuordnung Arbeitssuchender - Stellenangebot), Universität (Zuordnung Studenten - Übungsgruppen)

Nächstes Thema