Einführung in die Mathematik des Operations Research

Universität zu Köln
Mathematisches Institut
Dr. F. von Heymann
M. Dostert, M.Sc.
Einführung in die Mathematik des Operations Research
Sommersemester 2016
— Lösungsskizzen zu Blatt 1 —
Aufgabe 1.1 (10 Punkte) Finden Sie im rechtsstehenden gerichteten Graphen kürzeste Wege von dem Knoten v1 zu jedem der anderen Knoten, sowie eine optimale Potentialfunktion. Begründen Sie, warum die
von Ihnen angegebene Funktion eine optimale Potentialfunktion ist.
−2
v5
v2
1
v3
1
2
1
v4
1
v1
2
Lösung: Verwende z.B. den Algorithmus von Bellman-Ford, um kürzeste Wege zu finden. Wir
erhalten, dass d5 = d4 ist, sowie die Wege
P2 = {(v1 , v2 )},
P3 = {(v1 , v2 ), (v2 , v3 )},
P4 = {(v1 , v2 ), (v2 , v3 ), (v3 , v5 ), (v5 , v4 )},
P5 = {(v1 , v2 ), (v2 , v3 ), (v3 , v5 )}.
Dann ist dist(v1 , vi ) = d4 (vi ) = l(Pi ), und wir setzen p(vi ) = dist(v1 , vi ). Dann gilt für (vi , vj ) im
Graphen (nach Def. des Algorithmus, und da d4 = d5 ):
p(vj ) − p(vi ) = d5 (vj ) − d4 (vi ) ≤ l((vi , vj ))
und somit ist p ein Potential. Es ist optimal, da dist(v1 , vi ) = p(v1 ) − p(vi ) gilt.
Aufgabe 1.2 (5 + 5 = 10 Punkte) Zwei gerichtete Graphen D = (V, A) und D0 = (V 0 , A0 ) sind
isomorph, wenn es eine bijektive Abbildung f : V → V 0 gibt, so dass für alle u, v ∈ V gilt
(u, v) ∈ A ⇔ (f (u), f (v)) ∈ A0 .
a) Prüfen Sie, ob die beiden angegebenen Graphen isomorph sind.
f
h
e
a
g
g
a
b
h
i
e
d
f
c
b
c
d
j
j
i
Lösung:
Sei C = {a1 , . . . , ak } ein gerichteter Kreis im linken Graph, mit ai = (vi−1 , vi ). Falls die
Graphen isomorph sind, so bildet die bijektive Abbildung f den Kreis auf einen gerichteten
Kreis
f (C) = {(f (v0 ), f (v1 )), . . . , (f (vk−1 ), f (vk ))}
im rechten Graphen ab.
Beobachte, dass beide Graphen genau einen gerichteten Kreis mit 8 Kanten haben:
Cl = {(a, c), (c, e), (e, b), (b, i), (i, j), (j, f ), (f, g), (g, h), (h, a)}
Cr = {(a, g), (g, f ), (f, e), (e, d), (d, h), (h, i), (i, b), (b, c), (c, a)}.
Außerdem sind d 6∈ Cl und j 6∈ Cr die einzigen Knoten ausserhalb der Kreise. Betrachtet
man nun noch die Adjazenzen von d links und j rechts, kommt man zu der Vermutung dass
f (a) = i, f (b) = a, f (c) = b, f (d) = j, f (e) = c, f (f ) = e, f (g) = d, f (h) = h, f (i) = g,
f (j) = f eine Bijektion sein könnte. Überpruefung aller Kanten bestätigt diese Vermutung.
b) Prüfen Sie, ob die beiden angegebenen Graphen isomorph sind.
c
a
c
d
b
a
d
b
Lösung:
Im linken Graph gibt es keine Kante mit Endknoten d. Im Gegensatz dazu gilt im rechten Graphen,
dass jeder Knoten in mindestens einer Kante als Endknoten erscheint. Also sind die Graphen nicht
isomorph.
Aufgabe 1.3 (10 Punkte) Sei D = (V, A) ein gerichteter Graph mit n Knoten und m Kanten. Der
Graph D ist zusammenhängend, wenn es für alle s, t ∈ V eine Umorientierung der Kanten gibt
(d.h. (u, v) ∈ A kann ersetzt werden durch (v, u)), so dass ein s-t-Weg existiert.
Zeigen Sie: Falls D zusammenhängend ist, dann gilt n − 1 ≤ m ≤ n(n − 1).
Lösung:
n−1 ≤ m: Induktion über n. Im Induktions-Schritt wähle einen Knoten v so, dass D0 = (V \{v}, A0 )
zusammenhängend ist, wobei A0 = {a ∈ A : v 6∈ a} ist. (Wieso geht das?) Es gibt mindestens eine
Kante in A \ A0 , somit folgt die Behauptung.
m ≤ n(n − 1): Es ist A ⊆ V × V , und (v, v) 6∈ A für alle v ∈ V . Also
|A| ≤ |V × V | − |{(v, v) : v ∈ V }| = n2 − n.
Alternativ: Es gibt n2 Möglichkeiten, zwei verschiedene Elemente aus V zu wählen, und für jede
dieser Möglichkeiten zwei Reihenfolgen. Also
n
2 · n!
|A| ≤
·2=
= n(n − 1).
(n − 2)! 2!
2

Download Report