Embed Size (px)
Citation preview
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
