Vortrag über Graphen Von Jörg Hendricks Inhalt kurze Einführung Begriffserklärung Darstellung im...

Vortrag über Graphen

Von Jörg Hendricks

Inhalt

• kurze Einführung

• Begriffserklärung

• Darstellung im Computer

• Algorithmen für Graphen

Einleitung

Was sind Graphen?

• Knoten

• Kanten

• Werkzeug zur anschaulichen Darstellung

• Werkzeug zur Problemlösung

Begriffserklärung

Allgemeines• Schlinge• Kantenzug / Weg• erreichbarer Knoten• Teilgraph• Zyklus• Valenz

Eigenschaften• gerichtet / ungerichtet• gewichtet• licht, dicht, vollständig• schlicht• zyklisch

Begriffserklärung (Fortsetzung)

Sonderformen

• Liste

• Baum

• Wald

• Spannbaum

• Netz, Netzwerk, Netzplan

Darstellung im Computer

FE

DB CA

G

I JH

Bitte Skript zur Hand nehmen! Danke!

Inzidenzmatrix

E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 E12 E13 E14 E15A +1 +1 0 0 0 0 0 0 0 0 0 0 0 0 0B 0 0 +1 +1 0 0 0 0 0 0 0 0 0 0 0C 0 0 0 0 +1 0 0 0 0 0 0 0 0 0 0D 0 0 0 0 0 +1 0 0 0 0 0 0 0 0 0E -1 0 -1 0 0 0 +1 -1 +1 0 0 0 0 0 0F 0 -1 0 -1 0 0 -1 +1 0 +1 +1 0 0 0 0G 0 0 0 0 -1 -1 0 0 0 0 0 +1 +1 0 0H 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0I 0 0 0 0 0 0 0 0 0 -1 0 -1 0 +1 -1J 0 0 0 0 0 0 0 0 0 0 -1 0 -1 -1 +1

Inzidenzliste

E1 (A , E) E5 (C , D) E9 (E , H) E13 (G , J)

E2 (A , F) E6 (D , G) E10 (F , I) E14 (I , J)

E3 (B , E) E7 (E , F) E11 (F , J) E15 (J , I)

E4 (B , F) E8 (F , E) E12 (G , I)

Adjazenzmatrix

A B C D E F G H I J SpaltensummenA 0 0 0 0 1 1 0 0 0 0 2B 0 0 0 0 1 1 0 0 0 0 2C 0 0 0 0 0 0 1 0 0 0 1D 0 0 0 0 0 0 1 0 0 0 1E 0 0 0 0 0 1 0 1 0 0 2F 0 0 0 0 1 0 0 0 1 1 3G 0 0 0 0 0 0 0 0 1 1 2H 0 0 0 0 0 0 0 0 0 0 0I 0 0 0 0 0 0 0 0 0 1 1J 0 0 0 0 0 0 0 0 1 0 1

Zeilensummen 0 0 0 0 3 3 2 1 3 3 15Anzahl der Kanten

Adjazenzliste

A B C D E F G H I JE E G G F E I J IF F H I J

J

Algorithmen für Graphen

und deren Anwendung

Die Algorithmen werden anhand von Beispielen vorgestellt.

(Um den Ablauf verfolgen zu können bitte das Skript zur Hand nehmen) Danke!

Durchsuchen von Graphen

• GrundgedankeWegsuche in einem Graphen

Beispiel:

Labyrinth

Vom Eingang Ausgang

gibt es diesen Weg überhaupt?

Algorithmen:• Tiefensuche• Breitensuche

Tiefensuche (Verbindung vorhanden?)

Start

Ende

5 4

6

7321

Wir werden uns den Algorithmus nun am obenstehenden Graphen verdeutlichen.

Weg von 5 (Start) zu 7 (Ende).

Teil 1

5Start

Zunächst wird die 5 als Startknoten markiert und auf den Stack gelegt.

4

1

Man nimmt die 5 vom Stack und trägt sie bei den erreichbaren Knoten als Vorgänger ein.

Die Markierung eines besuchten Knotens ist selbstverständlich und wird daher nicht extra erwähnt.

Teil 2

Als nächstes wird die 4 vom Stack genommen

45Start

1

6

Da die 6 von 4 aus erreichbar ist, wird ihr die 4 als Vorgänger eingetragen und die 6 auf den Stack gelegt

Teil 3

45Start

1

6

Nun wird die 6 vom Stack genommen und auf erreichbare Knoten untersuchtEs gibt aber keine, daher wird das nächste Element vom Stack genommen

Teil 4

1

45Start

6

Da die 6 keinen Nachfolger hatte und wir den nächsten Knoten vom Stack nehmen sollten, ist nun die 1 an der Reihe

2

Wir nehmen die erreichbaren Nachfolger und legen sie auf den Stack

Teil 5

1

45Start

6

2 3

Wir nehmen die 2 vom Stack und testen die NachfolgerHierbei finden wir die 3 und legen sie auf den StackDa die 2 eine Schleife hat, finden wir die 2 zwar auch als Nachfolger, aber da sie schon einmal besucht wurde, wird sie nicht auf den Stack gelegt

Teil 6

3 7 Ende

Von 3 aus finden wir die 4 und die 7, die 4 wurde bereits besucht und ist daher uninteressantDie 7 wandert auf den Stack

21

45Start

6

Teil 7

7 Ende321

45Start

6

Wenn wir nun von der 7 aus weitere Knoten suchen wollen, gibt es zwei Dinge:

• 7 ist der Endpunkt

• 7 hat keine Nachfolger mehr ( zumindest in diesem Beispiel )

Der Tiefensuch-Algorithmus ist beendet

Nun wollen wir uns noch die zugehörige Tabelle ansehen.

Der gefundene Weg lautet:

• 5 (Start)

• 1

• 2

• 3

• 7 (Ende)

Teil 8

Schritte

Vorg [1]

Vorg [2]

Vorg [3]

Vorg [4]

Vorg [5]

Vorg [6]

Vorg [7]

Stack

1.

-

-

-

-

S

-

-

(5)

2.

5

-

-

5

-

-

-

(4)

(1)

3.

5

-

-

5

-

4

-

(6)

(1)

4.

5

-

-

5

-

4

-

(1)

5.

5

1

-

5

-

4

-

(2)

6.

5

1

2

5

-

4

-

(3)

7.

5

1

2

5

-

4

3

(7)

Breitensuche (topologisches Sortieren)

1 2 3

4 5 6

7

Wir werden uns den Algorithmus nun am obenstehenden Graphen verdeutlichen.

Teil 1

1

Zunächst wird das Feld der Eingangsgrade initialisiert und die Knoten mit dem Eingangsgrad 0 werden in die Queue eingefügt.

Schritte

Nummer

Nr.[1]

[2]

[3]

[4]

[5]

[6]

[7]

0.

0

-

-

-

-

-

-

-

Schritte

Queue

E-Grad[1]

[2]

[3]

[4]

[5]

[6]

[7]

0.

(1)

0

2

1

1

1

1

2

Teil 2

1

4

Der Knoten 1 wird aus der Queue genommen und erhält die Nummer 1. Nun werden seine Nachbarknoten untersucht und diejenigen mit Eingangsgrad 1 in die Queue eingereiht. Somit wandert die 4 in die Queue. Die 2 hat noch Vorgänger und wird dadurch nicht eingereiht. Aber ihr Eingangsgrad wird reduziert.

Schritte

Nummer

Nr.[1]

[2]

[3]

[4]

[5]

[6]

[7]

0.

0

-

-

-

-

-

-

-

1.

1

1

-

-

-

-

-

-

Schritte

Queue

E-Grad[1]

[2]

[3]

[4]

[5]

[6]

[7]

0.

(1)

0

2

1

1

1

1

2

1.

(4)

0

1

1

0

1

1

2

1 2

Teil 3

5

Die 4 wird aus der Queue entnommen und erhält die nächste Nummer. Die 5 wird als Nachbarknoten mit Eingangsgrad 1 auf E-Grad 0 gesetzt und in die Schlange eingereiht.

Schritte

Nummer

Nr.[1]

[2]

[3]

[4]

[5]

[6]

[7]

0.

0

-

-

-

-

-

-

-

2.

2

1

-

-

2

-

-

-

Schritte

Queue

E-Grad[1]

[2]

[3]

[4]

[5]

[6]

[7]

0.

(1)

0

2

1

1

1

1

2

2.

(5)

0

1

1

0

0

1

2

1.

1

1

-

-

-

-

-

-

1.

(4)

0

1

1

0

1

1

2

2

1 2

4

1

Teil 4

Nachdem wir der 5 die Nummer 3 zugewiesen haben, untersuchen wir auch ihre Nachbarn und erhalten 2 und 6 jeweils mit E-Grad 1. Somit werden beide der Reihe nach in die Queue gesetzt.

Schritte

Nummer

Nr.[1]

[2]

[3]

[4]

[5]

[6]

[7]

0.

0

-

-

-

-

-

-

-

2.

2

1

-

-

2

-

-

-

1.

1

1

-

-

-

-

-

-

Schritte

Queue

E-Grad[1]

[2]

[3]

[4]

[5]

[6]

[7]

0.

(1)

0

2

1

1

1

1

2

2.

(5)

0

1

1

0

0

1

2

1.

(4)

0

1

1

0

1

1

2

52

1 2

4

1

3.

3

1

-

-

2

3

-

-

3.

(2/6)

0

1

1

0

0

0

2

63

Teil 5

Nun wird die nächste Zahl (2) aus der Queue genommen und bekommt die folgende Nummer. Wir untersuchen ihre Nachfolger und finden die 3, die nun auch in die Queue gereiht wird.

Schritte

Nummer

Nr.[1]

[2]

[3]

[4]

[5]

[6]

[7]

0.

0

-

-

-

-

-

-

-

2.

2

1

-

-

2

-

-

-

1.

1

1

-

-

-

-

-

-

3.

3

1

-

-

2

3

-

-

Schritte

Queue

E-Grad[1]

[2]

[3]

[4]

[5]

[6]

[7]

0.

(1)

0

2

1

1

1

1

2

2.

(5)

0

1

1

0

0

1

2

1.

(4)

0

1

1

0

1

1

2

3.

(2/6)

0

1

1

0

0

0

2

52

1 2

4

1

63

43

4.

4

1

4

-

2

3

-

-

4.

(6/3)

0

0

0

0

0

0

2

Teil 6

Die nächste Zahl in der Queue ist die 6. Also bekommt sie die nächste Nummer und wir betrachten Ihre Nachfolger. Der Nachfolger ist die 7, sie hat aber den E-Grad 2 und wird daher nur um 1 reduziert, kommt aber nicht in die Queue.

Schritte

Nummer

Nr.[1]

[2]

[3]

[4]

[5]

[6]

[7]

0.

0

-

-

-

-

-

-

-

2.

2

1

-

-

2

-

-

-

1.

1

1

-

-

-

-

-

-

3.

3

1

-

-

2

3

-

-

4.

4

1

4

-

2

3

-

-

Schritte

Queue

E-Grad[1]

[2]

[3]

[4]

[5]

[6]

[7]

0.

(1)

0

2

1

1

1

1

2

2.

(5)

0

1

1

0

0

1

2

1.

(4)

0

1

1

0

1

1

2

3.

(2/6)

0

1

1

0

0

0

2

4.

(6/3)

0

0

0

0

0

0

2

5

5.

5

1

4

-

2

3

5

-

5.

(3)

0

0

0

0

0

0

1

4

52

1 2

4

1

63

3 7

Teil 7

Die nächste Zahl ist die 3. Wir nehmen sie aus der Queue und weisen ihr die nächste Nummer zu. Wir überprüfen die Nachfolger und stoßen auf die 7. Diese wandert nun, da sie den E-Grad 1 hat in die Queue.

Schritte

Nummer

Nr.[1]

[2]

[3]

[4]

[5]

[6]

[7]

0.

0

-

-

-

-

-

-

-

2.

2

1

-

-

2

-

-

-

1.

1

1

-

-

-

-

-

-

3.

3

1

-

-

2

3

-

-

4.

4

1

4

-

2

3

-

-

5.

5

1

4

-

2

3

5

-

Schritte

Queue

E-Grad[1]

[2]

[3]

[4]

[5]

[6]

[7]

0.

(1)

0

2

1

1

1

1

2

2.

(5)

0

1

1

0

0

1

2

1.

(4)

0

1

1

0

1

1

2

3.

(2/6)

0

1

1

0

0

0

2

4.

(6/3)

0

0

0

0

0

0

2

5.

(3)

0

0

0

0

0

0

1

5

4

52

1 2

4

1

63

3 7

6.

6

1

4

6

2

3

5

-

6.

(7)

0

0

0

0

0

0

0

6

Teil 8

Als letzte Zahl nehmen wir die 7 aus der Queue und geben ihr die Nummer 7. Sie hat keine Nachfolger mehr und somit kann der Algorithmus beendet werden.

Schritte

Nummer

Nr.[1]

[2]

[3]

[4]

[5]

[6]

[7]

0.

0

-

-

-

-

-

-

-

2.

2

1

-

-

2

-

-

-

1.

1

1

-

-

-

-

-

-

3.

3

1

-

-

2

3

-

-

4.

4

1

4

-

2

3

-

-

5.

5

1

4

-

2

3

5

-

6.

6

1

4

6

2

3

5

-

Schritte

Queue

E-Grad[1]

[2]

[3]

[4]

[5]

[6]

[7]

0.

(1)

0

2

1

1

1

1

2

2.

(5)

0

1

1

0

0

1

2

1.

(4)

0

1

1

0

1

1

2

3.

(2/6)

0

1

1

0

0

0

2

4.

(6/3)

0

0

0

0

0

0

2

5.

(3)

0

0

0

0

0

0

1

6.

(7)

0

0

0

0

0

0

0

5

4

52

1 2

4

1

63

3 76

7.

7

1

4

6

2

3

5

7

7.

(-)

0

0

0

0

0

0

0

7

Teil 9 :Nachfolgend erhalten wir die folgende Numerierung der Knoten

Knoten 1 2 3 4 5 6 7Nummer 1 4 6 2 3 5 7

Nummer 1 2 3 4 5 6 7Knoten 1 4 5 2 6 3 7

Minimaler Weg

GrundgedankeKürzester Weg durch den Graphen

Beispiel:

Fahrt von Hamburg nach München

Welcher Weg ist:

• der kürzeste ?

• der schnellste ?

Algorithmen• Dijkstra• Floyd

Prioritätsgesteuerte Breitensuche

(Algorithmus nach Dijkstra)

Teil 1

a b

C

f g

d

e

0

4

1

4

2

1

31

3

2

An diesem Beispiel wollen wir uns den Algorithmus nach Dijkstra verdeutlichen

Wir suchen „kürzesten“ oder „kostengünstigsten“ Weg von a nach g

Teil 2

a b

C

f g

d

e

0

4

1

4

2

1

31

3

2

Schritt

Kosten[a]

[b]

[c]

[d]

[e]

[f]

[g]

0.

2.

0

0

1.

0

3.

0

0

1

4.

0

0

1

3

5.

0

0

1

3

4

6.

0

0

1

3

4

4

7.

0

0

1

3

4

4

5

Schritt

Vorg [a]

[b]

[c]

[d]

[e]

[f]

[g]

P-Queue

0.

-

-

-

-

-

-

-

(0,a)

2.

-

a

b

b

-

a

-

(1,c)(4,f)(4,d)

1.

-

a

-

-

-

a

-

(0,b)(4,f)

3.

-

a

b

c

-

a

-

(3,d)(4,f)

4.

-

a

b

c

d

a

-

(4,f)(4,e)

5.

-

a

b

c

d

a

f

(4,e)(7,g)

6.

-

a

b

c

d

a

e

(5,g)

7.

-

a

b

c

d

a

e

(-,-)

Teil 3

Der kürzeste Weg, den man in diesem Graphen nehmen kann, hat die „Länge“ 5 und sieht wie folgt aus:

a

b

c

d

e

g

Knoten

0

1

2

1

1

= 5

Kosten

a b

C

f g

d

e

0

4

1

4

2

1

31

3

2

Kürzester Weg für alle Knoten

(Algorithmus nach Floyd)

Teil 1

a b

C

f g

d

e

0

4

1

4

2

1

31

3

2

K1 A B C D E F GA 0 0 4 B 0 1 4 C 0 2 D 0 1 E 0 3 1F 0 3G 0

Teil 2

a b

C

f g

d

e

0

4

1

4

2

1

31

3

2

K2 A B C D E F GA 0 0 1 4 4 7B 0 1 3 5 C 0 2 3 D 0 1 4 2E 0 3 1F 0 3G 0

Teil 3

a b

C

f g

d

e

0

4

1

4

2

1

31

3

2

K3 A B C D E F GA 0 0 1 3 5 4 7B 0 1 3 4 8 6C 0 2 3 6 4D 0 1 4 2E 0 3 1F 0 3G 0

Teil 4

a b

C

f g

d

e

0

4

1

4

2

1

31

3

2

K4 A B C D E F GA 0 0 1 3 4 4 6B 0 1 3 4 7 5C 0 2 3 6 4D 0 1 4 2E 0 3 1F 0 3G 0

Teil 5

a b

C

f g

d

e

0

4

1

4

2

1

31

3

2

K5 A B C D E F GA 0 0 1 3 4 4 5B 0 1 3 4 7 5C 0 2 3 6 4D 0 1 4 2E 0 3 1F 0 3G 0

Teil 6

a b

C

f g

d

e

0

4

1

4

2

1

31

3

2

K6 A B C D E F GA 0 0 1 3 4 4 5B 0 1 3 4 7 5C 0 2 3 6 4D 0 1 4 2E 0 3 1F 0 3G 0

ENDE

Vielen Dank für Ihr Interesse

Auf Wiedersehen

sagt Ihr

Jörg Hendricks