1

Kapitel 8:  Graphalgorithmen 8.1   Grundlagen 8.2   Tiefen- und Breitensuche 8.3   Prim- und Kruskal-Algorithmus 8.4   Kürzeste Wege in Graphen 8.5   Eulersche und Hamiltonsche Graphen

2

8.3.2 Greedy-Verfahren

Greedy-Verfahren: zum Finden der Lösung eines Problems beginnen mit der leeren Lösung und bauen diese in jedem Schritt mit der derzeit optimal erscheinenden Möglichkeit aus.

Der Algorithmus von Prim ist ein Greedy-Verfahren: Er

beginnt mit einer Ecke und fügt zum schon konstruierten Baum immer eine Kante mit dem kleinsten Gewicht hinzu (die genau ein Ende im schon konstruierten Baum hat).

3

Huffmancode

Gegeben: eine Quelle/ein Alphabet A.

Präfixcode: Abbildung von A auf die Menge aller Binärwörter mit:

kein Codewort (=Element der Bildmenge) ist Präfix eines anderen Codewortes.

Ein Präfixcode kann durch einen Binärbaum dargestellt werden: die Codewörter entsprechen den Blättern und sind durch den Weg von der Wurzel zum jeweiligen Blatt gegeben:

nach links = 0, nach rechts = 1.

Ein Präfixcode ermöglicht eine eindeutige Decodierung.

4

Jetzt:

Quelle/Alphabet A mit Häufigkeitsverteilung, d.h. mit Funktion f:A [0,1] mit

{a in A} f(a) = 1.

Optimaler Präfixcode zu (A,f): Präfixcode zu A mit minimaler Durchschnittslänge der Codewörter:

{a in A} f(a) l(a) = min!

( l(a):= die Länge des Codewortes für a).

Idee: oft vorkommende Zeichen: kurze Codewörter,

selten vorkommende Zeichen: längere Codewörter.

5

Buchstabenhäufigkeit 

a) alphabetisch sortiert ohne Leerzeichen  b) nach Häufigkeit sortiert 

6

Buchstabenhäufigkeit 2

7

Greedy-Algorithmus zur Erstellung eines optimalen Präfixcodes: Huffmancode

Erzeuge für jedes Zeichen aus dem Alphabet (für jede Häufigkeit) einen Knoten.

Starte mit den beiden Zeichen x und y mit den kleinsten Häufigkeiten f(x) und f(y), ersetze x und y durch ein neues Zeichen z mit der Häufigkeit f(z)=f(x)+f(y), erzeuge einen neuen Knoten für z und füge an diesen die beiden Knoten für x und y an. Wiederhole dies mit dem Alphabet A´ := A \ {x,y} U {z}.

Iteriere dies, bis nur noch ein Zeichen (automatisch mit Häufigkeit =1) übrig ist.

Der Binärbaum kann nun so angeordnet werden, dass die Häufigkeiten auf jeder Ebene von links nach rechts fallen oder gleich bleiben.

8

Konstruktion eines optimalen Präfixcodes zu:

Alphabet Häufigkeit

a1 0.5

a2 0.2

a3 0.1

a4 0.1

a5 0.06

a6 0.04

9

Korrektheit des Verfahrens

Erste Hilfsaussage:

In jedem optimalen Präfixcodebaum mit mind. zwei Codewörtern gibt es zwei tiefste Blätter (= längste Codewörter), die Brüder sind.

10

Korrektheit des Verfahrens (2)

Dann zeigt man:

Seien x und y zwei Zeichen in A geringster Häufigkeit f(x) und f(y).

Dann gibt es zu A einen optimalen Präfixcode, in dem x und y durch zwei gleich lange, längste Codewörter (=zwei tiefste Bruderblätter) codiert werden.

Denn wenn x und y nicht in zwei solchen Blättern stehen, kann man sie mit den Zeichen dort vertauschen.

11

Korrektheit des Verfahrens (3)

Dann zeigt man: Sei A´ := A \ {x,y} U {z} mit einem neuen Zeichen z mit Häufigkeit f(z) = f(x)+f(y). Man erhält durch Weglassen der Blätter x und y einen optimalen Präfix-Code zu A´.

Insbesondere ist

MCL(A) – MCL(A´) = f(x) + f(y).

Dabei sei MCL(A) := mittlere Codewortlänge eines optimalen Präfixcodes zu A.

12

Optimalitätsbeweis

Nun Beweis dafür, dass das Verfahren wirklich einen optimalen Präfixcode liefert: durch Induktion über die Zahl der Zeichen im Alphabet.

Induktionsanfang: klar für Alphabet mit einem Zeichen.Induktionsschluss: Sei A ein Alphabet mit mindestens zwei

Zeichen und A´ := A \ {x,y} U {z} wie oben. Nach Induktionsannahme liefert das Verfahren einen

optimalen Präfixcode für A´. Anhängen zweier Blätter für x und y an z liefert einen Präfixcode für A, dessen mittlere Codewortlänge nur um f(x) + f(y) größer ist. Also ist es ein optimaler Präfixcode für A.

13

AnwendungenAnwendungsbereiche der

Huffmankodierung: z.B.• Textkompression,• Bildkompression, z.B. in JPEG.• Faxkodierung, CCITT Standard

Jede Linie des Bildes wird als eine Folge von Codeworten mit variabler Länge kodiert. Dabei geht es um die Länge der wechselnden Weiß-, Schwarzfolgen. Ist die Länge kleiner als 64, so wird ein modifizierter Huffman-Code einer Standardtabelle 1 genutzt. Ist die Länge größer als 63, so wird die Zahl n in einen Teil modulo 64 und einen Teil n div 64 aufgespalten und dann der entsprechende Code aus Tabelle 2 gewählt. Jede Zeile beginnt man einem weißen Paketwort, das eventuell der Länge Null entspricht. Schließlich ist der eindeutige Code 000000000001 als EOL-Code zu benutzen. Ein neues Bild beginnt ebenfalls mit diesem Code und eine Serie von Bildern mit drei EOLs. Die Methode ist übrigens auf eine 2D-Kompression erweitert worden.

14

8.3.2 Greedy-Verfahren

Greedy-Verfahren: zum Finden der Lösung eines Problems beginnen mit der leeren Lösung und bauen diese in jedem Schritt mit der derzeit optimal erscheinenden Möglichkeit aus.

Der Algorithmus von Prim ist ein Greedy-Verfahren: Er

beginnt mit einer Ecke und fügt zum schon konstruierten Baum immer eine Kante mit dem kleinsten Gewicht hinzu (die genau ein Ende im schon konstruierten Baum hat).

15

8.4 Kürzeste Wege in Graphen

„Single source shortest path problem“

Gegeben: • Gerichteter, gewichteter (alle Gewichte 0)

Graph,• Ein Knoten („Quelle“, „Startknoten“) v0 in dem

Graphen.

Gesucht: kürzeste Wege von v0 zu allen anderen Knoten (sofern es überhaupt jeweils einen Weg gibt).

16

Dijkstra Algorithmus

Algorithmus Dijkstra (v0,G) // vereinfacht: berechnet Länge der kürzesten Wege in G von v0 aus

für alle u { dist(u) := maxint }; gruen :=leer; gelb:= {v0}; dist(v0):=0;

While gelb != leer do   { wähle w aus gelb, so dass dist(w) minimal;      färbe w grün;      für jedes u aus succ(w) do         { falls u aus V\(gruen oder gelb)              { färbe u gelb;                dist(u):= dist(w)+ cost(w,u);}          falls u aus gelb               { wenn dist (u) > dist(w)+cost(w,u) dann                dist(u):=dist(w)+cost(w,u) }

}     } end;

17

Korrektheitsnachweis:

Behauptung: zu jedem Zeitpunkt gilt für jeden grünen Knoten u:

• Es gibt einen kürzesten Weg von v0 nach u, der nur grüne Knoten enthält.

• Seine Länge ist dist(u).

Beweis: durch Induktion. Man muss die Behauptung jeweils für den Knoten zeigen, der von gelb nach grün umgefärbt wird.

Aus dieser Behauptung folgt die Korrektheit des Algorithmus.

18

BeispielGegeben sei der folgende bewertete ungerichtete Graph A, bei dem bereits ein minimaler Spannbaum in roten Kanten ausgegeben ist.

G

A

B5

C

D

E

F2

554

6

7

3

3

22

3 1

19

Beispiel (2)

Wir wollen in einer Array-Implementation den kürzesten Wegebaum von A aus berechnen. Hier werden die Entfernungen von A in die erste Zeile eingetragen. Sodann wird das Minimum 5 gewählt. Dieser Abstand und der neue Punkt B werden in die zweite Zeile eingetragen, die Abstände upgedatet. Sodann wählen wir das nächste Minimum in der Tabelle mit 6 und den zugehörigen Punkt D. Auch jetzt werden die Abstände angepasst. In der ersten Spalte stehen die Abstände im Nächste-Wege-Baum von A.

A

B5

C

D

E

F2

554

6

7

3

3

22

3 1G

20

Dijkstra-Algorithmus

Algorithmus Dijkstra (v0,G) // vereinfacht: berechnet Länge der kürzesten Wege in G von v0 aus

für alle u { dist(u) := maxint }; gruen :=leer; gelb:= {v0}; dist(v0):=0;

While gelb != leer do   { wähle w aus gelb, so dass dist(w) minimal;      färbe w grün;      für jedes u aus succ(w) do         { falls u aus V\(gruen oder gelb)              { färbe u gelb;                dist(u):= dist(w)+ cost(w,u);}          falls u aus gelb               { wenn dist (u) > dist(w)+cost(w,u)               dann dist(u):=dist(w)+cost(w,u) }

}     } end;

21

Korrektheitsnachweis:

Behauptung: zu jedem Zeitpunkt gilt für jeden grünen Knoten u:

• Es gibt einen kürzesten Weg von v0 nach u, der nur grüne Knoten enthält.

• Seine Länge ist dist(u).

Beweis: durch Induktion. Man muss die Behauptung jeweils für den Knoten zeigen, der von gelb nach grün umgefärbt wird.

Aus dieser Behauptung folgt die Korrektheit des Algorithmus.

22

Beispiel

A B

C D

E F

30

10090

10 4040

10

20

30

Kürzester Wegebaum von A gesucht

23

Beispiel (2)

A B

C D

E F

30

10090

A B

C D

E F

30

10090

10 40

24

Beispiel (3)

A B

C D

E F

30

10090

10 40

40

40

10

A B

C D

E F

30

10090

10 40

40

40

10

5020

25

Beispiel (4)

A B

C D

E F

30

10090

10 40

40

40

10

5020

70

70

30A B

C D

E F

30

10090

10 40

40

40

10

5020

70

70

30 30

26

Beschreibung:

Idee: Lasse Teilbaum mit bereits ermittelten kürzesten Wegen wachsen.

Grüne Knoten: die Knoten, deren Nachfolger schon betrachtet wurden. = die Knoten, zu denen schon ein kürzester Weg ermittelt

ist.

Gelbe Knoten: die Nachfolger von grünen Knoten, die nicht selbst grün sind.

Rote Kanten: Kanten, die auf mindestens einem zur Zeit optimal erscheinenden Weg liegen.

Gelbe Kanten: Kanten, die als nicht optimal erkannt wurden.

27

Schleife

Eine Schleife des Algorithmus:

• Färbe den v0 nächsten gelben Knoten w grün.

• Färbe alle seine ungefärbten Nachfolger gelb.

• Trage ein/korrigiere die kürzesten Wege von v0 zu jedem der Nachfolger von w, ebenso ihre jeweilige Länge (dadurch werden ungefärbte Kanten evtl. rot, und rote Kanten evtl. gelb).

Korrektheit: siehe vereinfachter Algorithmus.

28

8.4.2 Implementierung des Algorithmus

a) Implementierung mit einer Adjazenzmatrix Sei V={1,...,n} und sei cost(i,j) die Kostenmatrix mit

Einträgen unendlich in Elementen, in denen keine Kante vorhanden ist. Man benutzt dann:

Type node = 1..n; var dist : array[node] of real; var father: array[node] of node; var grün: array [node] of boolean;

Der Array father stellt den Baum der roten Kanten dar, in dem zu jedem Knoten sein Vaterknoten festgehalten wird.

Die gelben Knoten werden nicht explizit dargestellt.

29

Jeder Schleifendurchlauf besteht dann aus folgenden Teilschritten:

• Der gesamte Array dist wird durchlaufen, um den gelben Knoten w mit minimalem Abstand zu finden.

Aufwand: O(n). • Die Zeile cost(w,*) der Matrix wird durchlaufen, um für

alle Nachfolger von w ggf. den Abstand (dist) und den Vater (father) zu korrigieren.

Aufwand: O(n).

Gesamtaufwand: O(n²), da n Schleifendurchläufe.

Ineffizient, außer wenn n sehr klein oder e nahe n² !

30

b) Implementierung mit Adjazenzlisten und Heap

Graph: gegeben durch durch Adjazenzliste mit Kosteneinträgen.

Wie eben:• Array dist• Array father

Außerdem:• Heap (als Array implementiert) aller gelben Knoten,

geordnet nach Abstand vom Ausgangsknoten,• Array heapaddress, der für jeden gelben Knoten die

Heapposition enthält.

31

SchleifendurchlaufJeder Schleifendurchlauf besteht dann aus folgenden Teilschritten:1. Entnimm den gelben Knoten w mit minimalem Abstand aus dem Heap Aufwand: O(log n).2. Finde in der Adjazenzliste die m(w) Nachfolger von w. Aufwand: O(m(w)). (i) Für jeden ,,neuen" gelben Nachfolger erzeuge einen Eintrag im Heap (ii) Für jeden ,,alten" gelben Nachfolger korrigiere ggf. seinen Eintrag im Heap. Seine Position dort ist über heapaddress zu finden. Da sein Abstandswert bei der Korrektur sinkt, kann der Eintrag im Heap ein Stück nach oben wandern. Die Heap-Adressen der vertauschten Einträge können in O(1) Zeit geändert werden. Aufwand für (i) und (ii): insgesamt O(m(w) log n). Aufwand für (2) insges.: O( log n • {Knoten w} m(w)) = O( e log n).Aufwand für (1) insges.: O(min{n,e} log n), da ein Element nur aus dem Heap

entnommen werden kann, wenn es vorher eingefügt wurde.

Gesamtaufwand: O(e log n)(Gesamter Platzbedarf: O(n+e))

32

8.5 Eulersche und Hamiltonsche Graphen

Ein zusammenhängender Graph G=(V,E) mit |E| 0 heißt Eulerscher Graph, wenn es einen

geschlossenen Kantenzug gibt, der jede Kante von G enthält; ein solcher Kantenzug heißt geschlossener Eulerscher Kantenzug oder Eulertour.

Satz:Ein zusammenhängender Graph G mit |E| 0 ist genau dann eulersch, wenn der Grad jeder Ecke gerade ist.

33

Beweis des Satzes:Erste Richtung: Besitzt der Graph eine Eulertour, so wird

jede Ecke bei einem Durchlauf von einer ankommenden und einer ausgehenden Kante getroffen. Alle diese Kanten sind verschieden, und damit ist der Eckengrad in jeder Ecke gerade.

Umgekehrte Richtung: Laufe von einer Ecke los, bis eine Ecke zum zweiten Mal

erreicht wird. Dann eliminiere diesen Zyklus (d.h. seine Kanten).

Man erhält einen oder mehr kleinere zusammenhängende Graphen mit geradem Eckengrad in jeder Ecke. Nach Induktionsannahme haben diese je eine Eulertour.

Aus diesen kann mit dem eliminierten Zyklus eine Gesamt-Eulertour konstruiert werden (verklebe die einzelnen Zyklen in gemeinsamen Ecken).

34

Beispiel: Königsberger Brückenproblem: gibt es einen Rundweg, der genau einmal über jede Brücke führt?

35

Hamiltonkreisproblem

Ein zusammenhängender Graph G = (V,E) heißt Hamiltonscher Graph, wenn es einen geschlossenen Weg gibt, der durch jede Ecke von G führt. Ein derartiger Weg heißt Hamiltonkreis.

8.5.2 Satz (Ore 1960) Sei G = (V, E) ein Graph ohne Schlingen und

Mehrfachkanten mit |V| >2. Gilt für die Eckengrade g aller nicht adjazenten Ecken a und b die Ungleichung g(a) + g(b) > |V| -1, so ist G hamiltonscher Graph.

36

Problem:

Gegeben: • ein gewichteter Graph und• eine Zahl L >0.Frage: gibt es einen Hamiltonkreis mit Gesamtlänge L ?

Mögliche Lösungsstrategie: alle Wege ausprobieren (Backtracking) exponentieller Aufwand.

Ein deterministischer Algorithmus, der das Problem in besserer als exponentieller Zeit löst, ist nicht bekannt!

Dieses Problem ist NP-vollständig!

37

Jetzt: Möglichst kurzen Hamiltonkreis berechnen.

Annahmen: • Der Graph ist vollständig.• Die Kantenbewertung erfüllt die Dreiecksungleichung.

Selbst dann: Greedy-Verfahren (wähle billigste nächste Kante) liefert nicht immer eine optimale Lösung. Der von dem Greedy-Verfahren produzierte Hamiltonkreis kann sogar um einen Faktor log(|V|) von einer optimalen Lösung entfernt sein!

38

Bessere Strategien

Bessere Strategie (unter den obigen Annahmen):

• Ermittle zunächst einen minimalen Spannbaum. • Durch Duplizieren der Kanten erhält man eine Eulertour.

Dabei werden die Doppel-Kanten im Baum einmal, jeder Knoten jedoch zweimal durchlaufen.

• Aus dieser Tour kann man jedoch einen Hamiltonkreis konstruieren, indem man im Kurzschlussverfahren zur nächsten noch nicht benutzten Ecke springt, bzw. falls es keine mehr gibt, zum Ausgangspunkt.

Dann ist der konstruierte Hamiltonkreis höchstens doppelt so lang wie ein kürzester Hamiltonkreis.  

39

Beispiel:

In diesem Beispiel ist der Spannbaum durch die fetten Kanten gegeben.

Wir duplizieren sie, starten im unteren rechten Knoten D und durchlaufen die Kanten 2 nach C , 1 nach F, 1 nach B, 2 nach E, überspringen den Rückweg nach B und wählen die gestrichelte Kante 2 nach A, schließen dann mit der gestrichelten Kante 3 ab zum Anfangsknoten D mit Gesamtgewicht des Kreises 11.

40

8.6 Bipartite Graphen, HeiratssatzDefinition Bipartite Graphen Sei G = (V, E) ein Graph ohne Schlingen. Existiert eine Zerlegung der Ecken in zwei nichtleere disjunkte Teilmengen V1 und V2, so dass für beliebige a und b aus Vi dann a und b

nicht adjazent sind, so heißt G bipartiter Graph mit der Zerlegung (V1, V2).

Ist G zusätzlich ohne Doppelkanten und sind alle Ecken a und b aus verschiedenen Teilmengen adjazent, so heißt G vollständig bipartit. Heiratssatz (König, Hall) Genau dann gibt es für einen bipartiten Graph G mit der Zerlegung V1 , V2 eine Menge von Verbindungskanten von

allen Elementen aus V1 nach V2, wenn für alle Teilmengen

V ' aus V1 die Kardinalzahl |N(V ')| der Menge der Nachbarn

N(V ') nicht kleiner ist als |V '|. Jedes Element aus V1 findet

somit einen Partner aus V2.

41

Exkurs: Das P-NP-Problem

Entscheidungsprobleme: algorithmische Probleme mit einer Ja/Nein-Antwort.

Sei f: N N eine Zahlenfunktion.

TIME(f) := {jedes Entscheidungsproblem derart, dass es einen Algorithmus gibt, der bei einer

Eingabe der Größe n die Antwort in höchstens f(n) Schritten berechnet.}

P := {p Polynom} TIME(p)

(P enthält die „(deterministisch) in Polynomzeit lösbaren Probleme“).

42

Klasse NP

Sei f: N N eine Zahlenfunktion.

NTIME(f) := {jedes Entscheidungsproblem derart, dass es einen „ratenden“ Algorithmus gibt, der bei einer

Eingabe der Größe n die Antwort in höchstens f(n) Schritten berechnet.}

NP := {p Polynom} NTIME(p)

(NP enthält die „nichtdeterministisch in Polynomzeit lösbaren Probleme“).

43

NP-Klasse Erläuterung

Eine „ratender“ Algorithmus darf während der Berechnung etwas „raten“, z.B. ein Binärwort, und zur weiteren Berechnung verwenden.

Er „löst“ ein Entscheidungsproblem, wenn er• durch Raten zur Antwort JA gelangen kann,

wenn JA stimmt,

und• bei jedem Raten zur Antwort NEIN gelangt,

wenn NEIN stimmt.

44

Problem des Handlungsreisenden(Traveling Salesman):

Gegeben: • ein gewichteter Graph und• eine Zahl L >0.Frage: gibt es einen Hamiltonkreis mit Gesamtlänge L ?

Mögliche Lösungsstrategie: alle Wege ausprobieren (Backtracking) -> exponentieller Aufwand.

Ein deterministischer Algorithmus, der das Problem in besserer als exponentieller Zeit löst, ist nicht bekannt!

Also offene Frage: ist das Problem des Handlungsreisenden in P?

45

Handlungsreisenden-Problem

Das Problem des Handlungsreisenden ist in NP:

Ein ratender, in Polynomzeit arbeitender Algorithmus für das Problem ist z.B:

1. Rate eine Reiseroute.

2. Prüfe, ob sie jede Stadt genau einmal enthält und nicht länger als die Schranke L ist.

46

P-NP-Problem

Klar: P ist eine Teilmenge von NP.

Das P-NP-Problem:

ist P eine echte Teilmenge von NP oder sind P und NP gleich?

Siehe dazu: http://www.claymath.org/millennium

47

Reduktion eines Problems auf eine anderes Problem

Seien P1 und P2 zwei Entscheidungsprobleme.

Dann ist P1 polynomiell auf P2 reduzierbar, wenn es eine in Polynomzeit berechenbare Funktion

f: {Eingaben für P1} {Eingaben für P2}gibt mit

P1(w) =JA P2(w) = JA

für alle Eingaben w für P1.

48

NP-vollständig

Ein Entscheidungsproblem P2 heißt NP-vollständig, wenn

1. es in NP ist, und

2. jedes Problem P1 in NP auf P2 polynomiell reduzierbar ist. .

Beispiel: das Problem des Handlungsreisenden ist NP-vollständig.

49

Bedeutung der NP-vollständigen Probleme

Sei P1 ein beliebiges NP-vollständiges Problem.

Dann ist:

P = NP P1 ist in P.

50

NP-vollständige Probleme

51Auszug: SchöningTheoretische Informatik