Strahlgraph/Knotenüberdeckungszahl/Aufgabe/Lösung


  1. Die Anzahl der Kanten ist und die Anzahl der Knoten ist .
  2. Wir betrachten als Nullpunkt und nennen einen Punkt des Graphen gerade, wenn sein Abstand zum Nullpunkt gerade ist, andernfalls ungerade. Dann bilden alle geraden Punkte eine minimale Knotenüberdeckung, an der beteiligt ist. Ebenso bilden alle ungeraden Punkte eine minimale Knotenüberdeckung, an der nicht beteiligt ist.
  3. Wenn zu einer Knotenüberdeckung gehört, so sind die daran direkt anliegenden Kanten auf den Strahlen abgedeckt. Man muss dann noch auf den einzelnen Strahlen die jeweils verbleibenden Kanten abdecken. Dazu braucht man minimal Punkte. Eine minimale Knotenüberdeckung, die enthält, braucht also Knoten, und solche Überdeckungen gibt es wegen (3). Wenn nicht zu einer Knotenüberdeckung gehört, so muss diese den ersten Punkt auf jedem einzelnen Strahlen enthalten (um die Kante ) abzudecken. Weiter müssen auf jedem Strahl die Kanten abgedeckt sein, wozu man minimal Punkte braucht. Eine minimale Knotenüberdeckung, die nicht enthält, braucht also

    Knoten, und solche Überdeckungen gibt es wegen (3).

    Es geht also um das Minimum dieser beiden Zahlen. Wenn alle gerade sind, so ist die Knotenüberdeckungszahl gleich

    wenn ein ungerade sind, so ist die Knotenüberdeckungszahl gleich