Zum Inhalt springen

Linearer Graph/Knotenüberdeckungszahl/Beispiel

Aus Wikiversity

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,…} und {2,4,6,…} 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 ⌊n2⌋ Knoten. Es gibt aber auch noch ganz andere minimale Knotenüberdeckungen, beispielsweise {1,3,4,6,7,9,10} bei  n=11.