Knights Diagramm

In der Graphentheorie ist ein Springergraph (auch Springertourgraph genannt ) ein Graph , der alle möglichen Züge der Schachfigur Springer auf einem Schachbrett darstellt . Jeder Knoten dieses Graphen repräsentiert ein Feld des Schachbretts, und jede Kante verbindet zwei Felder, die einen Springerzug voneinander entfernt sind. Genauer gesagt ist ein Springergraph der Springergraph eines Schachbretts. ^{[ 1 ]} Seine Knoten können als Punkte der euklidischen Ebene dargestellt werden , deren kartesische Koordinaten ganze Zahlen sind, wobei (x, y) und (x, y) die Mittelpunkte der Schachbrettfelder sind. Zwei Knoten sind durch eine Kante verbunden, wenn ihr euklidischer Abstand n beträgt . ${\displaystyle m\times n}$${\displaystyle m\times n}$${\displaystyle (x,y)}$${\displaystyle 1\leq x\leq m}$${\displaystyle 1\leq y\leq n}$${\displaystyle {\sqrt {5}}}$

Für einen Springergraphen ist die Anzahl der Knoten . Wenn und , dann ist die Anzahl der Kanten (ansonsten gibt es keine Kanten). Für einen Springergraphen vereinfachen sich diese Ausdrücke zu , sodass die Anzahl der Knoten und die Anzahl der Kanten ist . ^{[ 2 ]}${\displaystyle m\times n}$${\displaystyle nm}$${\displaystyle m>1}$${\displaystyle n>1}$${\displaystyle 4mn-6(m+n)+8}$${\displaystyle n\times n}$${\displaystyle n^{2}}$${\displaystyle 4(n-2)(n-1)}$

Ein Hamiltonkreis auf dem Springergraphen ist ein (geschlossener) Springerzug . ^{[ 1 ]} Ein Schachbrett mit einer ungeraden Anzahl von Feldern besitzt keinen Springerzug, da der Springergraph ein bipartiter Graph ist (jede Feldfarbe kann als eine von zwei unabhängigen Mengen verwendet werden , und die Springerzüge ändern stets die Feldfarbe) und nur bipartite Graphen mit einer geraden Anzahl von Knoten Hamiltonkreise besitzen können. Die meisten Schachbretter mit einer geraden Anzahl von Feldern besitzen einen Springerzug; der Satz von Schwenk liefert eine genaue Liste, welche dies tun und welche nicht. ^{[ 3 ]}

Wenn die Randbedingungen so modifiziert werden , dass ein Springer nicht durch den Rand des Bretts blockiert wird, sondern auf die gegenüberliegende Kante weiterzieht, ist der Springergraph identisch mit dem vierdimensionalen Hyperwürfelgraphen . ^{[ 3 ]}${\displaystyle 4\times 4}$

• Kings Grafik
• Queen's Graph
• Rooks Diagramm
• Bischofsdiagramm
• Gittergraph

• Weisstein, Eric W. „Knight Graph“ . MathWorld .