Граф судоку: відмінності між версіями
Створено шляхом перекладу сторінки «Граф судоку» |
(Немає відмінностей)
|
Версія за 08:35, 19 серпня 2022
Граф судоку — неорієнтований граф, вершини якого представляють комірки (порожньої) головоломки судоку, а ребра — пари комірок, які належать тому ж рядку, стовпцю або блоку головоломки. Завдання головоломки судоку можна подати як розширення попереднього розфарбування[en] на цьому графі. Граф є цілим графом Келі.
Базові властивості та приклади
На полі судоку розміру граф судоку має вершин, кожна має рівно сусідів. Тому це регулярний граф. Наприклад, граф, наведений на малюнку з ігровим полем має 16 вершин і є 7-регулярним. Для більшості видів судоку на ігровому полі графом судоку є 20-регулярний граф із 81 вершиною[1][2].
Розв'язання головоломки та розфарбування графа
Кожен рядок, стовпець або блок головоломки судоку утворює кліку в графі судоку, розмір якої дорівнює числу символів, що використовуються в головоломці. Розфарбовування графа судоку за допомогою набору з таким числом кольорів (найменша можлива кількість кольорів для цього графа) можна інтерпретувати як головоломку. Звичайний вид головоломки судоку, в якій деякі комірки заповнено символами, а інші має заповнити гравець, відповідає задачі розширення попереднього розфарбування[en] для цього графа[1][2].
Алгебричні властивості
Для будь-якого , граф судоку поля є цілим графом, що означає, що спектр його матриці суміжності складається лише з цілих чисел. Точніше, його спектр складається зі власних значень[3]
- , із кратністю ,
- , із кратністю ,
- , із кратністю ,
- , із кратністю ,
- , із кратністю ,
- , із кратністю .
Його можна подати як граф Келі абелевої групи [4].
Пов'язані графи
Граф судоку містить як підграф туровий граф, який визначається тим самим способом, але тільки на рядках і стовпцях (але не на блоках) ігрового поля судоку.
20-регулярний 81-вершинний граф судоку слід відрізняти від іншого 20-регулярного графа з 81 вершинами, графа Брауера — Хемерса, який має менші кліки (розміру 3) і вимагає меншої кількості кольорів (7 замість 9)[5].
Примітки
- ↑ а б Jesús Gago-Vargas, Maria Isabel Hartillo-Hermoso, Jorge Martín-Morales, Jose Maria Ucha-Enríquez. {{{Заголовок}}}. — Т. 4194. — DOI:
- ↑ а б Agnes M. Herzberg, M. Ram Murty. Sudoku squares and chromatic polynomials // Notices of the American Mathematical Society. — 2007. — Т. 54, вип. 6. — С. 708–717.
- ↑ Torsten Sander. Sudoku graphs are integral // Electronic Journal of Combinatorics. — 2009. — Т. 16, вип. 1. — С. Note 25, 7pp.
- ↑ Walter Klotz, Torsten Sander. Integral Cayley graphs over abelian groups // Electronic Journal of Combinatorics. — 2010. — Т. 17, вип. 1. — С. Research Paper 81, 13pp.
- ↑ Weisstein, Eric W. Brouwer–Haemers Graph(англ.) на сайті Wolfram MathWorld.