Hrabě Sudoku

Sudoku graf je neorientovaný graf , jehož vrcholy představují buňky (prázdného) sudoku a jehož okraje představují dvojice buněk, které patří do stejného řádku, sloupce nebo bloku puzzle. Problém sudoku lze znázornit jako rozšíření předbarvení na tomto grafu. Graf je celočíselný graf Cayley .

Základní vlastnosti a příklady

Na poli sudoku o velikosti má graf sudoku vrcholy, z nichž každý má přesně své sousedy. Jedná se tedy o běžný graf . Například graf zobrazený na obrázku s hracím polem má 16 vrcholů a je 7 pravidelný. Pro většinu typů sudoku na hřišti je graf Sudoku 20-běžný graf s 81 vrcholy [1] [2] . $n^{2}\times n^{2}$ ${\displaystyle n^{4))$ $3n^{2}-2n-1$ $4\times 4$ $9\times 9$

Řešení hádanky a vybarvení grafu

Každý řádek, sloupec nebo blok sudoku tvoří kliku v grafu sudoku, jejíž velikost se rovná počtu symbolů použitých v hádance. Vybarvení grafu sudoku pomocí sady s tímto počtem barev (minimální možný počet barev pro tento graf) lze interpretovat jako řešení hádanky. Obvyklá podoba sudoku, ve které jsou některé buňky vyplněny symboly a zbytek musí vyplnit hráč, odpovídá problému předbarvování rozšíření pro tento graf [1] [2] .

Algebraické vlastnosti

Pro všechny je graf Sudoku pole celočíselný , což znamená, že spektrum jeho matice sousedství se skládá pouze z celých čísel. Přesněji řečeno, jeho spektrum se skládá z vlastních čísel [3] $n$ $n^{2}\times n^{2}$

$3n^{2}-2n-1$ , s mnohonásobností , $jeden$
$2n^{2}-2n-1$ , s mnohonásobností , $2(n-1)$
$n^{2}-n-1$ , s mnohonásobností , $2n(n-1)$
$n^{2}-2n-1$ , s mnohonásobností , ${\displaystyle (n-1)^{2))$
$-jeden$ , s mnohonásobností , ${\displaystyle n^{2}(n-1)^{2))$
$-n-1$ , s multiplicitou . ${\displaystyle 2n(n-1)^{2))$

Může být reprezentován jako Cayleyův graf abelovské grupy [4] . ${\displaystyle Z_{n}^{4))$

Související grafy

Sudoku graf obsahuje jako podgraf věžový graf , který je definován stejným způsobem, ale pouze na řádcích a sloupcích (nikoli však na blocích) hracího pole Sudoku.

20-běžný 81-vertexový graf Sudoku by měl být odlišen od jiného 20-běžného 81-vertexového grafu, Brouwer-Hemersova grafu , který má menší kliky (velikost 3) a vyžaduje méně barev (7 místo 9) [5] .

Poznámky

↑ 1 2 Jesús Gago-Vargas, Maria Isabel Hartillo-Hermoso, Jorge Martín-Morales, José Maria Ucha-Enríquez. Základy sudokusu a Gröbnera: Nejen divertimento // Počítačová algebra ve vědeckém počítání, 9. mezinárodní workshop, CASC 2006, Kišiněv, Moldavsko, 11.–15. září 2006, sborník příspěvků / Victor G. Ganzha, Ernst W. Mayr, Evgenii V. Vorozhtsov. - Springer, 2006. - T. 4194. - S. 155-165. — (Poznámky z informatiky). - doi : 10.1007/11870814_13 .
↑ 1 2 Agnes M. Herzberg, M. Ram Murty. Sudoku čtverce a chromatické polynomy // Notices of the American Mathematical Society . - 2007. - T. 54 , č. 6 . — S. 708–717 .
↑ Torsten Sander. Grafy sudoku jsou integrální // Electronic Journal of Combinatorics. - 2009. - T. 16 , no. 1 . — C. Poznámka 25, 7pp .
↑ Walter Klotz, Torsten Sander. Integrální Cayleyho grafy nad abelovskými skupinami // Electronic Journal of Combinatorics. - 2010. - T. 17 , no. 1 . — C. Research Paper 81, 13pp .
↑ Weisstein, Eric W. Brouwer–Haemers Graph na webu Wolfram MathWorld .