Transcript
Universit¨ at zu K¨ oln Mathematisches Institut Dr. F. von Heymann M. Dostert, M.Sc.
Einf¨uhrung in die Mathematik des Operations Research Sommersemester 2016 — L¨ osungsskizzen zu Blatt 1 — Aufgabe 1.1 (10 Punkte) Finden Sie im rechtsstehenden gerichteten Graphen k¨ urzeste Wege von dem Knoten v1 zu jedem der anderen Knoten, sowie eine optimale Potentialfunktion. Begr¨ unden Sie, warum die von Ihnen angegebene Funktion eine optimale Potentialfunktion ist.
−2
v5
v2
1 v3 1
2
1 v4
1
v1
2
L¨ osung: Verwende z.B. den Algorithmus von Bellman-Ford, um k¨ urzeste 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 f¨ ur (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 f¨ ur alle u, v ∈ V gilt (u, v) ∈ A ⇔ (f (u), f (v)) ∈ A0 . a) Pr¨ ufen 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
L¨ osung: 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, ¨ berpruefung aller Kanten best¨ f (j) = f eine Bijektion sein k¨ onnte. U atigt diese Vermutung. b) Pr¨ ufen Sie, ob die beiden angegebenen Graphen isomorph sind. c
a
c
d
b
a
d
b
L¨ osung: 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 zusammenh¨ angend, wenn es f¨ ur 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 zusammenh¨ angend ist, dann gilt n − 1 ≤ m ≤ n(n − 1). L¨ osung: ¨ ber n. Im Induktions-Schritt w¨ n−1 ≤ m: Induktion u ahle einen Knoten v so, dass D0 = (V \{v}, A0 ) 0 zusammenh¨ angend ist, wobei A = {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 f¨ ur alle v ∈ V . Also |A| ≤ |V × V | − |{(v, v) : v ∈ V }| = n2 − n. Alternativ: Es gibt n2 M¨ oglichkeiten, zwei verschiedene Elemente aus V zu w¨ ahlen, und f¨ ur jede dieser M¨ oglichkeiten zwei Reihenfolgen. Also n 2 · n! |A| ≤ ·2= = n(n − 1). (n − 2)! 2! 2
