Zum Inhalt springen

Schachfiguren/Planarer Graph/Aufgabe/Lösung

Aus Wikiversity


Zum Turm betrachten wir die Felder einer fixierten Zeile, die alle untereinander durch einen Turmzug erreichbar sind. Das ist also ein vollständiger Untergraph mit Knotenpunkten. Nach Beispiel ist dieser nicht planar und daher ist auch der Spielzuggraph zum Turm nicht planar. Für den Läufer betrachten wir Felder auf der Hauptidagonalen (oder Hauptnebendiagonalen). Dies ist ebenfalls ein vollständiger Graph mit Knotenpunkten und somit nicht planar. Der Spielzuggraph zur Dame ist aus dem gleichen Grund nicht planar.

Der Spielzuggraph zum König ist ebenfalls nicht planar. Er besitzt horizontale Kanten, vertikale Kanten und diagonale Kanten. Deshalb gibt es insgesamt Kanten. Bei einem planaren Graphen mit Knoten darf es aber nach Fakt  (1) höchstens

Kanten geben.