Transcript
Rolf Wanka Alexander Raß, Moritz M¨uhlenthaler
Erlangen, 25. April 2016
¨ Ubungen zur Vorlesung Randomisierte Algorithmen SS 2016 Blatt 3 AUFGABE 8: Sei G = (V, E) ein ungerichteter Graph, und seien s und t, s,t ∈ V , s 6= t, zwei besondere“ Knoten ” von G. Ein s-t-Schnitt C, C ⊆ E, ist ein Schnitt durch G, so daß es nach Entfernen von C aus G keinen Weg zwischen s und t mehr gibt. Betrachten Sie den Algorithmus C ONTRACT G RAPH aus der Vorlesung, der nun einen minimalen s-t-Schnitt berechnen soll. Der Algorithmus wird dazu so modifiziert, daß nie zwei Knoten zu einem neuen Knoten werden, wenn der dadurch s und t enthalten w¨urde. Dieser modifizierte Algorithmus soll nun auf den Graphen Hn angewandt werden, der aus den Knoten s, t und v1 , . . . , vn−2 besteht. Sowohl s, als auch t sind mit allen Knoten vi verbunden. Die Knoten v1 , . . . , vn−2 sind untereinander als ein Kreis verbunden. Die Abbildung zeigt H6 . v1
v2
s
t
v4
v3
(a) Wieviele minimale s-t-Schnitte gibt es in Hn ? (b) Zeigen Sie, daß die Wahrscheinlichkeit, daß einer dieser minimalen s-t-Schnitte den Kontraktionsvorgang u¨ berlebt, h¨ochstens ( 23 )n−2 ist. AUFGABE 9: Diese Aufgabe soll noch einmal das Gef¨uhl f¨ur die Varianz sch¨arfen. Sie haben einen normalen 6-seitigen W¨urfel mit den Zahlen 1 bis 6. Jede Seite liegt beim W¨urfeln mit Wahrscheinlichkeit 16 oben. Sei X die Zufallsvariable, die den erw¨urfelten Wert bezeichnet. (a) Berechnen Sie E[X]. (b) K¨onnen Sie mit (a) direkt E[X 2 ] berechnen? Bestimmen Sie E[X 2 ]. (c) Berechnen Sie Var[X] und σ[X].
