10.7 Independent Set

Definition:

Sei G = (V,E) ungerichtet.

Für einen Independent Set I $\subseteq$ V gilt: i,j $\in$ I $\Rightarrow$ (i,j)$\notin$E .

Behauptung:

Sei K $\subseteq$ V ein Vertexcover $\iff$$\overline{K}$ ist ein Independent Set.

Beweis:

Annahme: $\exists$  x,y $\in$ $\overline{K}$ mit (x,y) $\in$ E $\Rightarrow$ x oder y im Vertexcover. Widerspruch!

Analog zeigt man: Sei I $\subseteq$ V ein Independent Set $\Rightarrow$ $\overline{I}$ ist ein Vertexcover.

$\Rightarrow$ Kleinstes Vertexcover liefert größtes Independent Set (und umgekehrt).

Beispiel:

Eine Gruppe von Jungen und Mädchen möchte eine Party feiern. Einige der Jungen haben mit einigen der Mädchen Streit. Wie muß die Gruppe zusammengestellt werden, damit möglichst viele an der Party teilnehmen, es aber zu keinem Streit kommt? Lösung: Suche max. Independent Set $\Rightarrow$ Ruhe auf Party.

Lösungsweg: Bestimme max. Independent Set mittels minimalem Vertexcover. Bestimme minimales Vertexcover mittels Maximum Matching.

Konstruktion eines minimalen Vertexcovers (in einem bipartiten Graphen):

Sei G = (V,E) bipartit (V = V₁ $\cup$ V₂ (disjunkt), wobei gilt: (x,y) $\in$ E $\Rightarrow$ x $\in$ V₁,y $\in$ V₂ .) M $\subseteq$ E sei Maximum Matching.

Von jeder Matchingkante aus führt maximal ein alternierender Weg zu einem freien Knoten.

(i)

Falls von einer Matchingkante aus ein alternierender Weg zu einem freien Knoten führt, dann bewerte den Endknoten der Matchingkante, der näher am Ende des alternierenden Weges (Ende = freier Knoten) liegt, mit `+' und den anderen Endpunkt mit `-'. Alle freien Knoten werden mit `-' bewertet. Auf einem alternierenden Weg, beginnend beim freien Knoten, folgt also auf ein `-' immer ein `+' und auf ein `+' immer ein `-'.

(ii)

Bei allen Matchingkanten m = (x,y) , von denen kein alternierender Weg zu einem freien Knoten führt, bewerte x mit `+' und y mit `-'.

Beobachtung:

Jede Matchingkante hat genau ein `+'.

Behauptung:

Jede Nichtmatchingkante k = (x,y) hat mindestens ein `+'.

Beweis:

(i)

k liegt innerhalb eines alternierenden Weges zu einem freien Knoten. (trivial)

(ii)

k liegt nicht innerhalb eines alternierenden Weges zu einem freien Knoten. Beh.: Beide zugehörigen Knoten x und y sind gematcht.

Bew.: Annahme: Die Behauptung ist falsch.

O.B.d.A. sei x nicht gematcht, d.h. x ist ein freier Knoten. Falls y ebenfalls nicht gematcht ist, dann ist M erweiterbar. Also muß y gematcht sein und k liegt somit innerhalb eines alternierenden Weges zu einem freien Knoten ( x ). (Widerspruch !)

(x,w) und (z,y) seien die beiden Matchingkanten. Von keiner dieser beiden Matchingkanten führt ein alternierende r Weg zu einem freien Knoten, da sonst k in einem alternierenden Weg zu einem freien Knoten liegen würde.

x und z werden also mit `+', w und y mit `-' bewertet.

Jede Kante in G hat also mindestens ein `+'.

Wähle als Vertexcover K alle mit `+' bewerteten Knoten.

Es gilt dann: |M| = |K| und wegen |M|$\le$|K'| für alle Vertexcover K' folgt: K ist minimal!