09.02.2022

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


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

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

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


Похожие новости:

Матрица смежности

Матрица смежности
Матрица смежности — один из способов представления графа в виде матрицы. Определение Матрица смежности графа G {displaystyle G} с конечным числом вершин

Теорема Безу

Теорема Безу
Теорема Безу утверждает, что остаток от деления многочлена P ( x ) {displaystyle P(x)} на двучлен (

Независимое множество

Независимое множество
Независимое множество в теории графов может быть как независимым множеством вершин, так и независимым множеством ребер. Независимые множества рассматриваются в задачах покрытия графов.

Матрица Кирхгофа

Матрица Кирхгофа
Матрица Кирхгофа — одно из представлений конечного графа с помощью матрицы. Матрица Кирхгофа представляет дискретный оператор Лапласа для графа. Она используется для подсчета остовных деревьев
Комментариев пока еще нет. Вы можете стать первым!

Добавить комментарий!

Ваше Имя:
Ваш E-Mail:
Введите два слова, показанных на изображении: *
Популярные новости
Электрическая самоходная тележка – чем лучше гидравлики
Электрическая самоходная тележка – чем лучше гидравлики
Гидравлический механизм считается один из самых надежных, эффективных и доступных....
Защита водопровода от промерзания
Защита водопровода от промерзания
Как известно, в нашей стране зимы бывают очень долгими и холодными, поэтому для нас всегда...
Критерии выбора манжеты шевронной
Критерии выбора манжеты шевронной
Манжета шевронная ГОСТ 22704-77, купить которую можно у производителя, широко востребована для...
Все новости