Граф судоку

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

$4\times <!--\; \times \; -->4$$4\times 4$ граф судоку

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

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

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

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

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

Для любого $n$$n$ , граф судоку поля $n^2\times <!--\; \times \; -->n^2$$n^{2}\times n^{2}$  является целым графом, что означает, что спектр его матрица смежности состоит только из целых числе. Более точно, его спектр состоит из cобственных значений

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

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

Связанные графыПравить

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

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