Hinweise zum 10. Übungsblatt
zu GIN1b, WS04/05
Prof. Dr. W. Conen
(Version 1.0alpha, 25.01.2005)
Dijkstra (Aufgabe 43)
b
4
3-
d
71
6
3
s=a
2
1
0
5
c
Runde
v*
D(a)
V(a)
D(b)
Init
-
0
-
3
1
b
2
c
3
d
4
e
54
1
3
V(b) D(c)
a
71
e
V(c)
D(d)
V(d)
D(e)
V(e)
5
a
1
a
1
a
4
b
7
b
1
a
6
c
7
c
Achtung, in Runde 3 passiert kein Update, es wird der erste „kurze“ Weg genommen
Dijkstra (Aufgabe 43)
b
4
3-
d
71
6
3
s=a
1
0
5
c
54
2
1
3
71
e
Kürzeste Wege:
a zu b: a  b, 3
a zu c: a  b  c, 4
a zu d: a  b  c  d, 6
a zu e: a b  c  e, 7 (Vorsicht, über d wäre falsch, s. Algo)
Prim (Aufgabe 45)
b
4
3-
d
41
2
3
s=a
2
1
0
5
c
Runde
v*
D(a)
V(a)
D(b)
Init
-
0
-
3
1
b
2
c
3
d
4
e
51
1
3
V(b) D(c)
a
31
e
V(c)
D(d)
V(d)
D(e)
V(e)
5
a
1
a
1
a
1
b
4
b
1
a
2
c
3
c
1
d
Prim (Aufgabe 45)
b
3-
b
d
41
2
71
6
d
71
e
3
3
a
3-
1
0
c
51
2
1
31
Prim Spannbaum,
Gewicht 3+1+2+1 = 7
1
0
e
c
54
2
3
Dijkstra Spannbaum,
Gewicht 3+1+2+3 = 9
Beide Fragen sind mit NEIN zu beantworten, die Spannbäume sind in diesem
Beispiel nicht identisch und der Prim‘sche Baum ist nicht immer besser (aber
nicht schlechter!) – einfaches Beispiel: a  b, also nur eine Kante (Prim und
Dijkstra-Spannbaum sind hier natürlich gleich)
Moore-Bellmann-Ford (Aufgabe 44)
-1
b 1/d
3/a
1
2/b
1 d
4 Runden,
jeweils alle Kanten
anschauen
(dargestellt ist
die erste Runde)
3
a
2
1
0
5
c 2/e
5/a
4/b
1
1
3/d
1 e
-1
Reihenfolge: (a,b),(b,a),(a,c),(c,a),(b,c),(c,b),(b,d),(d,b),(c,d),(d,c),(d,e),(e,d),(c,e),(e,c)
Runde
D(a)
V(a)
D(b)
V(b) D(c)
V(c)
D(d)
V(d)
D(e)
V(e)
Init
0
-
1
a
1
a
1
a
1
a
1
1
d
2
e
2
b
3
d
2
-1
d
0
e
0
b
1
d
3
-3
d
-2
e
-2
b
-1
d
4
-5
d
-4
e
-4
b
-3
d
Usw. Hier nicht sinnvoll anwendbar! Negative ungerichtete Kanten ergeben einen neg. Kreis!
Moore-Bellmann-Ford (Aufgabe 44)
-1
b 3/a
1
2/b
1 d
4 Runden,
jeweils alle Kanten
anschauen
(dargestellt ist
die erste Runde)
3
a
2
1
0
5
c 2/e
5/a
4/b
1
1
3/d
1 e
-1
Reihenfolge: (a,b),(b,a),(a,c),(c,a),(b,c),(c,b),(b,d),(c,d),(d,c),(d,e),(e,d),(e,c)
Runde
D(a)
V(a)
D(b)
Init
0
-
1
a
3
a
1
V(b) D(c)
V(c)
D(d)
V(d)
D(e)
V(e)
1
a
1
a
1
a
2
e
2
b
3
d
2
In der Runde 2,3 und 4 tritt keine Änderung mehr ein (nach 2 kann man stoppen!)
Bei anderen Reihenfolgen der Kantenbetrachtung gibt es das gleiche Endergebnis,
aber andere Rundenverläufe (fangen sie mal „hinten“ an, also mit (e,c) usw.).
Verändert man das (bd)-Gewicht auf -2, dann hat man wieder einen neg. Kreis!
Moore-Bellmann-Ford (Aufgabe 44)
-1
1
b 3/a
s=a
3
5
0
2
1
Leichter auszufüllende Tabelle mit
Zwischenschritten (Zeile eintragen,
wenn eine Änderung eintritt)
2/b
1 d
1
5/a
4/b
1
c 2/e
Reihenfolge: (a,b),(b,a),(a,c),(c,a),(b,c),(c,b)
,(b,d),(c,d),(d,c),(d,e),(e,d),(e,c)
3/d
1 e
-1
Runde
Bogen
D(a)
V(a)
D(b)
V(b)
D(c)
V(c)
D(d)
V(d)
D(e)
V(e)
Init
-
0
-
1
a
1
a
1
a
1
a
1
(a,b)
3
a
(a,c)
5
a
(b,c)
4
b
2
b
3
d
(b,d)
(d,e)
(e,c)
2
e
2
Wie gehabt gibt es keine Veränderung mehr in Runde 2, dann Abbruch.
Aufgabe 42






Zeigen Sie: Jeder ungerichtet Graph ohne Schleifen mit n >= 2 Knoten
enthält mindestens zwei Knoten mit gleichen Grad.
Wir nehmen an, dass G in bel. zusammenhängender Graph ohne
Schleifen mit mehr als einem Knoten ist.
Der maximale Grad eines Knotens in G ist (n-1), der minimale 1.
Die Menge der Gradzahlen, die auftreten können, ist also {1,...,n-1},
sie hat (n-1) Elemente.
Wir haben aber n Knoten, die auf (n-1)-Zahlen abgebildet werden, d.h.
wenigstens eine der Zahlen muß mindestens zweimal getroffen werden
(denn die Abbildung kann nicht injektiv von der Menge der Knoten in die
Menge der Gradzahlen sein!) – fertig!
Übrigens: Wenn G nicht zusammenhängend wäre, dann könnten wir jede
Zusammenhangskomponente mit mehr als einem Knoten für sich
betrachten mit dem obigen Argument: m Knoten in der Komponente, nur
(m-1) Gradzahlen verfügbar.
Wenn es keine Zusammenhangskomponente mit mehr als einem Knoten
gibt, dann muß es mindestens zwei einzelne unverbundene Knoten
geben, beide mit der Gradzahl 0, auch das erfüllt die Behauptung.

PPT