El clásico problema matemático conocido como el problema de los tres servicios o, a veces, el problema del agua, el gas y la electricidad, pide que se dibujen conexiones que no se crucen entre tres casas y tres compañías de servicios públicos en el plano . Al plantearlo a principios del siglo XX, Henry Dudeney escribió que ya era un problema antiguo. Es un rompecabezas imposible : no es posible conectar las nueve líneas sin cruzarse. Se pueden resolver versiones del problema en superficies no planas como un toro o una banda de Möbius , o que permitan que las conexiones pasen a través de otras casas o servicios públicos.
Este rompecabezas se puede formalizar como un problema en la teoría de grafos topológicos preguntando si el grafo bipartito completo , con vértices que representan las casas y los servicios públicos y aristas que representan sus conexiones, tiene un grafo incrustado en el plano. La imposibilidad del rompecabezas corresponde al hecho de que no es un grafo planar . Se conocen múltiples pruebas de esta imposibilidad, y forman parte de la prueba del teorema de Kuratowski que caracteriza a los grafos planares por dos subgrafos prohibidos, uno de los cuales es . La cuestión de minimizar el número de cruces en dibujos de grafos bipartitos completos se conoce como el problema de la fábrica de ladrillos de Turán , y para el número mínimo de cruces es uno.
es un grafo con seis vértices y nueve aristas, a menudo denominado grafo de utilidad en referencia al problema. [1] También se le ha llamado grafo de Thomsen en honor al químico del siglo XIX Julius Thomsen . Es un grafo bien cubierto , el grafo cúbico sin triángulos más pequeño y el grafo mínimamente rígido no plano más pequeño .
Kullman (1979) hace un repaso de la historia del problema de los tres servicios públicos. Afirma que la mayoría de las referencias publicadas sobre el problema lo caracterizan como "muy antiguo". [2] En la publicación más antigua encontrada por Kullman, Henry Dudeney (1917) lo llama "agua, gas y electricidad". Sin embargo, Dudeney afirma que el problema es "tan antiguo como las montañas... mucho más antiguo que la iluminación eléctrica , o incluso el gas ". [3] Dudeney también publicó el mismo rompecabezas anteriormente, en The Strand Magazine en 1913. [4] Una reivindicación de prioridad que compite con Sam Loyd , a quien su hijo citó en una biografía póstuma como el autor del problema en 1900. [5]
Otra versión temprana del problema implica conectar tres casas a tres pozos. [6] Se plantea de manera similar a un rompecabezas diferente (y solucionable) que también involucra tres casas y tres fuentes, con las tres fuentes y una casa tocando una pared rectangular; el rompecabezas nuevamente implica hacer conexiones que no se cruzan, pero solo entre tres pares designados de casas y pozos o fuentes, como en los rompecabezas de enlace numérico modernos . [7] El rompecabezas de Loyd "Los vecinos pendencieros" implica de manera similar conectar tres casas a tres puertas mediante tres caminos que no se cruzan (en lugar de nueve como en el problema de los servicios públicos); una casa y las tres puertas están en la pared de un patio rectangular, que contiene las otras dos casas en su interior. [8]
Además del problema de las tres utilidades, el gráfico aparece en publicaciones de finales del siglo XIX y principios del XX, tanto en los primeros estudios sobre rigidez estructural [9] [10] como en la teoría de grafos químicos , donde Julius Thomsen lo propuso en 1886 para la entonces incierta estructura del benceno . [11] En honor al trabajo de Thomsen, a veces se le llama gráfico de Thomsen. [12]
El problema de las tres utilidades puede enunciarse de la siguiente manera:
Supongamos que es necesario conectar tres casas a las compañías de agua, gas y electricidad, con una línea independiente de cada casa a cada compañía. ¿Hay alguna manera de realizar las nueve conexiones sin que ninguna de las líneas se cruce con otra?
El problema es un rompecabezas matemático abstracto que impone restricciones que no existirían en una situación práctica de ingeniería. Su formalización matemática es parte del campo de la teoría de grafos topológicos que estudia la incrustación de grafos en superficies . Una parte importante del rompecabezas, pero que a menudo no se enuncia explícitamente en las formulaciones informales del rompecabezas, es que las casas, las empresas y las líneas deben colocarse en una superficie bidimensional con la topología de un plano , y que las líneas no pueden pasar por otros edificios; a veces esto se hace cumplir mostrando un dibujo de las casas y las empresas, y pidiendo que las conexiones se dibujen como líneas en el mismo dibujo. [13] [14]
En términos más formales de teoría de grafos , el problema plantea la pregunta de si el grafo bipartito completo es un grafo plano . Este grafo tiene seis vértices en dos subconjuntos de tres: un vértice para cada casa y uno para cada servicio. Tiene nueve aristas, una arista para cada uno de los emparejamientos de una casa con un servicio, o de manera más abstracta una arista para cada par de un vértice en un subconjunto y un vértice en el otro subconjunto. Los grafos planos son los grafos que se pueden dibujar sin cruces en el plano, y si se pudiera encontrar un dibujo así, resolvería el problema de los tres servicios. [13] [14]
Tal como se presenta habitualmente (en un plano bidimensional), la solución al problema de la utilidad es "no": no hay forma de hacer las nueve conexiones sin que ninguna de las líneas se cruce entre sí. En otras palabras, el grafo no es plano. Kazimierz Kuratowski afirmó en 1930 que es no plano, [15] de lo que se deduce que el problema no tiene solución. Kullman (1979), sin embargo, afirma que "Curiosamente, Kuratowski no publicó una prueba detallada de que [ ] no es plano". [2]
Una prueba de la imposibilidad de encontrar una incrustación planar de utiliza un análisis de caso que involucra el teorema de la curva de Jordan . [16] En esta solución, se examinan diferentes posibilidades para las ubicaciones de los vértices con respecto a los 4 ciclos del gráfico y se demuestra que todas son inconsistentes con una incrustación planar. [17]
Alternativamente, es posible demostrar que cualquier grafo bipartito planar sin puente con vértices y aristas tiene combinando la fórmula de Euler (donde es el número de caras de una incrustación planar) con la observación de que el número de caras es como máximo la mitad del número de aristas (los vértices alrededor de cada cara deben alternarse entre casas y servicios públicos, por lo que cada cara tiene al menos cuatro aristas, y cada arista pertenece exactamente a dos caras). En el grafo de utilidades, y por lo tanto en el grafo de utilidades, no es cierto que . Debido a que no satisface esta desigualdad, el grafo de utilidades no puede ser planar. [18]
es un grafo toroidal , lo que significa que puede ser incrustado sin cruces en un toro , una superficie de género uno. [19] Estas incrustaciones resuelven versiones del rompecabezas en las que las casas y empresas se dibujan en una taza de café u otra superficie similar en lugar de una superficie plana. [20] Incluso hay suficiente libertad adicional en el toro para resolver una versión del rompecabezas con cuatro casas y cuatro servicios públicos. [21] [5] De manera similar, si el rompecabezas de los tres servicios públicos se presenta en una hoja de un material transparente, puede resolverse después de torcer y pegar la hoja para formar una banda de Möbius . [22]
Otra forma de cambiar las reglas del rompecabezas que lo haría solucionable, sugerida por Henry Dudeney , es permitir que las líneas de servicios públicos pasen a través de otras casas o servicios públicos distintos de los que conectan. [3]
Más allá del rompecabezas de la utilidad, el mismo gráfico aparece en varios otros contextos matemáticos, incluida la teoría de la rigidez , la clasificación de jaulas y gráficos bien cubiertos , el estudio de números que cruzan gráficos y la teoría de los menores de gráficos .
El grafo de utilidad es un grafo de Laman , lo que significa que para casi todas las ubicaciones de sus vértices en el plano, no hay forma de mover continuamente sus vértices mientras se preservan todas las longitudes de los bordes, excepto mediante un movimiento rígido de todo el plano, y que ninguno de sus subgrafos de expansión tiene la misma propiedad de rigidez . Es el ejemplo más pequeño de un grafo de Laman no plano. [23] A pesar de ser un grafo mínimamente rígido, tiene incrustaciones no rígidas con ubicaciones especiales para sus vértices. [9] [24] Para incrustaciones de posición general, una ecuación polinómica que describe todas las ubicaciones posibles con las mismas longitudes de borde tiene grado 16, lo que significa que, en general, puede haber como máximo 16 ubicaciones con las mismas longitudes. Es posible encontrar sistemas de longitudes de borde para los que hasta ocho de las soluciones de esta ecuación describen ubicaciones realizables. [24]
es un grafo sin triángulos , en el que cada vértice tiene exactamente tres vecinos (un grafo cúbico ). Entre todos estos grafos, es el más pequeño. Por lo tanto, es la jaula (3,4) , el grafo más pequeño que tiene tres vecinos por vértice y en el que el ciclo más corto tiene una longitud de cuatro. [25]
Al igual que todos los demás grafos bipartitos completos , es un grafo bien cubierto , lo que significa que cada conjunto independiente máximo tiene el mismo tamaño. En este grafo, los únicos dos conjuntos independientes máximos son los dos lados de la bipartición y tienen tamaños iguales. es uno de los únicos siete grafos bien cubiertos 3-regulares 3-conectados . [26]
Dos caracterizaciones importantes de los grafos planares, el teorema de Kuratowski , que sostiene que los grafos planares son exactamente los grafos que no contienen ni el grafo completo como subdivisión, y el teorema de Wagner , que sostiene que los grafos planares son exactamente los grafos que no contienen ni como subdivisión menor , hacen uso de y generalizan la no planaridad de . [27]
El " problema de la fábrica de ladrillos " de Pál Turán plantea de forma más general una fórmula para el número mínimo de cruces en un dibujo del grafo bipartito completo en términos de los números de vértices y en los dos lados de la bipartición. El grafo de utilidad puede dibujarse con un solo cruce, pero no con cruces por cero, por lo que su número de cruces es uno. [5] [28]
