Graph/Knotenüberdeckung/Einführung/Textabschnitt

Definition

Es sei ${}G=(V,E)$ ein Graph. Eine Teilmenge ${}W\subseteq V$ heißt Knotenüberdeckung von ${}G$, wenn jede Kante mindestens einen Knoten aus ${}W$ trifft.

Es muss also jede Kante aus ${}G$ durch die Knoten aus ${}W$ 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 ${}v$ anliegenden Kanten mit ${}E(v)$ bezeichnet, so lautet die Bedingung, dass ${}W$ eine Knotenüberdeckung ist, einfach

${}E=\bigcup _{v\in W}E(v)\,.$

In einem kantenleeren Graphen ist die leere Menge eine Knotenüberdeckung.

Definition

Es sei ${}G=(V,E)$ ein Graph. Eine Knotenüberdeckung ${}W\subseteq V$ von ${}G$ heißt minimal, wenn ${}W\setminus \{w\}$ zu jedem ${}w\in W$ keine Knotenüberdeckung ist.

Definition

Es sei ${}G=(V,E)$ ein Graph. Eine Knotenüberdeckung ${}W\subseteq V$ von ${}G$ heißt optimal, wenn es keine Knotenüberdeckung von ${}G$ mit weniger als ${}{\#\left(W\right)}$ Elementen gibt.

Definition

Es sei ${}G=(V,E)$ ein Graph. Die minimale Anzahl von Knoten in einer Knotenüberdeckung von ${}G$ heißt Knotenüberdeckungszahl von ${}G$.

Beispiel

Es sei ${}G$ ein linearer Graph mit ${}n$ 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 ${}\{1,3,5,\ldots \}$ und ${}\{2,4,6,\ldots \}$ gegeben, wobei der letzte Knoten, ${}n-1$ oder ${}n$, davon abhängt, ob ${}n$ gerade oder ungerade ist. Bei ${}n$ gerade sind beide optimal, bei ${}n$ ungerade ist nur die zweite Knotenüberdeckung optimal. Die Knotenüberdeckungszahl beträgt in beiden Fällen ${}\left\lfloor {\frac {n}{2}}\right\rfloor$ Knoten. Es gibt aber auch noch ganz andere minimale Knotenüberdeckungen, beispielsweise ${}\{1,3,4,6,7,9,10\}$ bei ${}n=11$.

Beispiel

Bei einem Sterngraphen (sagen wir mit zumindest drei Knotenpunkten) ist die Knotenüberdeckungszahl gleich ${}1$, 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.