WikiDer > Судоку граф

${ displaystyle 4 times 4}$ Судоку граф

в математика судоку, то Судоку граф является неориентированный граф чья вершины представляют собой клетки (пустого) пазла судоку, и края представляют пары ячеек, принадлежащих одной строке, столбцу или блоку головоломки. Задачу решения головоломки судоку можно представить в виде расширение предварительной окраски на этом графике. Это интеграл Граф Кэли.

Основные свойства и примеры

Подсчет соседей ячейки на ${ displaystyle 9 times 9}$ Судоку граф (${ displaystyle n = 3}$)

На доске для судоку большого размера ${ Displaystyle п ^ {2} раз п ^ {2}}$, график судоку имеет ${ displaystyle n ^ {4}}$ вершины, каждый с ровно ${ displaystyle 3n ^ {2} -2n-1}$ соседи. Следовательно, это регулярный график. Общее количество ребер ${ Displaystyle п ^ {4} (3n ^ {2} -2n-1) / 2}$Например, график, показанный на рисунке выше, для ${ displaystyle 4 times 4}$ доска, имеет 16 вершин и 56 ребер и является 7-правильной. Для наиболее распространенной формы судоку на ${ displaystyle 9 times 9}$ доска, граф судоку - это 20-регулярный граф с 81 вершиной и 810 ребрами.^[1][2][3]На втором рисунке показано, как подсчитать количество соседей каждой ячейки в ${ displaystyle 9 times 9}$ доска.

Решение головоломок и раскраска графиков

Каждая строка, столбец или блок головоломки Судоку образует клика в графике судоку, размер которого равен количеству символов, используемых для решения головоломки. А раскраска графика графа судоку с использованием этого количества цветов (минимально возможное количество цветов для этого графа) можно интерпретировать как решение головоломки. Обычная форма головоломки судоку, в которой некоторые ячейки заполнены символами, а остальные должны быть заполнены лицом, решающим головоломку, соответствует расширение предварительной окраски проблема на этом графике.^[1][2][3]

Алгебраические свойства

Для любого ${ displaystyle n}$, график судоку ${ Displaystyle п ^ {2} раз п ^ {2}}$ Доска судоку - это интегральный график, что означает, что спектр своего матрица смежности состоит только из целых чисел. Точнее, его спектр состоит из собственные значения^[4]

• ${ displaystyle 3n ^ {2} -2n-1}$, с кратностью ${ displaystyle 1}$,
• ${ displaystyle 2n ^ {2} -2n-1}$, с кратностью ${ Displaystyle 2 (п-1)}$,
• ${ Displaystyle п ^ {2} -n-1}$, с кратностью ${ Displaystyle 2n (п-1)}$,
• ${ displaystyle n ^ {2} -2n-1}$, с кратностью ${ Displaystyle (п-1) ^ {2}}$,
• ${ displaystyle -1}$, с кратностью ${ Displaystyle п ^ {2} (п-1) ^ {2}}$, и
• ${ displaystyle -n-1}$, с кратностью ${ Displaystyle 2n (п-1) ^ {2}}$.

Его можно представить как Граф Кэли из абелева группа ${ Displaystyle Z_ {п} ^ {4}}$.^[5]

Связанные графики

Граф судоку содержит в качестве подграфа график ладьи, который определяется таким же образом, используя только строки и столбцы (но не блоки) доски судоку.

20-регулярный граф судоку с 81 вершиной следует отличать от другого 20-регулярного графа с 81 вершиной, т.е. График Брауэра – Хемерса, который имеет меньшие клики (размером 3) и требует меньшего количества цветов (7 вместо 9).^[6]

использованная литература