Rompecabezas y Antirompecabezas sobre una gráfica

Ponente(s): Ricardo Becerril Serrano, Enrique Casas Bautista

Una \textit{coloraci\'on propia} o \textit{buena coloraci\'on} de una gr\'afica \textit{G} es una asignaci\'on de colores a los v\'ertices de \textit{G} de manera que para cualesquiera $ u,v \in V(G) $ con $ uv \in A(G) $, el color de $ u $ es distinto al color de $ v $. Un problema fundamental dentro de la Teor\'ia de Gr\'aficas es la coloraci\'on de v\'ertices. El problema consiste en hallar el m\'inimo n\'umero de colores para dar una buena coloraci\'on a una gr\'afica. El sudoku, uno de los pasatiempos con m\'as popularidad en el mundo es un tablero de 9 x 9 que consta de 81 casillas, en algunas de las cuales se encuentra colocado un d\'igito inicial del 1 al 9, de forma que el jugador deber\'a completar el tablero, es decir, llenar las casillas que se encuentren vac\'ias con d\'igitos del 1 al 9, de manera que ning\'un d\'igito se repita en una fila, columna o regi\'on de 3 x 3.\\ Usando los conceptos de coloraci\'on de v\'ertices y buena coloraci\'on, el sudoku se puede modelar matem\'aticamente como una gr\'afica con tantos v\'ertices como casillas, de tal manera que dos v\'ertices son adyacentes si pertenecen a la misma fila o columna dentro del tablero. Si a cada d\'igito del 1 al 9 le asignamos un color diferente, un tablero de sudoku se convierte en un problema de hallar una buena coloraci\'on para los v\'ertices de la gr\'afica.\\ En esta platica, \textit{partici\'on} significa una partici\'on $ \boldsymbol{\mathcal{P}} = \lbrace \mathcal{P}_1, \mathcal{P}_2, ... \rbrace $ de $ V(G) $ de tal manera que $ \langle P_i \rangle $ es una gr\'afica conexa. Los elementos de la partic\'ion son llamados $ \textit{piezas} $.\\ Un \textit{rompecabezas} sobre una gr\'afica \textit{G} es una partici\'on de $ V(G) $ tal que hay exactamente una coloraci\'on de v\'ertices de \textit{G} con la propiedad de que las sumas sobre los colores de los v\'ertices de cada pieza de la partici\'on sean iguales. Una gr\'afica es \textbf{\textit{puzzling}} si hay un rompecabezas sobre \textit{G}.\\ El reciente estudio sobre los rompecabezas y antirompecabezas tuvo su origen cuando se formul\'o la siguiente pregunta, ?`ser\'a posible crear un tablero de sudoku en forma de rompecabezas, en el cual las sumas de los n\'umeros en cada regi\'on sean iguales y no exista ning\'un tipo de ayuda num\'erica?, en caso de que la pregunta tuviese respuesta afirmativa, ?`qu\'e se necesitar\'ia para partir el tablero de sudoku en forma de rompecabezas?, ?`qu\'e formas tendr\'an las regiones?.\\ Despu\'es de varios intentos, se logr\'o descubrir un tablero, el cual se puede partir a manera de rompecabezas, dicho tablero era de dimensi\'on 6x6.\\ Una variante a este problema es considerar una gr\'afica coloreada sobre los v\'ertices en lugar de considerar un tablero de sudoku y preguntarnos si es posible partirla en forma de rompecabezas, de tal manera que las sumas correspondientes a los v\'ertices en cada pieza sean iguales, de esta manera es como se origina el estudio de los rompecabezas. \\ Otra variante de este problema es considerar que las sumas de los n\'umeros correspondientes a los v\'ertices en cada pieza sean distintas, esto dio origen al estudio de los antirompecabezas.\\ Un \textit{antirompecabezas} sobre una gr\'afica \textit{G} es una partici\'on de $ V(G) $ tal que hay exactamente una coloraci\'on de v\'ertices de \textit{G} con la propiedad de que las sumas sobre los colores de los v\'ertices de cada pieza de la partici\'on sean diferentes. Una gr\'afica es \textbf{\textit{apuzzling}} si hay un antirompecabezas sobre \textit{G}.\\ En esta platica mostraremos algunas familias de gr\'aficas que son \textit{puzzling}, \textit{apuzzling} o ninguna de las anteriores, as\'i como tambi\'en mostraremos la existencia de gráficas infinitas que son \textit{puzzling} y \textit{apuzzling}. Por otro lado se pretende mostrar los resultados obtenidos en relaci\'on a los abanicos $F_{(1,n)}$ y las ruedas $W_n$.