Für ein Vertexcover
K V gilt:
(i,j)
E
i
K oder j
K .
Ein Vertexcover heißt optimal |K| minimal.
(Vertexcover = Knotenüberdeckung)
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
|M|
|K| .
Konstruktion: Siehe unten.