Граф ходів коня

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Граф ходів коня
Граф ходів коня 8 × 8
Вершинnm
Ребер4mn - 6(m + n) + 8
Обхват4 (якщо n ≥ 3, m ≥ 5)
Властивостідвочастковий

У теорії графів граф ходів коня — граф, що зображує всі можливі ходи коня на шахівниці; кожна вершина відповідає клітинці дошки, а ребра — можливим ходам[1].

Для графа ходів коня на дошці розміру число вершин дорівнює . Для дошки число вершин дорівнює , а число ребер дорівнює .

Знаходження гамільтонового шляху для графа ходів коня — це завдання про обхід дошки конем[1]. Теорема Швенка (Schwenk) дає розміри шахових дощок, для яких можливий обхід конем[2].

Див. також

[ред. | ред. код]

Примітки

[ред. | ред. код]