Typen von Graphen und Anwendungen

In diesem Kapitel werden Graphen behandelt. Ein Graph ist das mathematische Modell eines Netzwerks bestehend aus Knoten und Kanten. Graphen haben einen vielfältigen Einsatz. So kommen sie bei Verbindungsnetzwerken (Bahnnetz, Flugververbindungen, Straßenkarten, ...), Verweisen (WWW, Literaturverweise, Wikipedia, symbolische Links, ...), Technischen Modellen (Platinen-layout, finite Elemente, Computergrafik) und Software Reengineering und - dokumentation zum Einsatz. Bäume und Listen sind spezielle Graphen.

Ungerichteter Graph

Es gibt verschiedene Typen von Graphen. Der ungerichtete Graph ist beispielsweise eine Straßenverbindung, eine Telefonnetz oder ein soziales Netzwerk. Ein ungerichteter Graph ist ein Tupel G=(V,E). Wir haben eine endliche Menge V von Knoten (Vertices) und eine Menge E von Kanten (Edges), die aus ungeordneten Paaren aus V besteht. Es gilt, dass $E\subseteq VxV$ und jedes $e\in E$ ist eine zweielementige Teilmenge der Knotenmenge $V(e={a,b}{\text{ mit }}a,b\in V)$ . Im ungerichteten Graphen gibt es keine Schleifen, das heißt es gibt keine Kanten die von einem Knoten zu sich selbst laufen. Außerdem gibt es keine mehrfachen Kanten zwischen zwei Knoten, Parallelkanten genannt.

$V=\{1,2,3,4,5,6,7\}$

$E=\{\{1,2\},\{1,3\},\{1,4\},\{2,6\},\{3,4\},\{3,5\},\{3,6\},\{4,6\},\{5,6\}\}$

Hier können zum Beispiel die kürzesten Wege bei sozialen Netzwerken wie Facebook berechnet werden.

Spezielle Graphen

Sei $G=(V,E)$ ein Graph.

G heißt planar, falls er ohne Überschneidungen der Kanten in der Ebene gezeichnet werden kann.

G heißt vollständig, falls $E=V\times V$

G heißt regulär, falls alle Knoten denselben Grad haben

G heißt bipartit, falls $V=V_{1}\cup V_{2}$ und

- keine zwei Knoten in $V_{1}$ sind adjazent
- keine zwei Knoten in $V_{2}$ sind adjazent

Beispiele

Dieser Graph ist sowohl planar, regulär als auch vollständig.

Dieser Graph ist jedoch nur regulär und vollständig.

Hier handelt es sich nur um einen regulären Graphen.

Dies ist ein Beispiel für einen bipartiten Graph.

Gerichteter Graph

Der gerichtete Graph ist beispielsweise eine Förderanlage oder ein Kontrollfluss in Programmen. Der gerichtete Graph (auch Digraph) ist ein Tupel G=(V,E) mit V als endliche Menge von Knoten und E einer Menge von Kanten, geordneten Paaren aus V. Jedes $e\in E$ ist nun ein Tupel e=(a,b) mit $a,b\in V$ . Schleifen der Form (a,a) sind nun erlaubt. Dazu ist (a,b) eine andere Kante als (b,a). Der Unterschied zwischen (a,b) und {a,b} besteht darin, dass das Tupel (a,b) geordnet ist. Die Reihenfolge kann nicht verändert werden. Hingegen ist {a,b} eine Menge, in der die Reihenfolge der Elemente keine Rolle spielt.

$G_{g}=(V_{g},E_{g})$

$V_{g}=\{1,2,3,4,5,6\}$

$E_{g}=\{(1,2),(1,3),(3,1),(3,4),(3,6),(4,1),(5,3),(5,5),(6,2),(6,4),(6,5)\}$

Gerichtete Graphen werden zum Beispiel als Web-Graph (Google`s PageRank) benutzt. Aber auch in der Scientometrie kommen sie zum Einsatz bei der Impact Faktoren Berechnung. Bei Datenstrukturen im Semantik Web werden gerichtete Graphen zum Speichern von Daten genutzt.

Gerichtete und ungerichtete Graphen

Ein ungerichteter Graph kann in einen gerichteten Graphen transformiert werden, indem jede ungerichtete Kante {v,w} durch zwei gerichtete Kanten (v,w) und (w,v) ersetzt wird. Dann ist beispielsweise der Zusammenhang identisch mit dem starken Zusammenhang. Dazu haben gerichtete Graphen eine größere Ausdrucksstärke und daher wird "Graph" oft als Synonym für einen Digraph verwendet.

Gewichteter Graph

Ein ungerichteter gewichteter Graph ist beispielsweise eine Flugverbindung mit Meilen oder Kosten, ein Straßennetz mit Kilometern oder ein Rohrsystem mit Durchfluss.

Ein gerichteter gewichteter Graph ist beispielsweise ein Straßennetz mit Einbahnstraßen, Rohre mit Ventilen oder ein Förderband.

Der Graph ist ein Paar G=(V,E) und wir haben eine Kantengewichtsfunktion g. Daraus erhalten wir G=(V,E,g) mit  $g:E\to \mathbb {N}$ . Der Graph kann gerichtet oder ungerichtet sein und die Kantengewichte müssen nicht notwendigerweise natürliche Zahlen sein.

Ungerichtete gewichtete Graphen kommen zum Beispiel bei der Navigation beim Berechnen des kürzesten Weges zum Einsatz.

Gerichtete gewichtete Graphen kommen bei der Optimierung in der Telekommunikation zum Einsatz.

Hypergraph

Es gibt aber noch viele weitere Varianten von Graphen wie Multigraphen oder Hypergraphen.

Ein Hypergraph ist ein Paar G=(V,E) mit einer Menge von Knoten V und einer Menge von Hyperkanten $E\subseteq 2^{V}$ .

Definitionen

Hier werden allgemeine Definitionen bezüglich der Graphen behandelt. Dazu werden immer wieder Beispiele gebracht, die sich auf folgende Graphen beziehen. Dabei gilt je nach Beispiel G=(V,E) entweder für den ungerichteten oder den gerichteten Graphen.

Adjazenz

Ungerichteter Graph

Zwei Knoten $v,w\in V$ heißen adjazent, falls $\{v,w\}\in E$ .

Hier heißt v auch Nachbar von w.

Beispiel:

Knoten 1 und 3 sind adjazent

Gerichteter Graph

Zwei Knoten $v,w\in V$ heißen adjazent, falls $(v,w)\in E$ oder $(w,v)\in E$ .

Für $(v,w)\in E$ heißt w Nachfolger von v und v Vorgänger von w.

Beispiele:

Knoten 1 ist Vorgänger zu Knoten 3
Knoten 4 ist Nachfolger zu Knoten 6

Inzidenz

Ungerichteter Graph

Eine Kante $\{v,w\}\in E$ ist inzident zu einem Knoten $z\in V$ , falls $v=z$ oder $w=z$ .

Gerichteter Graph

Eine Kante $(v,w)\in E$ ist inzident zu einem Knoten $z\in V$ , falls $v=z$ oder $w=z$ .

Grad

Ungerichteter Graph

Der Grad (engl. degree) eines Knotens $v\in V$ ist die Anzahl seiner inzidenten Kanten, das heißt: $degree(v)=|\{\{w,x\}\in E|w=v{\text{ oder }}x=v\}|$ .

Beispiel:

Der Grad von Knoten 4 ist 3

Gerichteter Graph

Der Eingangsgrad (engl. in-degree) eines Knotens $v\in V$ ist die Anzahl seiner Vorgänger: $indeg(v)=|\{(w,v)\in E\}|$ .

Der Ausgangsgrad (engl. out-degree) eines Knotens $v\in V$ ist die Anzahl seiner Nachfolger: $outdeg(v)=|\{(v,w)\in E\}|$ .

Beispiele:

Der Eingangsgrad von Knoten 3 ist 2
Der Ausgangsgrad von Knoten 3 ist 3

Weg

Ungerichteter Graph

Ein Weg W ist eine Sequenz von Knoten $W=(v_{1},...,v_{n})$ mit $v_{1},...,v_{n}\in V$ für die gilt: $\{v_{i},v_{i+1}\}\in E{\text{ für alle }}i=1,...,n-1$

Beispiel:

(1,3,5,6,3,4) ist ein Weg

Gerichteter Graph

Ein (gerichteter) Weg W ist eine Sequenz von Knoten $W=(v_{1},...,v_{n}){\text{ mit }}v_{1},...,v_{n}\in V{\text{, für die gilt: }}(v_{i},v_{i+1})\in E{\text{ für alle }}i=1,...,n-1$ .

Beispiel:

(1,3,6,5,5,3,1) ist ein (gerichteter) Weg

Pfad

Ein Weg W heißt Pfad, falls zusätzlich gilt $v_{i}\neq v_{j}{\text{ für alle }}i,j=1,...,n{\text{ mit }}i\neq j$ . Das heißt, der Weg enthält keine doppelten Knoten. Diese Definition gilt sowohl für ungerichtete als auch gerichtete Graphen.

Beispiel:

(1,4,6,5) ist ein Pfad

Kreis

Ein Weg P heißt Kreis, falls $v_{1}=v_{n}$ . Dazu ist ein Kreis K elementar, falls $v_{i}\neq v_{j}{\text{ für alle }}i,j=1,...,n-1{\text{ mit }}i\neq j$ . Der Kreis enthält also keine doppelten Knoten bis auf den Anfangs- und den Endpunkt. Diese Definition gilt sowohl für ungerichtete als auch gerichtete Graphen.

Beispiel:

(1,3,4,6,3,4,1) ist ein Kreis
(3,4,6,3) ist ein elementarer Kreis

Länge

Die Länge eines Weges ist die Anzahl der durchlaufenen Kanten. Die Länge eines Pfades ist also n-1. Diese Definition gilt sowohl für ungerichtete als auch gerichtete Graphen.

Beispiel:

Die Länge von (3,4,6,3,4,1) ist 4
Die Länge von (1,3,6) ist 2

Teilgraph

Ungerichteter Graph

Ein Graph $G'=(V',E')$ heißt Teilgraph von G, falls $V'\subseteq V{\text{ und }}E'\subseteq E\cap (V'\times V')$ .

Beispiel:

G'=({3,4,6},{{3,4},{4,6}}) ist ein Teilgraph von G

Gerichteter Graph

Ein Graph $G'=(V',E')$ heißt Teilgraph von G, falls $V'\subseteq V$ und $E'\subseteq E\cap (V'\times V')$ .

Beispiel:

$G'=(\{1,3,4\},\{(1,3),(4,1)\})$ ist ein Teilgraph von $G_{g}$ .

Erreichbarkeit

Ungerichteter Graph

Ein Knoten $w\in V$ heißt erreichbar von einem Knoten $v\in V$ , falls ein Weg $W=(v_{1},...,v_{n})$ existiert mit $v_{1}=v$ und $v_{n}=w$ .

Beispiele:

Knoten 6 ist erreichbar von Knoten 1
Knoten 7 ist nicht erreichbar von Knoten 1

Gerichteter Graph

Ein Knoten $w\in V$ heißt erreichbar von einem Knoten $v\in V$ , falls ein Weg $W=(v_{1},...,v_{n})$ existiert mit $v_{1}=v$ und $v_{n}=w$ .

Beispiele:

Knoten 6 ist erreichbar von Knoten 1
Knoten 5 ist nicht erreichbar von Knoten 2

Zusammenhang

Ungerichteter Graph

G heißt (einfach) zusammenhängend, falls für alle $v,w\in V$ gilt, dass w von v erreichbar ist

Ein Teilgraph $G'=(V',E')$ von G heißt Zusammenhangskomponente von G, falls G' zusammenhängend ist und kein Teilgraph $G''=(V'',E'')$ von G existert mit $V'\subset V''$ .

Beispiele:

G ist nicht zusammenhängend
Der Teilgraph $G''=(V'',E''){\text{ mit }}V''=\{1,2,3,4,5,6\}{\text{ und }}E''=\{\{1,2\},\{1,3\},\{1,4\},\{2,6\},\{3,4\},\{3,5\},\{3,6\},\{4,6\},\{5,6\}\}$ ist eine Zusammenhangskomponente von G
Der Teilgraph $G'''=(\{7\},\emptyset )$ ist eine Zusammenhangskomponente von G

Gerichteter Graph

G heißt (stark) zusammenhängend, falls für alle $v,w,\in V$ gilt, dass w von v und v von w erreichbar ist.

Ein Teilgraph $G'=(V',E')$ von G heißt starke Zusammenhangskomponente von G, falls $G'$ stark zusammenhängend ist und kein Teilgraph $G''=(V'',E'')$ von G existiert mit $V'\subset V''$ .

Beispiel:

Der Teilgraph $G''=(V'',E'')$ mit $V''=\{1,3,4,5,6\}$ und $E''=\{(1,3),(3,1),(3,4),(3,6),(4,1),(5,3),(5,5),(6,4),(6,5)\}$ ist eine starke Zusammenhangskomponente von $G_{g}$ .

Repräsentation von Graphen

Auf dieser Seite wird die Repräsentation von Graphen behandelt. Wir fragen uns wie effizient die Datenstruktur für Graphen ist.

Kanten- und Knotenlisten

Bei durchnummerierten Knoten erfolgt eine einfache Realisierung. Historisch gesehen ist es die erste verwendete Datenstruktur. Außerdem ist sie als Austauschformat geeignet und die Auflistung ist nach Knoten oder nach Kanten sortiert.

Beispiel Kantenliste

Gegeben ist eine Kantenliste für $G_{g}:$

Die erste Zahl (6) steht für die Knotenzahl. Die zweite Zahl (11) steht für die Kantenzahl. Die weiteren Paare (1,2 ; 1,3...) stehen für die Kanten.

6,11,1,2,1,3,3,1,4,1,3,4,3,6,5,3,5,5,6,5,6,2,6,4

Beispiel Knotenliste

Gegeben ist eine Knotenliste für $G_{g}:$

6,11,2,2,3,0,3,1,4,6,1,1,2,3,5,3,2,4,5 Die Teilfolge 2,2,3 bedeutet, dass der Knoten 1 den Ausgangsgrad 2 hat und herausgehende Kanten zu den Knoten 2 und 3.

Vergleich Kanten-und Knotenliste

Falls ein Graph mehr Kanten als Knoten hat (=„Normalfall“),benötigen Knotenlisten weniger Speicherbedarf als Kantenlisten. Das bedeutet für die Kantenlisten gilt $2+2|E|$ und für die Knotenliste gilt $2+|V|+|E|$ .

Adjazenzmatrix

Adjazenz bedeutet berühren oder aneinander grenzen. Hier werden die Graphen als Boole‘sche Matrix dargestellt. 1-Einträge werden für direkte Nachbarschaften verwendet. A ist eine Adjazenzmatrix für den Graph $G=(V,E):(A_{ij})=1~genau~dann~wenn~(i,j)\in E$

Beispiel

Eigenschaften

Bei ungerichteten Graphen reicht eine Halbmatrix (ein Dreieck) aus. Bei gewichteten Graphen werden Gewichte statt Boolsche Werte genutzt. Der Vorteil einer Adjazenzmatrix ist, dass einige Graphenoperationen als Matrixoperation möglich sind. So ist sie beispielsweise durch iterierte Matrixmultiplikation erreichbar und besitzt schöne Eigenschaften für die mathematische Analyse.

So sieht die Darstellung als Dreiecksmatrix aus. Die Diagonale kann ebenfalls weggelassen werden, wenn Schleifen verboten sind.

Adjazenzliste

Wir haben eine Liste der 3b oder alternativ ein Array. Pro Knoten werden die von ihm ausgehenden Kanten als Liste, welche besonders geeignet für dünn besetzte Matrizen sind, oder als Array von Zeigern dargestellt. Der Graph wird durch |V|+1 verkettete Listen realisiert. In Adjazenzlisten sind dynamische Erweiterungen im Sinne verketteter Listen erlaubt. Knotenlisten können natürlich auch als verkettete Listen realisiert werden.

Speicherbedarf

Seien n=|V| und m=|E|. Benötigt werden insgesamt $n+\sum _{i=1}^{n}ag(i)=n+m$ Listenelemente. ag(i) ist die Anzahl der Nachbarn von i (gerichtet).

Transformation zwischen den Darstellungen

Die vorgestellten Realisierungsvarianten sind äquivalent. Jede Darstellung kann in jede andere ohne Informationsverlust transformiert werden. Dafür wird die eigene Darstellung ausgelesen und anschließend die andere Darstellung erzeugt. Der Aufwand dieser Transformationen variiert von O(n+m) bis $O(n^{2})$ wobei im schlechtesten Fall $m=n^{2}$ gilt. $n^{2}$ tritt immer auf, wenn eine naive Matrixdarstellung beteiligt ist. Nicht naive Darstellungen sind für sehr dünn besetzte Matrizen nötig.

Komplexitätsbetrachtung

Bei Kantenlisten ist das Einfügen von Kanten (Anhängen von zwei Zahlen) und von Knoten (Erhöhung der ersten Zahl um 1) besonders günstig. Das Löschen von Kanten zieht das Verschieben der nachfolgenden Kanten mit sich und die Knoten müssen neu nummeriert werden.

Bei Knotenlisten ist das Einfügen von Knoten, also die Erhöhung der ersten Zahl und das Anhängen einer 0, günstig.

Bei der Matrixdarstellung ist das Manipulieren von Kanten sehr effizient ausführbar. Der Aufwand beim Knoteneinfügen hängt von der Realisierung ab. Im worst case wird die Matrix in eine größere Matrix kopiert.

Bei Adjazenzlisten gibt es unterschiedlichen Aufwand, je nachdem, ob die Knotenliste ein Feld mit Direktzugriff oder eine verkettete Liste mit sequenziellem Durchlauf realisiert.

Operation	Kantenliste	Knotenliste	Adjazenzmatrix	Adjazenzliste
Einfügen Kanten	Beta(1)	O(n+m)	O(1)	O(1)/O(n)
Löschen Kanten	O(m)	O(n+m)	O(1)	O(n)
Einfügen Knoten	O(1)	O(1)	$O(n^{2})$	O(1)
Löschen Knoten	O(m)	O(n+m)	$O(n^{2})$	O(n+m)

Das Löschen eines Knotens impliziert für gewöhnlich auch das Löschen der dazugehörigen Kanten.

Datenstrukturen für Graphen

Auf dieser Seite werden die Datenstrukturen für Graphen behandelt. In Java gibt es keine hauseigene Graphimplementierung, aber es gibt diverse Pakete für verschiedene Anwendungen.

Jung (http://jung.sourceforge.net)

Graph<Integer, String> g = new SparseMultigraph<Integer, String>(); 
g.addVertex((Integer)1); 
g.addVertex((Integer)2); 
g.addEdge("Edge1", 1, 2);

Neo4j (http://www.neo4j.org)

GraphDatabaseService= new 
"GraphDatabaseFactory().newEmbeddedDatabase(“PATH”); 
Transaction tx = graphDb.beginTx(); 
try{ 
   Node firstNode = graphDb.createNode(); 
   Node secondNode = graphDb.createNode(); 
   Relationship relationship = firstNode.createRelationshipTo(secondNode, 
    … ); 
   tx.success(); 
}finally{ 
   tx.finish(); 
}

Die allgemeine Schnittstelle für die Vorlesung ist:

 public interface Graph {
   public int addNode();
   public boolean addEdge (int orig, int dest);
}

Implementierung Adjazenzliste

 public class AdjazenzListGraph implements Graph {
   private int [][] adjacencyList=null;

   //Knoten hinzufügen:
   public int addNode() {
      int nodeNumber = (adjacencyList ==null)?0: adjacencyList.length;
      int [][] newAdjacencyList= new int [nodeNumber+1][];
      //alte adjacencyList kopieren
      for (int i=0; i< nodeNumber; i++) 
         newAdjacencyList [i]=adjacencyList[i];
      //neuer Knoten hat noch keine Kanten
      newAdjacencyList[nodeNumber] =null; 
      adjacencyList=newAdjacencyList;
      return nodeNumber+1;
   }

   //Kante hinzufügen:
   public boolean addEdge (int orig, int dest){
      int nodeNumber = (adjacencyList == null)? 0: adjacencyList.length;
      if (orig > nodeNumber || dest > nodeNumber || orig < 1 || dest < 1 )
         return false;
      if (adjacencyList[orig-1] != null)
         for (int n : adjacencyList[orig-1])
            //Kante bereits vorhanden?
            if (n==dest) return false; 
      //Erste Kante am Knoten orig?
      if ( adjacencyList[orig-1] == null ) { 
         adjacencyList [orig-1] = new int[1];
         adjacencyList[orig-1][0]=dest;
      }  
      else {
         int[] newList= new int[adjacencyList[orig-1].length+1];
         System.arraycopy(adjacencyList[orig-1],0,newList,0,adjacencyList[orig-1].length);
         newList[adjacencyList[orig-1].length]=dest;
         adjacencyList [orig-1]=newList;
      }
      return true;
   }
}

Breitensuche

Auf dieser Seite behandeln wir die Breitensuche. Wir fragen uns wie man die Knoten eines Graphen effizient aufzählt. Die Lösung ist der Breitendurchlauf ( Breadth-First-Search, BFS). Dabei werden die Knoten eines Graphen nach der Entfernung vom Zielknoten aufgezählt. Eine andere Methode ist der Tiefendurchlauf, zu dem kommen wir aber später. Bei dem Breitendurchlauf für ungerichtete Graphen gibt es eine Warteschlange als Zwischenspeicher. Farbmarkierungen beschreiben den Status der Knoten. Weiß bedeutet er ist unbearbeitet, grau bedeutet er ist in Bearbeitung und schwarz bedeutet, dass er abgearbeitet ist. Pro Knoten wird die Entfernung zum Startknoten berechnet. Bei der Initialisierung wird der Startknoten in eine Warteschlange eingefügt, die Farbe auf grau gesetzt und die Entfernung mit 0 berechnet. Die anderen Knoten haben eine unendliche Entfernung und sind weiß markiert.

Beim Breitendurchlauf wird der aktuelle Knoten k aus der Warteschlange genommen und schwarz gefärbt. Alle von k aus erreichbaren weißen Knoten werden grau gefärbt, die Entfernung ist der Entfernungswert von k+1 und sie werden in der Warteschlange aufgenommen.

Algorithmus

Ergänzung zum Graph-Interface:

public interface Graph{
   public int addNode();
   public boolean addEdge(int orig, int dest);
   public Collection<Integer> getChildren(int node);!
}

Breitendurchlauf als Iterator:

public class BfsIterator implements Iterator<Integer>{
   private Graph g; 
   private Queue<Integer> q;
   private Set<Integer> visited;

   public BfsIterator(Graph g, int s){
      this.g = g;
      this.q = new LinkedList<Integer>();
      q.add(s);
      this.visited = new HashSet<Integer>();
   }

   public boolean hasNext() { return !this.q.isEmpty(); }

   public Integer next() {
      Integer n = this.q.poll();
      for(Integer m: this.g.getChildren(n))
           if(!this.visited.contains(m) && !this.q.contains(m))
             this.q.add(m);
      this.visited.add(n);
      return n;
   }
}

Ausgabe aller Knoten:

//Sei g ein Graph
Iterator<Integer> it = new BfsIterator(g,1);
while(it.hasNext())
   System.out.println(it.next());

Analyse

Theorem der Terminierung

Die Breitensuche terminiert nach endlicher Zeit

Theorem der Korrektheit

Ist G zusammenhängend, so werden alle Knoten von G genau einmal besucht.

Theorem der Laufzeit

Ist G=(V,E) zusammenhängend und ist die Laufzeit von getChildren linear in der Anzahl der Kinder, so hat die Breitensuche eine Laufzeit von O(|V| + |E|).

Tiefendurchlauf

Auf dieser Seite wird der Tiefendurchlauf behandelt. Der Tiefendurchlauf wird auch Depth-First-Search, oder abgekürzt DFS, genannt. Die Knoten werden aufgezählt indem vom Startknoten aus ein Pfad so weit wie möglich verfolgt wird und bei Bedarf ein Backtracking durchgeführt wird. Bei Tiefendurchlauf werden die Knoten ebenfalls farblich markiert. Weiß bedeutet der Knoten ist noch nicht bearbeitet, grau bedeutet der Knoten ist in Bearbeitung und schwarz bedeutet der Knoten ist bereits fertig abgearbeitet.

Ergänzung zum Graph Interface:

public interface Graph{
   public int addNode();
   public boolean addEdge(int orig, int dest);
   public Collection<Integer> getChildren(int node);
   public Collection<Integer> getNodes();
}

Algorithmus

enum Color {WHITE, GRAY, BLACK};

Map<Integer,Color> color = new HashMap<Integer,Color>();
Map<Integer,Integer> pi = new HashMap<Integer,Integer>();
Map<Integer,Integer> f = new HashMap<Integer,Integer>();
Map<Integer,Integer> d = new HashMap<Integer,Integer>();

int time = 0;

color speichert die Farbe, bzw. den Bearbeitungszustand eines Knotens.

pi speichert den Vorgänger eines Knotens beim Durchlauf.

f speichert den Zeitpunkt des Bearbeitungsbeginns eines Knotens.

d speichert den Zeitpunkt des Bearbeitungsendes eines Knotens.

public void dfs(Graph g){ 
   for(Integer n: g.getNodes())
      color.put(n, Color.WHITE); 
   for(Integer n: g.getNodes())
      if(color.get(n).equals(Color.WHITE))
          dfsVisit(g,n); 
}

public void dfsVisit(Graph g, Integer n){
   color.put(n, Color.GRAY);
   time++;
   d.put(n, time);
   for(Integer m: g.getChildren(n)){
      if(color.get(m).equals(Color.WHITE)){
         pi.put(m, n);
         dfsVisit(g,m);
      } 
   }
   color.put(n, Color.BLACK);
   time++;
   f.put(n, time);
}

Vorgehen

Der Tiefendurchlauf ist ein rekursiver Abstieg. Pro Knoten haben wir zwei Werte und deren Farbwerte. Beginn der Bearbeitung ist d und Ende der Bearbeitung ist f. Der rekursive Aufruf erfolgt nur bei weißen Knoten, die Terminierung der Rekursion ist hier garantiert. Die Ausführung von DFS resultiert in einer Folge von DFS-Bäumen. Der erste Baum wird aufgebaut bis keine Knoten mehr hinzugefügt werden können. Anschließend wird ein unbesuchter Knoten gewählt und fortgefahren. Bei den Kanten des aufgespannten Baumes ist der Zielknoten beim Test weiß. An den B-Kanten ist der Zielknoten beim Test grau. Hierbei handelt es sich um Back Edges oder Rückkanten im aufgespannten Baum. Eine mit B markierte Kante zeigt einen Zyklus an. Bei F Kanten werden beim Test schwarze Knoten gefunden, dessen Bearbeitungsintervall ins Intervall des aktuellen bearbeiteten Knotens passt. Es handelt sich hierbei um Forward Edges bzw. Vorwärtskanten in dem aufgespannten Baum. Bei C Kanten haben wir schwarze Zielknoten v, dessen Intervalle nicht in das aktuelle Intervall passen (d[u]>f[v]). Hierbei handelt es sich um Cross Edges, eine Kante die zwei aufgespannte Bäume verbindet.

Beispiel

Die Notation an den Knoten ist dabei durch <Beginn der Bearbeitung d> / <Ende der Bearbeitung f> gegeben.

Analyse

Theorem der Terminierung

Die Tiefensuche terminiert nach endlicher Zeit.

Theorem der Korrektheit

Es werden alle Knoten von G genau einmal besucht.

Theorem der Laufzeit

Ist sowohl die Laufzeit von getChidlren linear in der Anzahl der Kinder als auch getNodes linear in der Anzahl der Knoten, so hat die Tiefensuche eine Laufzeit von O(|V|+|E|).

Anwendung

Der Tiefendurchlauf wird beispielsweise bei dem Test auf Zyklenfreiheit verwendet. Damit ein Graph zyklenfrei ist, darf kein Kreis K in dem Graph G vorhanden sein. Deshalb basiert dieser Test auf dem Erkennen von Back Edges. Er ist effizienter als beispielsweise die Konstruktion einer transitiven Hülle. Die Tiefensuche wird aber auch beim topologischen Sortieren verwendet. Topologisch bedeutet sortieren nach Nachbarschaft, nicht nach totaler Ordnung.

Topologisches Sortieren

Auf dieser Seite wird das topologische Sortieren behandelt. Wir fragen uns, wie Knoten unter Berücksichtigung von Abhängigkeiten aufgezählt werden können bei gegebenem azyklischem gerichteten Graph. Zur Anwendung kommt diese Sortierung bei Scheduling bei kausalen und zeitlichen Abhängigkeiten, zum Beispiel bei der Netzplantechnik. Mathematisch liegt hier eine Konstruktion einer totalen Ordnung aus einer Halbordnung vor.

Beispiel

Die sorgfältige Mutter legt ihrem Kind morgens die Kleidungsstücke so auf einen Stapel, dass das Kind nur die Kleidungsstücke vom Stapel nehmen und anziehen muss und dann richtig gekleidet ist. Hierfür legt sie die Reihenfolgebedingungen fest:

Unterhose vor Hose

Hose vor Gürtel

Unterhemd vor Gürtel

Gürtel vor Pulli

Unterhemd vor Rolli

Rolli vor Pulli

Socken vor Schuhen

Hose vor Schuhen

Uhr: egal

DFS erstellt die topologische Ordnung on the fly. Das Sortieren nach f-Wert (invers) ergibt eine korrekte Reihenfolge. Statt der expliziten Sortierung nach f werden beim Setzen des f-Wertes die Knoten vorne in eine verkettete Liste eingehängt.

18 Socken

16 Unterhose

15 Hose

14 Schuhe

10 Uhr

8 Unterhemd

7 Gürtel

5 Rolli

4 Pulli

Alternativer Durchlauf:

Berechnung kürzester Wege

Auf dieser Seite wird die Berechnung der kürzesten Wege behandelt.

Gegeben ist ein (Di-)Graph $G=(V,E,\gamma )$ mit einer Gewichtsfunktion: $\gamma :E\to \mathbb {N}$ . Der Pfad durch G ist eine Liste von aneinanderstoßenden Kanten $P=\{(v_{1},v_{2}),(v_{2},v_{3}),...(v_{n-1},v_{n})\}\subseteq E$ . Das Gewicht oder die Länge eines Pfades ist die Aufsummierung der einzelnen Kantengewichte. $w(P)=\sum _{i=1}^{n-1}\gamma ((v_{i},v_{i+1}))$ . Die Distanz zweier Punkte d(u,v) ist das Gewicht des kürzesten Pfades von u nach v.

Es existieren verschiedene kürzeste Wege Probleme.

SPSP: Single pari shortest path

Eingabe: Graph G, Startknoten s, Endknoten t

Ausgabe: Distanz d(s,t)

SSSP: Single source shortest paths

Eingabe: Graph G, Startknoten s

Ausgabe: Distanzen d(s,v) für alle Knoten v

APSP: All-pairs shortest paths

Eingabe: Graph G

Ausgabe: Distanzen d(v,w) für alle Knoten v,w

Auf den nächsten Seiten lernen wir zwei Algorithmen zum Berechnen des kürzesten Weges kennen.

Dijkstra Algorithmus

Auf dieser Seite wird der Dijkstra Algorithmus behandelt. Der Dijkstra Algorithmus wird zur Berechnung des kürzesten Weges benutzt (SSSP). Der Algorithmus stammt von 1959. Es erfolgt eine iterative Erweiterung einer Menge von günstig erreichbaren Knoten. Der Greedy Algorithmus hat eine ähnliche Breitensuche ist aber nur für nichtnegative Gewichte. Er berechnet iterativ verfeinert die Distanzwerte d(v,w) und es gibt eine Prioritätswarteschlange zum Herauslesen des jeweils minimalen Elements.

Priority Queues

Eine Priority‐Queue P ist eine dynamische Datenstruktur, die (mindestens) die folgenden Operationen unterstützt:

P.add(Element): Element hinzufügen
P.poll(): Minimalste Element zurückgeben
P.contains(Element): Enthält P das Element?

Die Ordnung zur Sortierung muss dabei vorab deﬁniert sein.

Ein Heap kann beispielsweise zur Implementierung einer Priority‐Queue benutzt werden (add‐Operation ist dann O(log n), poll‐Operation O(log n), und contains‐Operation ist O(n)). Benutzt man zusätzlich zum Heap noch einen binären Suchbaum auf denselben Element so ist auch contains in O(log n) realisierbar.

Priority Queue in Java

class DijkstraComparator implements Comparator<Integer>{
   Map<Integer,Integer> d = new HashMap<Integer,Integer>();

   public DijComparator(Map<Integer,Integer> d){
      this.d = d;
   }

   public int compare(Integer o1, Integer o2) {
      return d.get(o1).compareTo(d.get(o2));
   }
}

Ist d eine Map “Knoten”‐>”Aktueller Distanzwert von s aus”, so ist PriorityQueue<Integer> queue = new PriorityQueue<Integer>(g.getNumberOfNodes(),new DijkstraComparator(d)); eine Priority‐Queue, die bei iterativen Aufruf queue.poll() immer das Element mit dem minimalsten d‐Wert zurückliefert.

Idee

Initialisiere alle Distanzwerte von s zu v mit ∞ (und von s zu s mit 0)
Initialisiere eine Priority‐Queue Q mit allen v
Extrahiere das minimale Element $w_{min}$ aus Q
Aktualisiere alle Distanzwerte der Nachfolger von $w_{min}$ in Q:

Ist es günstiger über $w_{min}$ zu einem Knoten w zu kommen?
Falls ja setzte d(s,w)=d(s, $w_{min}$ )+y( $w_{min}$ ,w)

5. Wiederhole bei 3 solange Q noch Elemente hat

Algorithmus in Java

Map<Integer,Integer> dijkstra(Graph g, int s){
   Map<Integer,Integer> d = new HashMap<Integer, Integer>();
   PriorityQueue<Integer> queue = //Initialisiere Priority-Queue entsprechend
   for(Integer n: g){
      if(!n.equals(s)){
         d.put(n, Integer.MAX_VALUE);
         queue.add(n);
      }
   }
   d.put(s, 0);
   queue.add(s);

   while(!queue.isEmpty()){
      Integer u = queue.poll();
      for(Integer v: g.getChildren(u)){
         if(queue.contains(v)){
            if(d.get(u) + g.getWeight(u,v) < d.get(v){
               d.put(v, d.get(u) + g.getWeight(u,v));
            }
         }
      }
   }
   return d;
}

Algorithmus

algorithm Dijkstra (G,s)

Eingabe: Graph G mit Startknoten s

for each Knoten u

\in

V[G] -s do // Initialisierung

D[u] :=

\infty

od;

D[s]:= O; PriorityQueue Q := V;

while not isEmpty (Q) do

U := extractMinimal (Q);

for each v

\in

ZielknotenAusgehenderKanten (u)

\cap

Q do

if D[u] +

\gamma

((u,v)) < D[v] then // Entfernung über u nach v kleiner als aktuelle Entfernung D[v]

D[v] := D[u] +

\gamma

((u,v));

adjustiere Q an neuen Wert D[v]

fi

od

Initialisierung

$D[s]+\gamma (s,u)<D[u]?$

$0+10<\infty$

$\Rightarrow D[u]=10$

$D[s]+\gamma (s,x)<D[x]?$

$0+5<\infty$

$\Rightarrow D[x]=5$

$Q=\langle (s:0),(u:\infty ),(v:\infty ),(y:\infty )\rangle$

$D[x]+\gamma (x,u)<D[u]?$

$5+3<10$

$\Rightarrow D[u]=8$

$D[y]analog$

$Q=\langle (x:5),(u:10),(v:\infty ),(y:\infty )\rangle$

$Q=\langle (y:7),(u:8),(v:\infty )\rangle$

$Q=\langle (u:8),(v:13)\rangle$

$Q=\langle (v:9)\rangle$

Der Iterationsstart ist korrekt für die Tiefe 0. Wir nehmen an, dass der vorherige Iterationsschritt korrekt war ( Induktionsbeweis). Der Ein Iterationsschritt ist jeweils die günstigste Verbindung zu einem noch nicht bearbeiteten Knoten hinzunehmen. Da die bisher bearbeiteten Knoten den korrekten Distanzwert haben, ist der neue Distanzwert durch den „günstigsten“ aus dem bisher bearbeiteten Teilgraphen um genau eine Kante hinausgehenden Pfad bestimmt. Jeder Pfad zum Zielknoten dieses Pfades, der um mehr als eine Kante aus dem bearbeiteten Bereich hinausgeht, ist teurer als die gewählte, da Kosten mit zusätzlich hinzu genommenen Kanten nicht sinken können.

Analyse

Terminierungstheorem

Der Algorithmus von Dijkstra terminiert für eine endliche Eingabe nach endlicher Zeit.

Beweis

In jedem Schritt der while‐Schleife wird ein Element aus queue entfernt und die Schleife endet sobald queue leer ist. Jeder Knoten hat nur endliche viele Kinder, deswegen ist auch die Laufzeit der inneren for‐Schleife endlich.

Korrektheitstheorem

Sind alle Kantengewichte nicht‐negativ, so enthält d am Ende die Distanzwerte von s zu allen anderen Knoten.

Beweis

Beachte, dass sobald ein Knoten v aus queue entfernt wird, der Wert für v in d nicht mehr geändert wird.

Zeige nun, dass gilt: Wird v aus queue entfernt, so enthält d den Distanzwert von s nach v. Zeige dies durch Induktion nach i=„Anzahl bisher aus queue entfernter Knoten“:

i=0: Am Anfang hat queue nur für s einen endlichen Wert gespeichert, alle anderen Werte sind ∞. Der Knoten s wird auch stets zuerst entfernt und der Distanzwert ist 0. Dies ist auch korrekt, da s zu sich selbst Distanz 0 hat und alle anderen Knoten keine geringere Distanz von s aus haben können (da alle Kanten nicht‐negative Gewichte haben).
i → i+1: Sei v der (i+1)te Knoten, der aus queue entfernt wird.
- Da die bisher bearbeiteten Knoten den korrekten Distanzwert haben, ist der neue Distanzwert durch den „günstigsten“ aus dem bisher bearbeiteten Teilgraphen um genau eine Kante hinausgehenden Pfad bestimmt.
- Jeder Pfad zum Zielknoten dieses Pfades, der um mehr als eine Kante aus dem bearbeiteten Bereich hinausgeht, ist teurer als die gewählte, da Kosten mit zusätzlich hinzugenommenen Kanten nicht sinken können.

Laufzeittheorem

Sei G=(V,E,g) ein gerichteter Graph. Der Laufzeitaufwand von Dijkstras Algorithmus für einen beliebigen Knoten s in G ist O((|E| + |V|) log |V|).

Beweis

Beachte: Wird für die Priority‐Queue beispielsweise ein Heap verwendet, so hat die Operation poll() einen Aufwand von O(log k) (mit k=„Anzahl Elemente in Queue“). Sei |V|=n und |E|=m. Insgesamt: O(n log n) + O(n) + n* O(log n) + m *O(log n) = O((m + n) log n) Durch Benutzung sog. Fibonacci‐Heaps (anstatt normaler Heaps) kann die Laufzeit von O((m + n) log n) verbessert werden zu O(m + n log n)

Nachteile

Der kürzeste Weg wird immer gefunden, aber es werden viele unnötige und sinnlose Wege gegangen. Bei negativen Kanten resultieren auch falsche Ergebnisse.

Bellmann-Ford

Auf dieser Seite wird der Bellmann-Ford Algorithmus behandelt. Bei Dijkstra dürfen nur nichtnegative Gewichte benutzt werden. Doch gibt es auch eine Variante mit negativen Gewichten? Das würde nur bei gerichteten Graphen Sinn machen. Das Problem sind Zyklen mit negativem Gesamtgewicht. Ein Beispiel für Gewinn statt Kosten ist beispielsweise ein Verbindungsnetz mit Bonus Gewinnen für bestimmte Verbindungen um Auslastungen zu erhöhen. Dies ist bei Flügen mit Zwischenstopps der Fall, die oft billiger sind. Dieser Algorithmus löst ebenfalls das SSSP Problem.

Prinzip

Der Algorithmus erfolgt in mehreren Durchläufen. Es wird zunächst die bisher beste mögliche Verbindung bestimmtl, die die um eine Kante länger ist. Der i-te Durchlauf berechnet korrekt alle Pfade vom Startknoten der Länge i. Der längste Pfad ohne Zyklus hat eine Länge kleiner als |V|-1, somit hat man spätestens nach |V|-1 Durchläufen ein stabiles Ergebnis. Sollte das Ergebnis nach |V|-1 Durchläufen nicht stabil sein, so ist ein negativ bewerteter Zyklus enthalten. Hierbei wird das Prinzip der dynamischen Programmierung verwendet.

Algorithmus

algorithm BF(G, s)
   Eingabe: ein Graph G mit Startknoten s

   D[s] = 0
   D[t] = ∞ for all other t
   for i := 1 to |V|-1 do
      for each (u,v)∈ E do
         if D[u]+γ((u,v)) < D[v] then
            D[v] := D[u] + γ((u,v))
         fi
      od
   od

Beispiel

Bei der Initialisierung wird der Startknoten auf den Wert 0 gesetzt und alle weiteren Knoten erhalten den Wert ∞.

Beim ersten Schleifendurchlauf bekommt x den Wert 5 und u den Wert 10 zugewiesen.

Im zweiten Schleifendurchlauf werden alle weiteren Verbindungen aktualisiert, sowohl von u als auch von x. Dabei ändern sich die Werte von v, y und auch u. Die Änderung an u wird aber erst im nächsten Schritt an v propagiert.

Im dritten, i=3, Schleifendurchlauf verändern sich diesmal nur noch die Werte der Knoten v und y. Der neue Wert aus y berechnet sich durch den vorherigen Wert aus v=11 und der negativ gewichteten Kante -5. Hier wird also die negativ gewichtete Kante (v,y) zur Berechnung von D[y] genutzt.

Im vierten, i=4, Schleifendurchlauf wird nochmals die negativ gewichtete Kante (v,y) zur Berechnung von D[y] genutzt. Das Greedy-Verfahren, das jeden Knoten nur einmal besucht, hätte für y den in jedem Schritt lokal optimalen Pfas $<s,x,y>$ gewählt und nicht das beste Ergebnis geliefert.

Analyse

Terminierungstheorem

Der Algorithmus BF(G,s) terminiert für eine endliche Eingabe G in endlicher Zeit.

Beweis

Alle Schleifen sind endlich.

Korrektheitstheorem

Ist G ein Graph, der keinen Zyklus mit negativem Gewicht hat, so enthält D nach Aufruf BF(G,s) die Distanzwerte von s zu allen Knoten.

Beweis

Wir zeigen, dass die folgenden Aussagen Schleifeninvariante der for‐ Schleife (Schleifenvariable i) sind:

Ist D[v] < ∞, so ist D[v] der Wert eines Pfades von s nach v
Ist D[v] < ∞, so ist D[v] der kleinste Wert eines Pfades von s nach v mit maximal i Kanten
D[v] < ∞ gdw. es einen Pfad von s nach v mit gleich oder weniger als i Kanten gibt

Da G keine Zyklen mit negativem Gewicht hat, ist die Länge des längsten kürzesten Pfades maximal |Anzahl Knoten|‐1 (jeder Knoten wird auf diesem Pfad einmal besucht). Also gilt nach dem letzten Schleifendurchlauf nach 2 und 3. die Aussage des Theorems. Wir zeigen diese Aussagen durch Induktion nach i(=#Schleifendurchläufe).

Bei i=0 gilt vor dem ersten Schleifendurchlauf nur D[s]=0 < ∞. Daraus folgt direkt 1., 2., 3.
Bei i -> i+1 beweisen wir zunächst Aussage 3.
- War D[v] schon vorher endlich, so gilt die Aussage nach IV.
- Ist D[v] in diesem Schritt auf einen endlichen Wert gesetzt worden, so gab es ein u, so dass D[u] vorher schon endlich war und D[v]=D[u]+γ(u,v). Nach IV gibt es einen Pfad von s nach u der Länge i. Damit gibt es einen Pfad der Länge i+1 von s nach v.
- Umgekehrt wird bei Existenz eines Pfades der Länge i+1 dieser auch gefunden und D[v] auf einen endlichen Wert gesetzt.

Die Aussage 1 wird dadurch bewiesen, dass nach IV der Wert eines Pfades von s nach u D[u] ist. Wird D[v]=D[u]+γ(u,v) gesetzt so ist somit D[v] der Wert des Pfades von s nach v über u.
Die Aussage 2 wird dadurch bewiesen, dass nach IV der kleinste Wert eines Pfades von s nach v mit maximal i Kanten D[v] ist. Mache folgende Fallunterscheidung:
- 1.Fall: Es existiere ein Pfad P1 von s nach v mit i+1 Kanten, der minimalen Wert unter allen Pfaden von s nach v mit gleich oder weniger als i+1 Kanten hat. Betrachte den vorletzten Knoten u auf diesem Pfad und den Teilpfad P2 von P1 von s nach u. Dieser Teilpfad hat minimalen Wert unter allen Pfaden der maximalen Länge i von s nach u (ansonsten wäre P1 kein Pfad mit minimalem Wert). Nach IV ist D[u] genau dieser Wert und D[u]+γ(u,v) der Wert von P1, der dann im i+1ten Durchgang aktualisiert wird.
- 2.Fall: Es existiere kein Pfad von s nach v mit i+1 Kanten, der minimalen Wert unter allen Pfaden von s nach v mit gleich oder weniger als i+1 Kanten hat.
  - 1. Unterfall: Es existiert kein Pfad von s nach v mit maximal i+1 Kanten. Dann bleibt nach 3. D[v]=∞.
  - 2. Unterfall: Es existiert ein Pfad von s nach v mit k<i+1 Kanten, der minimalen Wert unter allen Pfaden von s nach v mit gleich oder weniger als i+1 Kanten hat. Dann ist nach IV D[v] genau dieser Wert und wird im i+1ten Durchgang auch nicht aktualisiert.

Graph mit negativ gewichtetem Zyklus

Betrachten wir die Situation nach |V|-1 Iterationen. Eine Kante könnte noch verbessert werden genau dann wenn der Graph einen Zyklus negativer Länge enthält. Der Zyklus s,x,u,v,y,s hat die Kosten 5+3+1-5-7=-3. Jeder Durchlauf durch den Zyklus erzeugt also einen Gewinn. Es gibt hier keinen günstigen Pfad endlicher Länge!

Laufzeittheorem

Sei G=(V,E,g) ein gerichteter Graph. Der Laufzeitaufwand vom Algorithmus von Bellmann‐Ford für einen beliebigen Knoten s in G ist O(|V||E|).

Beweis

Einfache Schleifenanalyse.

Floyd-Warshall

Auf dieser Seite wird der Floyd-Warshall Algorithmus behandelt. Der Dijkstras Algorithmus und Bellman-Ford berechnen zu einem gegebenen Startknoten die kürzesten Wege zu allen anderen Knoten (Single Source Shortest Paths – SSSP. Aber wie kann man die kürzesten Wege zwischen zwei Knoten v und w berechnen? Man könnte die bereits kennengelernten Algorithmen für jeden einzelnen Startknoten neu aufrufen, doch das geht auch geschickter. Hier kommt der Floyd-Warshall Algorithmus ins Spiel, welcher das All Pairs Shortest Path Problem löst. Zwar nicht unbedingt effizienter, aber eleganter. Dies geschieht nach dem Prinzip der dynamischen Programmierung.

Problemdefinition

Gegeben ist ein Graph G=(V,E). Wir möchten für jedes Paar $(v,w)\in V\times V$ den Wert D(v,w) eines kürzesten Pfades finden. Wir nehmen an, dass es keine negativen Kreise gibt.

D	s	u	v	x	y
s	0	8	9	5	4
u	3	0	1	-2	-4
v	2	10	0	7	-5
x	6	3	4	0	-1
y	7	15	6	12	0

Idee

Die Grundidee des Floyd-Warshall Algorithmus ist, dass wenn ein kürzester Weg $\{(v,a_{1}),...,(a_{n},k),(k,a_{n+1}),...,(a_{m},w)\}$ von v nach w über k geht, dann gilt:

$\{(v,a_{1}),...,(a_{n},k)\}$ ist ein kürzester Weg von v nach k
$\{(k,a_{n+1}),...,(a_{m},w)\}$ ist ein kürzester Weg von k nach w

Im obigen Beispiel gilt folgendes:

$s\to y:\{(s,x),(x,u),(u,v),(v,y)\}$
$s\to u:\{(s,x),(x,u)\}$
$u\to y:\{(u,v),(v,y)\}$

Die Umkehrung gilt jedoch nicht. Ist $\{(v,a_{1}),...,(a_{n},k)\}$ ein kürzester Weg von v nach k und ist $\{(k,a_{n+1}),...,(a_{m},w)\}$ ein kürzester Weg von k nach w dann gilt nicht notwendigerweise, dass $\{(v,a_{1}),...,(a_{n},k),(k,a_{n+1}),...,(a_{m},w)\}$ ein kürzester Weg von v nach w ist!

Im obigen Beispiel bedeutet dies:

$x\to y:\{(x,y)\}$
$y\to v:\{(y,v)\}$
$x\to v:\{(x,y),(y,v)\}$ ist nicht der kürzeste Weg!

Jedoch gilt, wenn bekannt ist, dass ein kürzester Weg zwischen v und w nur Knoten aus $V'\subseteq V$ enthält, so gilt entweder der kürzeste Weg zwischen v und w benutzt nur Knoten aus $V'\backslash \{k\}$ oder der kürzeste Weg zwischen v und w ist Konkatenation aus dem kürzesten Weg zwischen v und k und dem kürzesten Weg zwischen k und w und beide Wege enthalten nur Knoten aus $V'\backslash \{k\}$ .

$D^{V'}[i,j]=fac(x):=\left\{{\begin{array}{ll}\gamma (i,j)&falls~k=0\\min\{D^{V'\backslash \{k\}}[i,j],D^{V'\backslash \{k\}}[i,k]+D^{V'\backslash \{k\}}[k,j]\}&falls~k\geq 1\end{array}}\right.$

Algorithmus

algorithm FW(G)
   Eingabe: ein Graph G

   for each v,v‘∈V
      D[v,v‘] = γ((v,v‘)) (or ∞)
   for each k ∈ V do
      for each i ∈ V do
         for each j ∈ V do
            if D[i,k]+D[k,j] < D[i,j] then
               D[i,j] := D[i,k]+D[k,j]
            fi
         od
      od
   od

Beispiel

Initialisiere D mit den Kantengewichten. Nicht vorhandene Kanten haben das Gewicht $\infty$ . Die Kantengewichte zum Knoten selber sind 0. Im folgenden betrachten wir nur Schleifendurchgänge mit $k\neq i,k\neq j,i\neq j$

D	s	u	v	x	y
s	0	10	$\infty$	5	$\infty$
u	$\infty$	0	1	-2	$\infty$
v	$\infty$	$\infty$	0	$\infty$	-5
x	$\infty$	3	$\infty$	0	2
y	7	$\infty$	6	$\infty$	0

D	s	u	v	x	y
s	0	10	$\infty$	5	$\infty$
u	$\infty$	0	1	-2	$\infty$
v	$\infty$	$\infty$	0	$\infty$	-5
x	$\infty$	3	$\infty$	0	2
y	7	17	6	$\infty$	0

D	s	u	v	x	y
s	0	10	$\infty$	5	$\infty$
u	$\infty$	0	1	-2	$\infty$
v	$\infty$	$\infty$	0	$\infty$	-5
x	$\infty$	3	$\infty$	0	2
y	7	17	6	12	0

Führt man den Algorithmus weiter durch, kommt man zu folgendem Endergebnis:

D	s	u	v	x	y
s	0	8	9	5	4
u	3	0	1	-2	-4
v	2	10	0	7	-5
x	6	3	4	0	-1
y	7	15	6	12	0

Analyse

Terminierungstheorem

Der Algorithmus FW(G) terminiert für eine endliche Eingabe G in endlicher Zeit.

Beweis

Alle Schleifen sind endlich.

Korrektheitstheorem

Ist G ein Graph, der keinen Zyklus mit negativem Gewicht hat, so enthält D nach Aufruf FW(G) die Distanzwerte von allen Knoten zu allen anderen Knoten.

Beweis

Betrachte dazu folgende Schleifeninvariante, die äußerste for-Schleife mit der Laufvariablen k): Nach der k-ten Schleifeniteration gilt, dass D[v,w], für alle v,w, der Wert eines kürzesten Pfades ist, der nur Knoten 1,...,k benutzt. Wenn der Algorithmus endet, gilt damit die Aussage des Theorems. Dies zeigen wir durch Induktion.

k=0 (bei der Initialisierung): Nach der Initialisierung gilt D[v,w]= ∞ gdw. es keine Kante von v nach w gibt. Das bedeutet, dass jeder Pfad zwischen v und w mindestens einen anderen Knoten enthalten haben muss. Ist D[v,w] endlich, so ist dies genau der Wert der Kante. Dann gibt es also einen Pfad, der keine weiteren Knoten beinhaltet.
k -> k+1: Nach der Induktionsannahme ist D[v,w] der Wert eines kürzestens Pfades, der nur Knoten aus 1,...,k enthält. Im k+1-Schleifendurchgang wird überprüft, ob es einen kürzeren Weg über k+1 gibt und ggfs. aktualisiert. Es wird also genau folgende Gleichung ausgenutzt:

$D^{V'}[i,j]=\left\{{\begin{array}{ll}\gamma (i,j)&{\text{falls}}\ V'=\emptyset \\min\{D^{V'\backslash \{k\}}[i,j],D^{V'\backslash \{k\}}[i,k]+D^{V'\backslash \{k\}}[k,j]\}&{\text{für}}\ k\in V'\end{array}}\right.$

Anschließend ist also D[v,w] der Wert eines kürzestens Pfades, der nur Knoten 1,...,k+1 benutzt.

Ein anderer Ansatz ist dies per Induktion nach der kürzesten Länge eines kürzesten Weges für jedes Knotenpaar (v,w) zu zeigen. Anmerkung: zwischen v und w können mehrere Wege mit minimalem Gewicht existieren, diese können auch unterschiedliche Länge haben. Angenommen zwischen v und w existiert ein kürzester Weg der Länge 1, dann ist der Wert dieses Weges gleich dem Wert der Kante (die existieren muss. Dieser wird in der Initialisierungsphase gesetzt und später nicht mehr geändert. Angenommen zwischen v und w gibt es einen kürzesten Pfad (=minimales Gewicht) der Länge l≥ 2 , dann gibt es einen Knoten k auf diesem Pfad, so dass zum einen der Teilpfad von v nach k ein kürzester Weg von v nach k ist und zum anderen, dass der Teilpfad von k nach w ein kürzester Weg von k nach w ist. Somit haben beide Pfade haben Länge < l, d.h. die Werte D[v,k] und D[k,w] müssen schon korrekt berechnet sein (die Induktionsvoraussetzung greift). Da alle potentiellen “Mi5elknoten” überprüft werden, wird ein geeignetes k gefunden und der Wert D[v,w] aktualisiert.

Laufzeittheorem

Sei G=(V,E,g) ein gerichteter Graph. Der Laufzeitaufwand vom Algorithmus von Floyd‐Warshall auf G ist $O(\mid V\mid ^{3}$ ).

Beweis

Einfache Schleifenanalyse.

Flussproblem

Auf dieser Seite wird das Flussproblem behandelt. Die Bestimmung des maximalen Flusses muss in vielen logischen Aufgaben angewandt werden. Beispielsweise bei Verteilungsnetzen mit Kapazitäten wie Wasserrohren, Förderbändern oder Paketvermittlungen mit Rechnernetzen. Die Quellen liefert beliebig viele Objekte pro Zeiteinheit und die Senke verbraucht diese. Jede Verbindung hat eine maximale Kapazität c und einen aktuellen Fluss f. Wie hoch ist nun die Übertragungskapazität?

Definition Fluss

Ein Fluss f von $q\in V$ nach $z\in V$ ist eine Funktion $f_{q,z}:E\to \mathbb {R}$ . Für diese Funktion $f_{q,z}$ gelten folgende zwei Bedingungen:

Die Kapazitäten werden eingehalten: $\forall e\in E:f_{q,z}(e)\leq c(e)$
Was in einen Knoten hereinfließt, muss wieder herausfließen, mit Ausnahme von q und z: $\forall v\in V\backslash \{q,z\}:\sum _{u\in P(v)}f((u,v))=\sum _{w\in S(v)}f((v,w))$ , wobei $P(v)=\{u|(u,v)\in E\}$ der Vorgänger von v ist und $S(v)=\{w|(v,w)\in E\}$ der Nachfolger von v ist.

Einschränkungen der Kapazität der Kanten werden eingehalten, auch bei negativem Fluss:

 $|f_{q,z}(u,v)|\leq c((u,v))$

Außerdem ist der Fluss konsistent. Bei in beiden Richtungen nutzbaren Verbindungen wird als Nettoeffekt nur in eine Richtung gesendet und der entstehende negative Fluss nimmt den korrekten Wert an:

 $f_{q,z}(u,v)=-f_{q,z}(v,u)$

Der Fluss wird für jeden Knoten $v\in V\backslash \{q,z\}$ mit Ausnahme der Quelle q und des Ziels z bewahrt:

 $\sum _{u\in V}f_{q,z}(v,u)=0$

Der Wert eines Flusses beträgt:

 $val(G,f_{q,z})=\sum _{u\in S(q)}f_{q,z}(q,u)$

Gesucht wird der maximale Fluss:

 $max\{val(G,f)|$  f ist korrekter Fluss von q nach z}

Beispiel

Definiere $f_{1}$ durch

$f_{1}((1,2))=2,\ f_{1}((1,3))=4,\ f_{1}((2,4))=1,\ f_{1}((2,5))=1,\ f_{1}((3,2))=0,\ f_{1}((3,5))=4,\ f_{1}((4,5))=0,\ f_{1}((4,6))=1,\ f_{1}((5,6))=5$ .

Daraus folgt, dass der Wert des Flusses 6 ist: $val(G,f_{1})=6$ .

Definiere $f_{2}$ durch

$f_{2}((1,2))=5,\ f_{2}((1,3))=3,\ f_{2}((2,4))=4,\ f_{2}((2,5))=1,\ f_{2}((3,2))=2,\ f_{2}((3,5))=1,\ f_{2}((4,5))=1,\ f_{2}((4,6))=3,\ f_{2}((5,6))=3$ .

Daraus folgt, dass $f_{2}$ kein Fluss ist.

Definiere $f_{3}$ durch

$f_{3}((1,2))=5,\ f_{3}((1,3))=9,\ f_{3}((2,4))=4,\ f_{3}((2,5))=5,\ f_{3}((3,2))=4,\ f_{3}((3,5))=5,\ f_{3}((4,5))=0,\ f_{3}((4,6))=4,\ f_{3}((5,6))=10$ .

Daraus folgt, dass der Wert des Flusses 14 ist: $val(G,f_{3})=14$ . Damit ist der Fluss $f_{3}$ maximal.

Ford-Fulkerson

Auf dieser Seite wird der Ford Fulkerson Algorithmus zur Berechnung des maximalen Flusses behandelt.

Berechnung des maximalen Flusses

Der Ford-Fulkerson Algorithmus ist ein effizienter Algorithmus zur Bestimmung eines maximalen Flusses von q nach z. Dabei wird der Greedy Algorithmus mit Zufallsauswahlen gemischt. Hier wird das Prinzip "Füge so lange verfügbare Pfade zum Gesamtfluss hinzu wie möglich" verfolgt. Zuerst soll ein nutzbarere Pfad durch Tiefensuche gefunden werden. Für die Kanten werden dann drei Werte notiert. Zum einen der aktuellen Fluss entlang der Kante. Im initialisierten Graphen ist dieser Wert überall 0. Zudem wird die vorgegebene Kapazität c notiert und die abgeleitete noch verfügbare Restkapazität von c-f.

Algorithmus

initialisiere Graph mit leerem Fluss;
do
   wähle nutzbaren Pfad aus;
   füge Fluss des Pfades zum Gesamtfluss hinzu;
while noch nutzbarer Pfad verfügbar

Ein nutzbarere Pfad ist ein zyklenfreier Pfad von der Quelle q zum Ziel z, der an allen Kanten eine verfügbare Kapazität hat. Ein nutzbarer Fluss ist das Minimum der verfügbaren Kapazitäten der einzelnen Kanten.

Der nachfolgende Pseudocode realisiert das Problem mit zusätzlichen Rückkanten.

für jede Kante(u,v) füge Kante (v,u) mit Kapazität 0 ein;
initialisiere Graph mit leerem Fluss;
do
   wähle nutzbaren Pfad aus;
   füge Fluss des Pfades zum Gesamtfluss hinzu;
while noch nutzbarer Pfad verfügbar

Beispiele

Wir haben einen Graph mit Kapazitäten gegeben

Es wird mit dem Fluss 0 initialisiert. Notation: <aktueller Fluss f> / <Kapazität c> / <verfügbare Kapazität c-f>

Die Auswahl der nutzbaren Pfade geschieht zufällig oder durch geeignete Heuristik. Es gibt auch kürzere Pfade mit höheren Kapazitäten. Die Rückkanten werden mit der Kapazität 0 eingefügt. Die Auswahl eines Pfades geschieht durch $1\to 2\to 4\to 5\to 6$ Der nutzbare Fluss beträgt 4.

Der Fluss wird aktualisiert. Die Auswahl des Pfades ist nun : $1\to 3\to 5\to 6$ . Der nutzbare Fluss beträgt 5.

Der Fluss wird aktualisiert. Die Auswahl des Pfades ist nun : $1\to 3\to 2\to 5\to 6$ . Der nutzbare Fluss beträgt 3.

Der Fluss wird aktualisiert. Die Auswahl des Pfades ist nun : $1\to 3\to 2\to 5\to 4\to 6$ . Der nutzbare Fluss beträgt 2.

An dieser Stelle sind keine Kapazitäten mehr über und die Berechnung wir beendet. Der maximale Fluss beträgt 14.

Der Algorithmus kann dabei auf verschiedene Ergebnisse kommen, jedoch ist der maximale Fluss immer gleich. Eine weitere Lösung ist folgende:

Zunächst wird der Pfad $1\rightarrow 2\rightarrow 5\rightarrow 6$ mit dem nutzbaren Fluss 5 ausgewählt.

Anschließend wird der Fluss aktualisiert. Im nächsten Schritt wird dann der Pfad $1\rightarrow 3\rightarrow 5\rightarrow 6$ gewählt. Ebenfalls ist hier wieder ein nutzbarer Fluss von 5.

Nach der zweiten Aktualisierung ist nur noch ein Pfad vom Start zum Ziel möglich. Also wird der Pfad $1\rightarrow 3\rightarrow 2\rightarrow 4\rightarrow 6$ ausgewählt. Dieser Fluss enthält allerdings nur noch einen nutzbaren Fluss von 4.

Nach dem Aktualisieren des Flusses ist es nicht mehr möglich einen Pfad vom Start zum Ziel zu finden. Damit ist die Berechnung beendet. Wie zuvor berechnet ist der maximale Fluss 14.

Problem: Ungünstige Pfadwahl

Die bisher betrachtete Version des Algorithmus ist nicht immer optimal.

Wählen der Pfad $1\rightarrow 3\rightarrow 2\rightarrow 4$ ausgewählt, besitzt dieser Pfad einen nutzbaren Fluss von 5.

Nun wird der Fluss aktualisiert. Daraus folgt, dass keine weitere Pfadwahl mehr möglich ist. Dabei wäre die optimale Lösung über die Pfade $1\rightarrow 2\rightarrow 4$ und $1\rightarrow 3\rightarrow 4$ .

Das Problem ist, dass der Fluss nicht zurückgenommen werden kann. Die Lösung dazu ist, dass man entgegengesetzte Flussrichtung durch Rückkanten erlaubt. Auch hier wird wieder der ungünstige Pfad $1\rightarrow 3\rightarrow 2\rightarrow 4$ mit einem nutzbaren Fluss von 5 im ersten Schritt ausgewählt.

Anschließend wird der Fluss aktualisiert. Dabei wird der Pfad $1\rightarrow 2\rightarrow 3\rightarrow 4$ mit dem nutzbaren Fluss von 5 ausgewählt.

Beim erneuten aktualisieren des Flusses, stellt sich heraus, dass keine weiteren Pfade möglich sind. Damit ist die Berechnung, bei einem maximalen Fluss von 10, beendet.

Analyse

Terminierungstheorem

Sind alle Kapazitäten in G nicht-negativ und rational, dann terminiert der Algorithmus von Ford‐Fulkerson nach endlicher Zeit.

Laufzeittheorem

Ist X der Wert eines maximales Flusses in G=(V,E) und sind alle Kapazitäten in G nicht-negativ und ganzzahlig, so hat der Algorithmus von Ford‐Fulkerson eine Laufzeit von O(|E|X).

Korrektheitstheorem

Sind alle Kapazitäten in G nicht‐negativ und rational, dann berechnet der Algorithmus von Ford‐Fulkerson den Wert eines maximalen Flusses.

Anmerkung

Die Wahl des Pfades beeinflusst die Anzahl benötigter Iteratoren. Bei dem Verfahren von Edmons und Karp muss die Anzahl der Pfade die in einem Graphen G = (V,E) bis zum Finden des maximalen Flusses verfolgt werden, kleiner sein als |V||E|, wenn jeweils der kürzeste Pfad von Quelle q zu Ziel z gewählt wird. Daher kann die Auswahl des nächsten kürzesten Pfades basierend auf einer Variante der Breitensuche erfolgen. Dadurch wird die Laufzeit auf $O(\mid V\mid \mid E\mid ^{2})$ verbessert.

Spannbäume

Auf dieser Seite werden Spannbäume und in diesem Zusammenhang der Algorithmus von Prim behandelt.

Beispiel Kommunikationsnetz

Zwischen n Knotenpunkten $v_{1}...v_{n}$ soll ein möglichst billiges Kommunikationsnetz geschaltet werden, so dass jeder Knotenpunkt mit jedem anderen verbunden ist, ggf. auf einem Umweg über andere Knotenpunkte. Bekannt sind die Kosten $c_{ij}$ für die direkte Verbindung zwischen $v_{i}$ und $v_{j}1\leq i,j\leq n$ . Alle Kosten $c_{ij}$ seien verschieden und größer Null. Die Modellierung geschieht somit als gewichteter, ungerichteter und vollständiger Graph mit einer Gewichtungsfunktion c.

$G=(V,E)$

$V=\{v_{1},...,v_{5}\}$

$E=\{(v_{1},v_{2}),(v_{1},v_{3}),(v_{1},v_{4}),(v_{1},v_{5}),(v_{2},v_{3}),(v_{2},v_{4}),(v_{2},v_{5}),(v_{3},v_{4}),(v_{3},v_{5}),(v_{4},v_{5})\}$

$c((v_{1},v_{2}))=6,c((v_{1},v_{3}))=7$ etc; abgekürzt $c_{1,2}=6,c_{1,3}=7$ etc

Problemstellung: Finde minimal aufspannenden Baum

Einige Definitionen für ungerichtete Graphen:

Ein Graph G=(V,E) heißt zusammenhängend, wenn für alle v,w∈V ein Pfad von v nach w in G existiert.

Ein Graph G=(V,E) enthält einen Zyklus, wenn es unterschiedliche Knoten $v_{1},...,v_{n}\in V$ gibt, so dass $\{v_{1},v_{2}\},...,\{v_{n-1},v_{n}\},\{v_{n},v_{1}\}\in E$ . Ein Graph G=(V,E) heißt Baum, wenn er zusammenhängend ist und keinen Zyklus enthält.

Ein Graph G’=(V’,E’) heißt Teilgraph von G=(V,E), wenn $V'\subseteq V$ und $E'\subseteq E\cap (V'xV')$ .

Ein Graph G’=(V’,E’) heißt induzierter Teilgraph von G=(V,E) bzgl. $V'\subseteq V$ , wenn $E'=E\cap (V'xV')$

Ein Graph G‘=(V‘,E‘) heißt Spannbaum von G=(V,E), wenn V'=V und G' ein Teilgraph von G und ein Baum ist.

Das Gewicht einen Graphen G=(V,E) ist $C(G)=\sum _{(i,j)\in E}c_{i,j}$ .

Ein Graph G'=(V',E') ist ein minimaler Spannbaum von G=(V,E), wenn G' ein Spannbaum von G ist und G' unter allen Spannbäumen von G das minimalste Gewicht hat.

Algorithmus von Prim

Der Algorithmus wird schrittweise verfeinert und der Aufbau eines aufgespannten Baumes erfolgt durch das Hinzufügen von Kanten. Das Greedy Muster, also jeweils die Wahl der kostengünstigsten Kante als Erweiterung, wird hier benutzt.

Aufspannender minimaler Baum

//Teilbaum B besteht anfangs aus einem beliebigen Knoten
while [ B noch nicht GV aufspannt ]
do [ suche kostengünstige von B ausgehende Kante ];
     [ füge diese Kante zu B hinzu ];
od

Eine Verfeinerung der Suche nach der kostengünstigsten Kante ist notwendig!

Suche nach kostengünstigster Kante

Die intuitive Vorgehensweise erfordert jeweils |W|(|V|-|W|) Vergleiche für ein gegebenes W. Das ganze |V| mal, also eine Gesamtlaufzeit von $O(n^{3})$ . Man kann die Suche auf die Teilmengen $F\subseteq E$ beschränken, so dass F immer die günstigste aus b ausgehende Kante enthält, wesentlich weniger Kanten hat als |W|(|V|-|W|) und im Verlauf des Algorithmus einfach anpassbar ist.

Wahl von F

Alternativen:

a) F enthält für jeden Knoten v in B die günstigste von v aus B herausführende Kante

b) F enthält für jeden Knoten v außerhalb B die günstigste von v in B hineinführende Kante

Bewertung:

a) Mehrere Kanten können zum gleichen Knoten herausführen – redundant und änderungsaufwändig (bei Wahl dieses Knotens darf er nicht mehr verwendet werden und alle Verbindungen zu diesem Knoten müssen gelöscht werden)

b) Daher: Wahl von b)

Erste Verfeinerung

// Teilbaum B 
		[ B:= ({ beliebiger Knoten v }, {}) ]

		// Menge der Kandidatenkanten F
		[ F:= alle nach v führenden Kanten ]

		// alle Knoten betrachten
		for i := 1 to |V|-1
		do 	[ suche günstigste Kante f=(u,w) in F ];
			[ Füge f zu B hinzu (natürlich auch w) ];
		     	[ Aktualisiere F ];
		od

F muss nach jedem Durchlauf angepasst werden. Wenn f aus F entfernt wird erkennt man, dass der Teilgraph B tatsächlich ein Baum ist. Nun haben wir den neu verbundenen Knoten w. Jeder noch nicht verbundene Knoten x hat nun eine günstigste Verbindung entweder wie zuvor, oder aber mit dem neu hinzugefügten Knoten w!

Zweite Verfeinerung

// Teilbaum B 
		[ B:= ({ beliebiger Knoten v },{}) ]
		// Menge der Kandidatenkanten F
		[ F:= alle nach v führenden Kanten ]
		
		for i := 1 to |V|-1
		do 	
			// Sei v∈B, w∈B
			[ suche günstigste Kante f=(v,w) in F ];
			[ Füge f zu B hinzu ];
			// Aktualisiere F	
		     	[ Entferne f aus F ];
			// x in B, w neuerdings in B, y noch nicht in B
			for [ alle Kanten e=(x,y)∈F]
			do 
				if [ c((w,y))<c(e)] then [ Ersetze e durch (w,y) ] fi
			od	
		od

Kommunikationsnetz

i:

$B_{0}=(\{A\},\{\})$

$F_{0}=\{(A,E),(A,D),(A,C),(A,B)\}$

$f_{1}=(A,E)$ ist am günstigsten

$B_{1}=(\{A,E\},\{(A,E)\})$

$F_{1}=\{(A,D),(A,C),(A,B)\}$

$(A,D):F_{1}^{1}=\{(D,E),(A,C),(A,B)\}$

$(A,C):F_{1}^{2}=\{(D,E),(C,E),(A,B)\}$

$(A,B):F_{1}^{3}=\{(D,E),(C,E),(B,E)\}$

$f_{2}=(E,B)$

….

Analyse

Terminierungstheorem

Der Algorithmus von Prim terminiert nach endlicher Zeit.

Beweis

Einfache Schleifenanalyse

Laufzeittheorem

Wird für die Implementierung von F ein Fibonacci‐Heap benutzt, so hat der Algorithmus von Prim eine Laufzeit von O(|E| + |V| log |V|).

Korrektheitstheorem

Ist G ein verbundener ungerichteter gewichteter Graph, so berechnet der Algorithmus von Prim einen minimalen Spannbaum von G.

Beweis

Wir betrachten eine einfache Version des Algorithmus.

while [ B noch nicht GV aufspannt ]
do [ suche kostengünstige von B ausgehende Kante ]; 
     [ füge diese Kante zu B hinzu ];
od

Wir beobachten, dass B am Ende ein Spannbaum ist. Jetzt ist noch zu zeigen, dass B am Ende ein minimaler Spannbaum ist.

Sei B‘ ein minimaler Spannbaum von G und B≠B‘. Betrachte den Zeitpunkt in der Hauptschleife, an dem sich die Konstruktion von B von B‘ unterscheidet. Sei e die Kante, die dann zu B hinzugefügt wird. Sei $V_{1}$ die Menge der Knoten, die schon in B sind und $V_{2}=V$ \ $V_{1}$ Da B‘ ein minimaler Spannbaum ist, gibt es eine Kante e', die $V_{1}$ mit $V_{2}$ verbindet. Da im Algorithmus stets eine günstigste Kante gewählt wird, muss gelten g(e)≤g(e‘). Tauschen wir in B‘ die Kante e‘ durch e erhalten wir also einen minimalen Spannbaum, der nicht mehr kostet als B‘, es folgt g(e)=g(e‘). Induktiv folgt damit die Korrektheit.