Strahlgraph/Knotenüberdeckungszahl/Aufgabe

Wir betrachten Graphen

${}G=S(n_{1},n_{2},\ldots ,n_{k})\,$

von der folgenden Bauart: Es gibt ein Zentrum ${}z$, an das ${}k$ lineare Graphen (Strahlen) der Länge ${}n_{1},n_{2},\ldots ,n_{k}$ anliegen. Ansonsten gibt es keine weiteren Kanten.

1. Skizziere einen solchen Graphen für ${}k=5$ und

   ${}(n_{1},n_{2},n_{3},n_{4},n_{5})=(2,3,1,3,4)\,.$

2. Erstelle eine Formel für die Anzahl der Knoten und die Anzahl der Kanten von ${}G$.
3. Beschreibe eine minimale Knotenüberdeckung von ${}G$, die ${}z$ enthält, und eine minimale Knotenüberdeckung, die ${}z$ nicht enthält.
4. Bestimme die Knotenüberdeckungszahl von ${}G$.

Zur Lösung, Alternative Lösung erstellen