Strahlgraph/Knotenüberdeckungszahl/Aufgabe/Lösung

1. ${}\,$

   

2. Die Anzahl der Kanten ist ${}\sum _{j=1}^{k}n_{j}$ und die Anzahl der Knoten ist ${}1+\sum _{j=1}^{k}n_{j}$.
3. Wir betrachten ${}z$ 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 ${}z$ beteiligt ist. Ebenso bilden alle ungeraden Punkte eine minimale Knotenüberdeckung, an der ${}z$ nicht beteiligt ist.
4. Wenn ${}z$ 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 ${}\{1,2\},\{2,3\},\{3,4\},\ldots ,\{n_{j-1},n_{j}\}$ abdecken. Dazu braucht man minimal ${}\left\lfloor {\frac {n_{j}}{2}}\right\rfloor$ Punkte. Eine minimale Knotenüberdeckung, die ${}z$ enthält, braucht also ${}1+\sum _{j=1}^{k}\left\lfloor {\frac {n_{j}}{2}}\right\rfloor$ Knoten, und solche Überdeckungen gibt es wegen (3). Wenn ${}z$ nicht zu einer Knotenüberdeckung gehört, so muss diese den ersten Punkt auf jedem einzelnen Strahlen enthalten (um die Kante ${}\{z,1\}$) abzudecken. Weiter müssen auf jedem Strahl die Kanten ${}\{2,3\},\{3,4\},\ldots ,\{n_{j-1},n_{j}\}$ abgedeckt sein, wozu man minimal ${}\left\lfloor {\frac {n_{j}-1}{2}}\right\rfloor$ Punkte braucht. Eine minimale Knotenüberdeckung, die ${}z$ nicht enthält, braucht also

   ${}k+\sum _{j=1}^{k}\left\lfloor {\frac {n_{j}-1}{2}}\right\rfloor =\sum _{j=1}^{k}\left\lfloor {\frac {n_{j}+1}{2}}\right\rfloor \,$

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

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

   $\sum _{j=1}^{k}\left\lfloor {\frac {n_{j}+1}{2}}\right\rfloor ,$

   wenn ein ${}n_{j}$ ungerade sind, so ist die Knotenüberdeckungszahl gleich

   $1+\sum _{j=1}^{k}\left\lfloor {\frac {n_{j}}{2}}\right\rfloor .$

Zur gelösten Aufgabe