Graph/Knotenüberdeckung/Einführung/Textabschnitt
Es sei ein Graph. Eine Teilmenge heißt Knotenüberdeckung von , wenn jede Kante mindestens einen Knoten aus trifft.
Es muss also jede Kante aus durch die Knoten aus abgedeckt sein. Es geht also um die Überdeckung von Kanten durch Knoten. Ein einzelner Knoten deckt genau die an ihm anliegenden Kanten ab. Wenn man die an einen Knoten anliegenden Kanten mit bezeichnet, so lautet die Bedingung, dass eine Knotenüberdeckung ist, einfach
In einem kantenleeren Graphen ist die leere Menge eine Knotenüberdeckung.
Es sei ein Graph. Eine Knotenüberdeckung von heißt minimal, wenn zu jedem keine Knotenüberdeckung ist.
Es sei ein Graph. Eine Knotenüberdeckung von heißt optimal, wenn es keine Knotenüberdeckung von mit weniger als Elementen gibt.
Es sei ein Graph. Die minimale Anzahl von Knoten in einer Knotenüberdeckung von heißt Knotenüberdeckungszahl von .
Es sei ein linearer Graph mit Knotenpunkten. Dann muss in einer Knotenüberdeckung zumindest jeder zweite Knoten (in der natürlichen Reihenfolge auf einem linearen Graphen) vorkommen. Minimale Knotenüberdeckungen sind beispielsweise durch die Knotenfolgen und gegeben, wobei der letzte Knoten, oder , davon abhängt, ob gerade oder ungerade ist. Bei gerade sind beide optimal, bei ungerade ist nur die zweite Knotenüberdeckung optimal. Die Knotenüberdeckungszahl beträgt in beiden Fällen Knoten. Es gibt aber auch noch ganz andere minimale Knotenüberdeckungen, beispielsweise bei .
Bei einem Sterngraphen (sagen wir mit zumindest drei Knotenpunkten) ist die Knotenüberdeckungszahl gleich , man kann ja das Zentrum als einelementige Knotenüberdeckungsmenge nehmen. Dies ist die einzige optimale Knotenüberdeckung. Die Menge aller Blätter ist eine minimale Knotenüberdeckung, aber keine optimale Knotenüberdeckung.
