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:
Введите два слова, показанных на изображении: *
Популярные новости
Какой материал смесителя лучше?
Какой материал смесителя лучше?
Идеальная ванная для каждого своя. Кто-то предпочитает броские цвета, а кто-то – монохромные...
Ручная рокла – преимущества, виды и особенности складской техники
Ручная рокла – преимущества, виды и особенности складской техники
Гидравлическая тележка или рокла – это конструкция, используемая для транспортировки поддонов....
Клеевые и клеепереносящие ленты
Клеевые и клеепереносящие ленты
Клейкие ленты производят на основе специальных материалов. Параметр адгезии их является важным,...
Все новости