Problema de las tres utilidades

El rompecabezas matemático clásico conocido como el problema de los tres servicios públicos o, a veces , agua, gas y electricidad pide que se dibujen conexiones no cruzadas entre tres casas y tres empresas de servicios públicos en el plano . Al plantearlo a principios del siglo XX, Henry Dudeney escribió que ya era un viejo problema. Es un rompecabezas imposible : no es posible conectar las nueve líneas sin cruzarlas. Se pueden resolver versiones del problema sobre superficies no planas, como un toroide o una tira de Möbius , o que permiten que las conexiones pasen a través de otras casas o servicios públicos.

Este acertijo puede formalizarse como un problema de 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 bordes que representan sus conexiones, tiene un grafo incrustado en el plano. La imposibilidad del rompecabezas corresponde al hecho de que no es un grafo plano . Se conocen múltiples pruebas de esta imposibilidad, y forman parte de la prueba del teorema de Kuratowski que caracteriza a los grafos planos 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 $K_{3,3}$ $K_{3,3}$ $K_{3,3}$ Problema de la fábrica de ladrillos de Turán , y para el número mínimo de cruces es uno. $K_{3,3}$

$K_{3,3}$ es un gráfico con seis vértices y nueve aristas, a menudo denominado gráfico de utilidad en referencia al problema. ^[1] También se le ha llamado gráfico de Thomsen en honor al químico del siglo XIX Julius Thomsen . Es un gráfico bien cubierto , el gráfico cúbico sin triángulos más pequeño y el gráfico mínimamente rígido no plano más pequeño .

Kullman (1979) ofrece una revisión de la historia del problema de las tres utilidades . Afirma que la mayoría de las referencias publicadas sobre el problema lo caracterizan como "muy antiguo". ^[2] En la primera publicación encontrada por Kullman, Henry Dudeney ( 1917 ) lo nombra "agua, gas y electricidad". Sin embargo, Dudeney afirma que el problema es "tan antiguo como las colinas... 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] Un reclamo de prioridad en competencia es para Sam Loyd, quien fue citado por su hijo en una biografía póstuma por haber publicado el problema en 1900. ^[5]

Otra versión temprana del problema consiste en conectar tres casas a tres pozos. ^[6] Se establece 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 acertijo nuevamente implica hacer conexiones que no se crucen, pero solo entre tres pares designados de casas y pozos o fuentes, como en los acertijos de enlaces numéricos modernos . ^[7] El acertijo de Loyd "Los vecinos pendencieros" implica conectar tres casas a tres puertas por 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 dentro de él. ^[8]

Diagrama del problema de las tres utilidades que muestra líneas en un plano. ¿Se puede conectar cada casa a cada servicio público sin que se crucen las líneas de conexión?

Dos vistas del gráfico de utilidad, también conocido como gráfico de Thomsen o

K_{3,3}

Prueba sin palabras : una casa se elimina temporalmente. Las líneas que conectan las casas restantes con los servicios públicos dividen el plano en tres regiones. Cualquiera que sea la región en la que se coloque la casa eliminada, la utilidad sombreada de manera similar está fuera de la región. Por el teorema de la curva de Jordan , una línea que los conecte debe intersecar una de las líneas existentes.

Solución en un toro

Solución en una tira de Möbius

Dibujo de con un cruce

K_{3,3}