DAP2 Präsenzübung 14

C. Sohler
M. Bury, A. Krivo²ija
D. Mezlaf, A. Rey
SoSe 2016
DAP2 Präsenzübung 14
Besprechung: 20.7.2016 22.7.2016
: Graphen: Matchings
Ein
M in einem ungerichteten Graphen G = (V, E) ist eine Teilmenge der Kantenmenge, wobei keine zwei Kanten aus M einen gemeinsamen Knoten haben. Ein Matching M heiÿt
, falls es kein Matching M mit |M | > |M | gibt. Mit Match(G) = |M |
bezeichnen wir die Gröÿe eines Maximum-Matchings in G.
Sie haben in der Vorlesung bereits das Knotenübderdeckungsproblem kennengelernt. Zur Erinnerung: Eine Menge U ⊆ V heiÿt Knotenüberdeckung, wenn für jede Kante (u, v) ∈ E
mindestens einer der Endpunkte u, v in U enthalten ist. Mit Cover(G) = |U | bezeichnen wir
die Gröÿe einer minimalen Knotenüberdeckung in G.
Es gibt einen engen Zusammenhang zwischen Knotenüberdeckungen und Matchings in sogenannten
. Ein Graph G = (V, E) ist ein bipartiter Graph, falls es eine
Partition der Knotenmenge V = U ∪ W in zwei disjunkte Mengen U und W gibt, so dass für
alle Kanten (u, v) ∈ E entweder u ∈ U, v ∈ W oder u ∈ W, v ∈ U gilt.
Präsenzaufgabe 14.1
Matching
0
Maximum-Matching
0
bipartiten Graphen
u1
u2
u3
u4
w1
w2
w3
w4
w5
a) Zeigen Sie, dass Cover(G) ≥ Match(G) für alle Graphen G gilt.
b) Zeigen Sie, dass für einen bipartiten Graphen G = (V, E), in dem jeder Knoten höchstens zwei Nachbarn hat, Cover(G) = Match(G) gilt. Sie können annehmen, dass G
zusammenhängend ist.
c) (Bonus) Zeigen Sie nun per Widerspruch, dass für jeden bipartiten Graphen Cover(G) =
Match(G) gilt. Betrachten Sie dazu einen bipartiten Graphen G = (V, E) für den
Cover(G) > Match(G) gilt und |V | + |E| minimal ist.
• Was folgt aus b) für mindestens einen Knoten u in diesem Graphen?
1
•
Sei u der Knoten aus der vorherigen Beobachtung und v ein beliebiger Nachbar von
u. Betrachten Sie den Graphen G = (V , E ) mit V = V \{v} und E = E∩(V ×V ).
Machen Sie nun eine Fallunterscheidung, ob (1) Match(G ) < Match(G) oder (2)
Match(G ) = Match(G) gilt.
Konstruieren Sie in beiden Fällen mit Hilfe der Minimalitätseigenschaft von G eine
Knotenüberdeckung für G, dessen Gröÿe höchstens Match(G) ist, was ein Widerspruch zu unsere Annahme ist.
0
0
0
0
0
0
0
0
0
: Approximationsalgorithmus
Ein Matching M heiÿt
, falls es keine Kante e ∈ E \ M gibt, so dass M ∪ {e}
ein gültiges Matching ist.
a) Entwerfen Sie eine Algorithmus, der in einem Graphen G = (V, E) ein inklusionsmaximales Matching berechnet und dessen Laufzeit durch O(|V | + |E|) beschränkt ist. Nehmen
Sie hierfür an, dass der Graph in der Adjazenzlistendarstellung gegeben ist.
b) Zeigen Sie, dass die Gröÿe eines inklusionsmaximalen Matchings eine 2-Approximation
für die Gröÿe eines Maximum-Matchings ist und geben Sie einen Graphen an, in dem ein
inklusionsmaximales Matching existiert, das diesen Approximationsfaktor erreicht.
Präsenzaufgabe 14.2
inklusionsmaximal
2

Download Report