ナイトのグラフ

ナイトのグラフ
${\displaystyle 8\times 8}$ ナイトグラフ
頂点	${\displaystyle mn}$
エッジ	${\displaystyle 4mn-6(m+n)+8}$ （もし、）${\displaystyle n\geq 2}$ ${\displaystyle m\geq 2}$
胴回り	4 (もしと)${\displaystyle n\geq 3}$ ${\displaystyle m\geq 5}$
プロパティ	二分法
グラフとパラメータの表

グラフ理論において、ナイトグラフ、またはナイトツアーグラフは、チェス盤上のナイトの駒のすべての正当な動きを表すグラフです。このグラフの各頂点はチェス盤のマス目を表し、各辺はナイトの動き分離れた2つのマス目を結びます。より具体的には、ナイトグラフはチェス盤のナイトグラフです。^{[1]その頂点は}ユークリッド平面 の点として表すことができ、その直交座標は整数で、 と（チェス盤のマス目の中心の点）を持ち、2つの頂点間のユークリッド距離がのとき、それらの頂点は辺で結ばれています。 ${\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}}}$

ナイトグラフでは、頂点の数は です。 かつ の場合、辺の数は です（それ以外の場合は辺はありません）。ナイトグラフでは、これらを簡略化して、頂点の数は、辺の数は となります。^[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)}$

ナイトグラフ上のハミルトン閉路は（閉じた）ナイトツアーである。[ 1 ]^奇数のマス目を持つチェス盤にはツアーは存在しない。これはナイトグラフが二部グラフ（各マス目は2つの独立した集合のいずれかとして使用でき、ナイトの動きによってマス目の色が常に変化する）であり、頂点数が偶数の二部グラフのみがハミルトン閉路を持つことができるためである。偶数のマス目を持つチェス盤のほとんどはナイトツアーを持つ。シュヴェンクの定理は、どのチェス盤がナイトツアーを持ち、どのチェス盤がナイトツアーを持たないかを正確にリストアップしている。^[3]

トロイダル境界条件（ナイトが盤の端でブロックされず、反対側の端まで続くことを意味する）を持つように修正すると、ナイトのグラフは4次元ハイパーキューブグラフと同じになる。^[3]${\displaystyle 4\times 4}$

参照

• キングのグラフ
• クイーンのグラフ
• ルークのグラフ
• ビショップグラフ
• 格子グラフ

参考文献

1. アバーバッハ、ボニー；チェイン、オリン（1980）、レクリエーション数学による問題解決、ドーバー、p. 195、ISBN 9780486131740。
2. Sloane, N. J. A. (編). 「シーケンスA033996」.整数シーケンスのオンライン百科事典. OEIS財団.
3. Watkins, John J. (2004), 『チェス盤上の問題の数学的考察：頭を悩ませる人のためのパラドックス、パープレキシティ、そして数学的難問集』、プリンストン大学出版局、pp. 44, 68, ISBN 978-0-691-15498-5。

外部リンク

• ワイスタイン、エリック・W.「ナイトグラフ」。MathWorld。