En las matemáticas del Sudoku , el gráfico de Sudoku es un gráfico no dirigido cuyos vértices representan las celdas de un Sudoku (en blanco) y cuyos bordes representan pares de celdas que pertenecen a la misma fila, columna o bloque del rompecabezas. El problema de resolver un Sudoku se puede representar como una extensión de precoloración en este gráfico. Es un gráfico de Cayley integral .
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/5/5c/4x4_Sudoku_graph.svg/220px-4x4_Sudoku_graph.svg.png)
Propiedades básicas y ejemplos
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/3/38/9x9_Sudoku_graph_neighbors_%28really_fixed%29.svg/300px-9x9_Sudoku_graph_neighbors_%28really_fixed%29.svg.png)
En un tablero de Sudoku de tamaño , el gráfico de Sudoku tiene vértices , cada uno con exactamentevecinos. Por tanto, es un gráfico regular . El número total de aristas es. Por ejemplo, el gráfico que se muestra en la figura anterior, para untablero, tiene 16 vértices y 56 aristas, y es 7 regular. Para la forma más común de Sudoku, en untablero, el gráfico de Sudoku es un gráfico regular de 20 con 81 vértices y 810 aristas. [1] [2] [3] La segunda figura muestra cómo contar los vecinos de cada celda en un Junta.
Soluciones de rompecabezas y coloración de gráficos
Cada fila, columna o bloque del Sudoku forma una pandilla en el gráfico de Sudoku, cuyo tamaño es igual al número de símbolos utilizados para resolver el rompecabezas. Una coloración del gráfico del Sudoku utilizando este número de colores (el número mínimo posible de colores para este gráfico) se puede interpretar como una solución al rompecabezas. La forma habitual de un Sudoku, en la que algunas celdas se rellenan con símbolos y el resto debe ser rellenado por la persona que resuelve el puzzle, corresponde al problema de extensión de precoloración de este gráfico. [1] [2] [3]
Propiedades algebraicas
Para cualquier , el gráfico Sudoku de un El tablero de sudoku es un gráfico integral , lo que significa que el espectro de su matriz de adyacencia consta solo de números enteros. Más precisamente, su espectro consiste en los valores propios [4]
- , con multiplicidad ,
- , con multiplicidad ,
- , con multiplicidad ,
- , con multiplicidad ,
- , con multiplicidad , y
- , con multiplicidad .
Se puede representar como un gráfico de Cayley del grupo abeliano. . [5]
Gráficos relacionados
El gráfico de Sudoku contiene como subgrafo el gráfico de la torre , que se define de la misma manera utilizando solo las filas y columnas (pero no los bloques) del tablero de Sudoku.
El gráfico Sudoku de 81 vértices y 20 regulares debe distinguirse de un gráfico diferente de 20 regulares sobre 81 vértices, el gráfico de Brouwer-Haemers , que tiene grupos más pequeños (de tamaño 3) y requiere menos colores (7 en lugar de 9). [6]
Referencias
- ^ a b Gago-Vargas, Jesús; Hartillo-Hermoso, María Isabel; Martín-Morales, Jorge; Ucha-Enríquez, Jose Maria (2006), "Bases Sudokus y Gröbner: No solo un divertimento ", en Ganzha, Victor G .; Mayr, Ernst W .; Vorozhtsov, Evgenii V. (eds.), Computer Algebra in Scientific Computing, 9th International Workshop, CASC 2006, Chisinau, Moldova, 11-15 de septiembre de 2006, Proceedings , Lecture Notes in Computer Science, 4194 , Springer, págs. 155– 165, doi : 10.1007 / 11870814_13
- ^ a b Herzberg, Agnes M .; Murty, M. Ram (2007), "Cuadrados de Sudoku y polinomios cromáticos" (PDF) , Notices of the American Mathematical Society , 54 (6): 708–717, MR 2327972
- ^ a b Rosenhouse, Jason ; Taalman, Laura (2011), Tomando el Sudoku en serio: Las matemáticas detrás del rompecabezas de lápiz más popular del mundo , Oxford University Press, págs. 128–130
- ^ Sander, Torsten (2009), "Los gráficos de Sudoku son integrales" , Electronic Journal of Combinatorics , 16 (1): Nota 25, 7pp, doi : 10.37236 / 263 , MR 2529816
- ^ Klotz, Walter; Sander, Torsten (2010), "Gráficos de Cayley integral sobre grupos abelianos" , Electronic Journal of Combinatorics , 17 (1): Documento de investigación 81, 13pp, doi : 10.37236 / 353 , MR 2651734
- ^ Weisstein, Eric W. "Gráfico de Brouwer-Haemers" . MathWorld .