Punkte/Sprung/Direkte Erreichbarkeit/Graph/Beispiel

Die möglichen Springerzüge. Die mit einem Punkt markierten Felder sind diejenigen Felder, die der Springer (das Pferdchen) von seiner markierten Position aus mit einem Zug erreichen kann. Im zugehörigen Erreichbarkeitsgraphen muss also dieses Feld mit den acht angekreuzten Feldern durch eine Kante verbunden werden. Dies muss man für alle ${}64$ Felder machen.

Wir betrachten eine Ansammlung von mehr oder weniger geometrisch gegebenen Punkten, wo zugleich eine gewisse Bewegungsvorschrift oder Sprungvorschrift oder Zugvorschrift festgelegt ist, mit der man von einem Punkt aus zu gewissen anderen Punkten gelangen kann, indem man diese Bewegungsvorschrift ausführt. Die Bewegungsvorschrift soll symmetrisch sein, also umkehrbar, man kann die Bewegung rückgängig machen. Grundsätzlich kann die Bewegungsvorschrift willkürlich für jeden einzelnen Punkt festgelegt werden, interessantere Strukturen ergeben sich aber, wenn die Bewegungsvorschrift homogen unter Berücksichtigung der geometrischen Konfiguration festgelegt ist. Eine solche Situation wird durch einen Erreichbarkeitsgraphen beschrieben. Die Knotenpunkte sind die geometrischen Punkte und zwei Punkte sind miteinander durch eine Kante zu verbinden, wenn man durch einen einzigen direkten Sprung von dem einen Punkt zu dem anderen gelangen kann.

Im Unterschied zu Beispiel ist hier die Erreichbarkeit nicht transitiv, der Graph drückt die direkte Erreichbarkeit aus. Die dadurch festgelegte indirekte Erreichbarkeit, die durch eine Hintereinanderausführung von direkten Erreichbarkeiten gegeben ist, führt aber auch zu interessanten Fragestellungen, beispielsweise zur Frage, mit wie vielen Sprüngen man minimal von einem Punkt zu einem anderen Punkt kommen kann.

Bei einem Brettspiel hängen beispielsweise die erlaubten Züge von den Figuren ab. Die Felder des Brettspiels sind die Knotenmenge und jede Figur legt einen Erreichbarkeitsgraphen fest, den wir Spielzuggraph nennen. Eine Schachfigur (nicht der Bauer, dessen Bewegungsvorschrift ist nicht symmetrisch, da er nicht zurückziehen darf) ist durch ihre Zugmöglichkeiten festgelegt. Der Läufer kann diagonal beliebig weit ziehen, der Turm horizontal und vertikal beliebig weit, der König immer nur um eine Position, die Einschränkungen durch die Gesamtstellung spielen hier keine Rolle. Eine solche Interpretation spiegelt natürlich nur einen einzelnen Aspekt des Spiels wider.