< Schachfiguren < Planarer Graph < Aufgabe

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.
This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.