Граф судоку

$4\times 4$ граф судоку

Граф судоку — это неориентированный граф, вершины которого представляют ячейки (пустой) головоломки судоку, а рёбра представляют пары ячеек, которые принадлежат той же строке, тому же столбцу или блоку головоломки. Задача головоломки судоку может быть представлена как Шаблон:Не переведено 5 на этом графе. Граф является целочисленным графом Кэли.

Базовые свойства и примеры

На поле судоку размера $n^2\times n^2$, граф судоку имеет $n^4$ вершин, каждая имеет в точности $3n^2-2n-1$ соседей. Поэтому это регулярный граф. Например, граф, представленный на рисунке с игровым полем $4\times 4$, имеет 16 вершин и является 7-регулярным. Для большинства видов судоку на игровом поле $9\times 9$ графом судоку является 20-регулярный граф с 81 вершинойШаблон:R.

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

Каждая строка, столбец или блок головоломки судоку образует клику в графе судоку, размер которой равен числу символов, используемых в головоломке. Раскраска графа судоку с помощью набора с таким числом цветов (минимальное возможное число цветов для этого графа) может интерпретироваться как решение головоломки. Обычный вид головоломки судоку, в которой некоторые ячейки заполнены символами, а остальные должны быть заполнены игроком соответствует задаче Шаблон:Не переведено 5 для этого графа Шаблон:R.

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

Для любого $n$, граф судоку поля $n^2\times n^2$ является целым графом, что означает, что спектр его матрица смежности состоит только из целых числе. Более точно, его спектр состоит из cобственных значенийШаблон:R

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

Он может быть представлен как граф Кэли абелевой группы $Z_n^4$Шаблон:R.

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

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

20-регулярный 81-вершинный граф судоку следует отличать от другого 20-регулярного графа с 81 вершинами, графа Брауэра — Хемерса, который имеет меньшие клики (размера 3) и требует меньшего числа цветов (7 вместо 9)Шаблон:R.