Linearer Graph/Knotenüberdeckungszahl/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$.