Knotenüberdeckung
Einfache Sprache
Eine Knotenüberdeckung (auch vertex cover) ist eine Teilmenge der Knotenmenge des Graphen, die von jeder Kante mindestens einen Endknoten enthält.
Def. Knotenüberdeckung
Sei $G=(V,E)$ ein Ungerichteter Graph. Eine Knotenüberdeckung ist eine Teilmenge $C\subseteq V$ so, dass alle Knoten aus $E$ incident zu mindestens einem Knoten in $C$ sind.
Alternativ: Es existiert keine Kante $e\in E$ mit $e\subseteq V\setminus C$.
Example
Hier zwei Graphen mit jeweils einer möglichen Knotenüberdeckung. Merke das Links eine Problem der minimale Knotenüberdeckung ist. Die Knotenüberdeckung rechts hingegen beinhaltet noch Knoten die “wegrationalisiert” werden könnten.
