Problema de tres servicios públicos - Three utilities problem

"Agua, gas y electricidad" vuelve a dirigir aquí. Para conocer las utilidades, consulte Utilidad pública .
El problema de las tres utilidades. ¿Se puede conectar cada casa a cada servicio público, sin que se crucen las líneas de conexión?
En un avión, se necesita un cruce

El rompecabezas matemático clásico conocido como el problema de las tres utilidades ; El problema de las tres cabañas o, a veces , el agua, el gas y la electricidad se puede expresar de la siguiente manera:

Suponga que hay tres cabañas en un avión (o esfera) y cada una debe estar conectada a las compañías de agua, gas y electricidad. Sin utilizar una tercera dimensión o enviar ninguna de las conexiones a través de otra empresa o casa de campo, ¿hay alguna manera de hacer las nueve conexiones sin que ninguna de las líneas se cruce entre sí?

El problema es un rompecabezas matemático abstracto que impone restricciones que no existirían en una situación práctica de ingeniería. Es parte del campo matemático de la teoría de grafos topológicos que estudia la incrustación de grafos en superficies . En términos más formales de la teoría de grafos , el problema pregunta si el grafo bipartito completo K 3,3 es plano . Este gráfico a menudo se denomina gráfico de utilidad en referencia al problema; también se le ha llamado gráfico de Thomsen .

Historia

Kullman (1979) ofrece una revisión de la historia del problema de las tres utilidades . Afirma que la mayoría de las referencias publicadas al problema lo caracterizan como "muy antiguo". En la primera publicación encontrada por Kullman, Henry Dudeney  ( 1917 ) lo denomina "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 ". Dudeney también publicó el mismo rompecabezas anteriormente, en The Strand Magazine en 1913.

Otra versión inicial del problema implica conectar tres casas a tres pozos. 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 modernos acertijos numéricos .

Matemáticamente, el problema se puede formular en términos de dibujos de gráficos del gráfico bipartito completa K 3,3 . Este gráfico hace una aparición temprana en Henneberg (1908) . Tiene seis vértices, divididos en dos subconjuntos de tres vértices y nueve aristas, una para cada una de las nueve formas de emparejar un vértice de un subconjunto con un vértice del otro subconjunto. El problema de las tres utilidades es la cuestión de si este gráfico es un gráfico plano .

Solución

El 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, sombreadas en amarillo, rojo y azul. Cualquiera que sea la región en la que se coloque la casa eliminada, la utilidad de color similar está fuera de la región. El teorema de la curva de Jordan establece que una línea que los conecte debe intersecar una de las líneas existentes.

Como suele presentarse (en un plano bidimensional plano), la solución al rompecabezas 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 gráfico K 3,3 no es plano. Kazimierz Kuratowski afirmó en 1930 que K 3,3 no es plano, de lo que se sigue que el problema no tiene solución. Kullman, sin embargo, afirma que "Curiosamente, Kuratowski no publicó una prueba detallada de que [ K 3,3 es] no plano".

Una prueba de la imposibilidad de encontrar una incrustación plana de K 3,3 utiliza un análisis de caso que involucra el teorema de la curva de Jordan . 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 muestra que todas son inconsistentes con una incrustación plana.

Alternativamente, es posible demostrar que cualquier grafo plano bipartito sin puentes con vértices V y aristas E tiene E ≤ 2 V - 4 combinando la fórmula de Euler V - E + F = 2 (donde F es el número de caras de una incrustación plana ) 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 alternar entre casas y servicios, por lo que cada cara tiene al menos cuatro aristas y cada arista pertenece exactamente a dos caras). En el gráfico de utilidad, E  = 9 y 2 V  - 4 = 8 , violando esta desigualdad, por lo que el gráfico de utilidad no puede ser plano.

Generalizaciones

K 3,3 dibujado con un solo cruce.
Solución al problema de las tres utilidades en un toro.

Dos caracterizaciones importantes de las gráficas planas, el teorema de Kuratowski de que las gráficas planas son exactamente las gráficas que no contienen ni K 3,3 ni la gráfica completa K 5 como subdivisión, y el teorema de Wagner de que las gráficas planas son exactamente las gráficas que no contienen ni K 3 , 3 ni K 5 como menor , hacen uso y generalizan la no planaridad de K 3,3 .

K 3,3 es un gráfico toroidal , lo que significa que se puede incrustar sin cruces en un toro . En términos del problema de las tres cabañas, esto significa que el problema se puede resolver perforando dos agujeros a través del avión (o la esfera) y conectándolos con un tubo. Esto cambia las propiedades topológicas de la superficie y el uso del tubo permite conectar las tres cabañas sin cruzar líneas. Una afirmación equivalente es que el género gráfico del gráfico de utilidad es uno y, por lo tanto, no se puede incrustar en una superficie de género menor que uno. Una superficie del género uno equivale a un toro. Se puede obtener una incrustación toroidal de K 3,3 reemplazando el cruce por un tubo, como se describió anteriormente, en el que los dos orificios donde el tubo se conecta al plano se colocan a lo largo de uno de los bordes de cruce a cada lado del cruce. Otra forma de cambiar las reglas del rompecabezas es permitir que las líneas de servicios públicos pasen por las cabañas o los servicios públicos; esta libertad adicional permite resolver el rompecabezas.

Pál Turán 's ' problema fábrica de ladrillos ' pregunta más general, para una fórmula para el número mínimo de cruces en un dibujo de la gráfica completa bipartito K un , b en términos de los números de vértices a y b en los dos lados de la bipartición . El gráfico de utilidad K 3,3 se puede dibujar con un solo cruce, pero no con cero, por lo que su número de cruce es uno.

Otras propiedades de la teoría de grafos

El gráfico de utilidad K 3,3 es un gráfico circulante . Es la jaula (3,4) , el gráfico cúbico sin triángulos más pequeño . Como todos los demás gráficos bipartitos completos , es un gráfico bien cubierto , lo que significa que cada conjunto máximo independiente tiene el mismo tamaño. En este gráfico, los únicos dos conjuntos independientes máximos son los dos lados de la bipartición y, obviamente, son iguales. K 3,3 es una de las siete gráficas bien cubiertas de 3-regulares 3-conectadas .

También es un gráfico de Laman , lo que significa que forma un sistema mínimamente rígido cuando está incrustado (con cruces) en el plano. Es el ejemplo más pequeño de un gráfico de Laman no planar, ya que el otro gráfico no planar mínimo, K 5 , no es mínimamente rígido.

Referencias

enlaces externos