prev up inhalt next


10.6 Vertexcover


Definition:


Sei G = (V,E) ungerichtet.

Für ein Vertexcover K $\subseteq$ V gilt: (i,j) $\in$ E $\Rightarrow$ i $\in$ K oder j $\in$ K .

Ein Vertexcover heißt optimal $\iff$|K| minimal.

(Vertexcover = Knotenüberdeckung)


Beispiele:


i)
K = V
ii)


hier |K| = 4 (optimal).

In bipartiten Graphen läßt sich aus einem Maximum-Matching ein minimales Vertexcover konstruieren.

Es gilt: Sei M ein Matching, K ein Vertexcover $\Rightarrow$ |M|$\le$|K| .

Konstruktion: Siehe unten.


prev up inhalt next