Schach/3x3/König/Knotenüberdeckungszahl/Aufgabe/Kommentar
Wir analysieren erst al den Graphen. Der Graph hat Knotenpunkte, wie man unmittelbar sieht. Der König kann um ein Feld in jede Richtung ziehen, horizontal, vertikal und diagonal. Entlang Die Anzahl der Kanten bestimmen wir entlang dieser Einteilung. Es gibt sechs horizontale, sechs vertikale und vier diagonale Kanten, also insgesamt Kanten. Eine Knotenüberdeckung muss all diese Kanten abdecken. Die Paarungszahl gibt eine erste Orientierung für die Knotenüberdeckungszahl, suchen wir also nach zueinander disjunkten Kanten. Da gibt es außen im Uhrzeigersinn vier Kanten, beginnend mit rechts oben und oben mittig. Die Paarungszahl ist also genau , da sie ja höchstens so groß wie die Hälfte der Punktanzahl sein kann. Somit ist die Knotenüberdeckungszahl zumindest . Wir behaupten, dass sie ist. Beispielsweise bildet der zentrale Punkt zusammen mit den weißen Feldern eine Knotenüberdeckung. Dies kann man sich mit einer Fallunterscheidung überlegen, ob der zentrale Punkt dazu oder nicht dazugehört.
