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

Перейти к навигации Перейти к поиску

Граф ходов коня
Граф ходов коня 8 × 8
Вершин	nm
Рёбер	4mn - 6(m + n) + 8
Обхват	4 (если n ≥ 3, m ≥ 5)

В теории графов графом ходов коня называется граф, изображающий все возможные ходы коня на шахматной доске — каждая вершина соответствует клетке на доске, а рёбра соответствуют возможным ходам^[1].

Для графа ходов коня на доске размера $n\times m$ число вершин равняется $nm$ . Для доски $n\times n$ число вершин равняется $n^{2}$ , а число рёбер равняется $4(n-2)(n-1)$ .

Нахождение гамильтонова пути для графа ходов коня — это задача об обходе доски конём^[1]. Теорема Швенка (Schwenk) даёт размеры шахматных досок, для которых возможен обход конём^[2].

См. также

Примечания

↑ ¹ ² Orin Averbach, Orin Chein. Problem Solving Through Recreational Mathematics. — Dover, 1980. — ISBN 9780486131740.
↑ John J. Watkins. Across the Board: The Mathematics of Chessboard Problems. Paradoxes, perplexities, and mathematical conundrums for the serious head scratcher. — Princeton University Press, 2012. — С. 44. — ISBN 9780691154985.

Похожие исследовательские статьи

Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:

как и геометрия, обладает наглядностью;
как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
не имеет громоздкого математического аппарата ;
имеет выраженный прикладной характер.

Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.

Дерево — связный ациклический граф. Связность означает наличие маршрута между любой парой вершин, ацикличность — отсутствие циклов. Отсюда, в частности, следует, что число рёбер в дереве на единицу меньше числа вершин, а между любыми парами вершин имеется один и только один путь.

<span class="mw-page-title-main">Теорема Кёнига (комбинаторика)</span>

В теории графов теорема Кёнига , доказанная Денешем Кёнигом в 1931, утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах. Независимо была открыта, в том же 1931, Йенё Эгервари в несколько более общем виде для случая взвешенных графов.

Теорема о четырёх красках утверждает, что всякую расположенную на плоскости или на сфере карту можно раскрасить не более чем четырьмя разными цветами (красками) так, чтобы любые две области с общим участком границы имели разный цвет. При этом области должны быть связными, а граница должна быть неточечной.

Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.

По́лный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна. Полный граф с $\text{[math]}$ вершинами имеет $\text{[math]}$ рёбер и обозначается $\text{[math]}$ . Является регулярным графом степени $\text{[math]}$ .

<span class="mw-page-title-main">Задача о ходе коня</span> задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу

Задача о ходе коня — задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу.

<span class="mw-page-title-main">Двудольный граф</span> граф, вершины которого образуют два множества, внутри которых нет рёбер

Двудо́льный граф или бигра́ф в теории графов — это граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет вершину из одной части с какой-то вершиной другой части, то есть не существует рёбер между вершинами одной и той же части графа.

В теории графов паросочетание, или независимое множество рёбер в графе, — это набор попарно несмежных рёбер.

Теорема Дилуорса — комбинаторное утверждение, характеризующее экстремальное свойство для частично упорядоченных множеств: конечное частично упорядоченное множество $\text{[math]}$ может быть разбито на $\text{[math]}$ попарно непересекающихся цепей, где $\text{[math]}$ — количество элементов наибольшей антицепи множества $\text{[math]}$ .

Мост — ребро в теории графов, удаление которого увеличивает число компонент связности. Такие рёбра также известны как разрезающие рёбра, разрезающие дуги или перешейки. Эквивалентное определение — ребро является мостом в том и только в том случае, если оно не содержится ни в одном цикле.

Рёберная раскраска — назначение «цветов» рёбрам графа таким образом, что никакие два смежных ребра не имеют один и тот же цвет. Рёберная раскраска — это один из видов различных типов раскраски графов. Задача рёберной раскраски задаётся вопросом, можно ли раскрасить рёбра заданного графа максимум в $\text{[math]}$ различных цветов для заданного значения $\text{[math]}$ или для минимального возможного числа цветов. Минимальное требуемое число цветов для раскраски рёбер заданного графа называется хроматическим индексом графа. Например, рёбра графа на иллюстрации можно раскрасить в три цвета, но нельзя раскрасить в два, так что граф имеет хроматический индекс 3.

В теории графов графом без треугольников называется неориентированный граф, в котором никакие три вершины не образуют треугольник из рёбер. Графы без треугольников можно определить также как графы с кликовым числом ≤ 2, графы с обхватом ≥ 4, графы без порождённых 3-циклов, или как локально независимые графы.

В теории графов ладе́йным гра́фом называется граф, представляющий все допустимые ходы ладьи на шахматной доске — каждая вершина представляет клетку на доске, а рёбра представляют возможные ходы. Ладейные графы являются крайне симметричными совершенными графами — их можно описать в терминах числа треугольников, которым принадлежит ребро и существования цикла длины 4, включающего любые две несмежные вершины.

В теории графов графом ходов короля называется граф, изображающий все возможные ходы короля на шахматной доске — каждая вершина соответствует клетке на доске, а рёбра соответствуют возможным ходам.

Замощение плитками домино области в евклидовой плоскости — мозаика из плиток домино, которые образованы объединением двух единичных квадратов, соединённых по ребру. Эквивалентно — это паросочетание в графе решётки, образованное помещением вершины в центр каждого квадрата области и соединением двух вершин, если два соответствующих квадрата смежны.

<span class="mw-page-title-main">Контурный ранг</span>

В теории графов контурный ранг неориентированного графа — это минимальное число рёбер, удаление которых разрушает все циклы графа, превращая его в дерево или лес. Контурный ранг можно понимать также как число независимых циклов в графе. В отличие от соответствующей задачи нахождения разрезающего циклы набора дуг для ориентированных графов, контурный ранг r легко вычисляется по формуле

\text{[math]}

В комбинаторике разбиений ацтекским бриллиантом порядка $\text{[math]}$ называется фигура, состоящая из клеток, наведённых плоской целочисленной решёткой, центры которых удовлетворяют неравенству $\text{[math]}$ .

<span class="mw-page-title-main">Задача «никакие три на прямой»</span>

Задача «никакие три точки не лежат на одной прямой» из комбинаторной геометрии. Её формулировка звучит следующим образом: сколько точек можно расположить на решётке $\text{[math]}$ так, чтобы никакие три точки не находились на одной прямой. Обнаружено, что их число не превосходит $\text{[math]}$ , поскольку при $\text{[math]}$ точек должна появиться строка с тремя или более точками согласно принципу Дирихле. Задачу описал Генри Эрнест Дьюдени в 1900 году. Брасс, Мозер и Пах назвали её «одним из самых старых и интенсивно изучаемых геометрических вопросов, касающихся точек решётки».

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.