Граф судоку

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

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

Базові властивості та приклади

На полі судоку розміру ${\displaystyle n^{2}\times n^{2}}$ граф судоку має ${\displaystyle n^{4}}$ вершин, кожна має рівно ${\displaystyle 3n^{2}-2n-1}$ сусідів. Тому це регулярний граф. Наприклад, граф, наведений на малюнку з ігровим полем ${\displaystyle 4\times 4}$ має 16 вершин і є 7-регулярним. Для більшості видів судоку на ігровому полі ${\displaystyle 9\times 9}$ графом судоку є 20-регулярний граф із 81 вершиною.

Розв'язання головоломки та розфарбування графа

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

Алгебричні властивості

Для будь-якого ${\displaystyle n}$, граф судоку поля ${\displaystyle n^{2}\times n^{2}}$ є цілим графом, що означає, що спектр його матриці суміжності складається лише з цілих чисел. Точніше, його спектр складається зі власних значень

• ${\displaystyle 3n^{2}-2n-1}$, із кратністю ${\displaystyle 1}$,
• ${\displaystyle 2n^{2}-2n-1}$, із кратністю ${\displaystyle 2(n-1)}$,
• ${\displaystyle n^{2}-n-1}$, із кратністю ${\displaystyle 2n(n-1)}$,
• ${\displaystyle n^{2}-2n-1}$, із кратністю ${\displaystyle (n-1)^{2}}$,
• ${\displaystyle -1}$, із кратністю ${\displaystyle n^{2}(n-1)^{2}}$,
• ${\displaystyle -n-1}$, із кратністю ${\displaystyle 2n(n-1)^{2}}$.

Його можна подати як граф Келі абелевої групи ${\displaystyle Z_{n}^{4}}$.

Пов'язані графи

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

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

Примітки

1. Jesús Gago-Vargas, Maria Isabel Hartillo-Hermoso, Jorge Martín-Morales, Jose Maria Ucha-Enríquez. Sudokus and Gröbner bases: Not only a divertimento // Computer Algebra in Scientific Computing, 9th International Workshop, CASC 2006, Chisinau, Moldova, September 11–15, 2006, Proceedings / Victor G. Ganzha, Ernst W. Mayr, Evgenii V. Vorozhtsov. — Springer, 2006. — Т. 4194. — С. 155–165. — (Lecture Notes in Computer Science). — DOI:10.1007/11870814_13.
2. Agnes M. Herzberg, M. Ram Murty. Sudoku squares and chromatic polynomials // Notices of the American Mathematical Society. — 2007. — Т. 54, вип. 6. — С. 708–717.
3. Torsten Sander. Sudoku graphs are integral // Electronic Journal of Combinatorics. — 2009. — Т. 16, вип. 1. — С. Note 25, 7pp.
4. Walter Klotz, Torsten Sander. Integral Cayley graphs over abelian groups // Electronic Journal of Combinatorics. — 2010. — Т. 17, вип. 1. — С. Research Paper 81, 13pp.
5. Weisstein, Eric W. Brouwer–Haemers Graph(англ.) на сайті Wolfram MathWorld.