Inhaltsverzeichnis
Graphalgorithmen ( elementare A. )
Eingangsgrad: indeg(v) = |{v' | (v', v) Î E}|
Speicherung von Graphen
Welche Repräsenation geeigneter ist, hängt von dem Problem ab:
Abstände werden in array d gespeichert
Tiefensuche:
Topologisches Sortieren:
Aus dem Beweis ist rekursiver Algorithmus abzuleiten.
Transitive Hülle: Warshall-Algorithmus
Sei A[i,j] Adjazenzmatrix. Algorithmus berechnet Adjazenzmatrix von G*.
Läßt sich einfach modifizieren, um kürzeste Wege zwischen allen Knotenpaaren zu berechnen.
Beispiel: Kürzeste Wege von einem Knoten (Dijkstra-Algorithmus)
for (v in V )
Beispiel: Kürzeste Wege von einem Knoten
Korrektheitsbeweis:
Flüsse in Netzen: Ford-Fulkerson
Gesucht: Fluß mit maximalem Wert
Jeder gerichtete Pfad von q nach s im Restgraphen heißt zunehmender Weg.
f kann so abgeändert werden:
Daraus ergibt sich folgender Algorithmus:
Beispiel:
Maximales Matching
Maximales Matching kann auf maximalen Fluß zurückgeführt werden:
Aufspannende Bäume: Kruskal-Algorithmus
Sowohl A als auch B zerlegen die zugrundeliegende
Nächste Annahme, es sei eine Gewichtsfunktion w : E ? ?
Beispiel: Gegeben sei folgender kanten-bewerteter Graph:
Der Kruskal-Algorithmus wählt nun
Sofern man nach absteigendem Kantengewicht die Kanten
Kürzeste Wege: Dijkstra-Algorithmus
Dijkstra-Algorithmus
Beispielgraph (wie oben)
Vom Startknoten u aus entwickelt der Dijkstra-Algorithmus
Diese Pfade bilden wieder einen aufspannenden Baum,
Die Korrektheit des Dijkstra-Algorithmus‘ kann man sich
Notwendig ist noch eine geeignete Gewichtsfunktion w‘
Im Beispiel oben wählt der kanonische Greedy-Algorithmus
Nachbemerkung:
|