Hispanopedia Wiki
Articulo de referencia

Problema de tres servicios públicos

Diagrama del problema de las tres utilidades en un plano. Todas las líneas están conectadas, pero dos de ellas se cruzan. K_{3,3} "}},"i":0}}]}"> Dos vistas del gráfico de utili...

Hispanopedia WikiContenido en espanolLectura gratuita
Este es un buen artículo. Haz clic aquí para obtener más información.

Diagrama del problema de las tres utilidades en un plano. Todas las líneas están conectadas, pero dos de ellas se cruzan.
Dos vistas del gráfico de utilidad, también conocido como gráfico de Thomsen oK3,3{\displaystyle K_{3,3}}

El problema de las tres compañías de servicios públicos , también conocido como agua, gas y electricidad , es un rompecabezas matemático que consiste en trazar conexiones sin cruces entre tres casas y tres compañías de servicios públicos en un 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 que ninguna se cruce. Se pueden resolver versiones del problema en superficies no planas, como un toroide o una cinta de Möbius , o que permitan que las conexiones atraviesen otras casas o servicios públicos.

Este rompecabezas puede formalizarse como un problema en la teoría topológica de grafos preguntando si el grafo bipartito completoK3,3{\displaystyle K_{3,3}}, con vértices que representan las casas y los servicios públicos y aristas que representan sus conexiones, tiene una incrustación gráfica en el plano. La imposibilidad del rompecabezas corresponde al hecho de queK3,3{\displaystyle K_{3,3}}no es un grafo planar . Se conocen múltiples pruebas de esta imposibilidad, y forman parte de la demostración del teorema de Kuratowski que caracteriza a los grafos planares mediante dos subgrafos prohibidos, uno de los cuales esK3,3{\displaystyle K_{3,3}}.

La cuestión general 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 .K3,3{\displaystyle K_{3,3}}El número mínimo de cruces es uno.

K3,3{\displaystyle K_{3,3}}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 planar más pequeño .

Historia

Kullman (1979) ofrece una revisión de la historia del problema de los tres servicios públicos . Afirma que la mayoría de las referencias publicadas al problema lo caracterizan como "muy antiguo". [ 2 ] En la publicación más antigua 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 ". [ 3 ] Dudeney también publicó el mismo rompecabezas anteriormente, en The Strand Magazine en 1913. [ 4 ] Una reclamación de prioridad rival se le atribuye a Sam Loyd , quien fue citado por su hijo 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 otro rompecabezas diferente (y resoluble) 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 modernos de enlace numérico . [ 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áficoK3,3{\displaystyle K_{3,3}}aparece en publicaciones de finales del siglo XIX y principios del siglo XX, tanto en estudios iniciales de rigidez estructural [ 9 ] [ 10 ] como en la teoría de grafos químicos , donde Julius Thomsen la propuso en 1886 para la entonces incierta estructura del benceno . [ 11 ] En honor al trabajo de Thomsen,K3,3{\displaystyle K_{3,3}}A veces se le llama gráfico de Thomsen. [ 12 ]

Declaración

El problema de las tres utilidades se puede plantear de la siguiente manera:

Supongamos que tres casas necesitan conectarse a las compañías de agua, gas y electricidad, con una línea independiente desde cada casa hasta cada compañía. ¿Existe alguna manera de realizar las nueve conexiones sin que ninguna de las líneas se cruce?

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 forma parte del campo de la teoría topológica de grafos, que estudia la incrustación de grafos en superficies . Una parte importante del rompecabezas, pero que a menudo no se menciona explícitamente en su formulación informal, es que las casas, las empresas y las líneas deben estar ubicadas en una superficie bidimensional con la topología de un plano , y que las líneas no pueden atravesar otros edificios; a veces esto se refuerza 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 pregunta si el grafo bipartito completoK3,3{\displaystyle K_{3,3}}es un grafo planar . Este grafo tiene seis vértices en dos subconjuntos de tres: un vértice por cada casa y uno por cada servicio. Tiene nueve aristas, una arista por cada emparejamiento de una casa con un servicio, o más abstractamente, una arista por cada par de un vértice en un subconjunto y un vértice en el otro subconjunto. Los grafos planares son aquellos que se pueden dibujar sin cruces en el plano, y si se pudiera encontrar un dibujo de este tipo, resolvería el enigma de los tres servicios. [ 13 ] [ 14 ]

Soluciones de rompecabezas

Insolubilidad

Demostración sin palabras : Se elimina temporalmente una casa. Las líneas que conectan las casas restantes con las infraestructuras dividen el plano en tres regiones. Independientemente de la región en la que se coloque la casa eliminada, la infraestructura sombreada de forma similar queda fuera de dicha región. Según el teorema de la curva de Jordan , una línea que las conecte debe intersecar una de las líneas existentes.

Tal como se presenta habitualmente (en un plano bidimensional), la solución al rompecabezas de utilidad es "no": no hay manera de hacer las nueve conexiones sin que ninguna de las líneas se cruce con otra. En otras palabras, el gráficoK3,3{\displaystyle K_{3,3}}no es planar. Kazimierz Kuratowski afirmó en 1930 queK3,3{\displaystyle K_{3,3}}es no planar, [ 15 ] de lo cual se deduce que el problema no tiene solución. Sin embargo, Kullman (1979) afirma que "Curiosamente, Kuratowski no publicó una demostración detallada de que [K3,3{\displaystyle K_{3,3}}] no es planar". [ 2 ]

Una prueba de la imposibilidad de encontrar una incrustación planar deK3,3{\displaystyle K_{3,3}}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 grafo y se muestra que todas son inconsistentes con una incrustación planar. [ 17 ]

Alternativamente, es posible demostrar que cualquier grafo planar bipartito sin puentes conV{\displaystyle V}vértices ymi{\displaystyle E}bordes tienemi≤2V−4{\displaystyle E\leq 2V-4}combinando la fórmula de EulerV−mi+F=2{\displaystyle V-E+F=2}(dóndeF{\displaystyle F}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 alternar 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 servicios públicos,mi=9{\displaystyle E=9}y2V−4=8{\displaystyle 2V-4=8}por lo tanto en el gráfico de utilidad es falso quemi≤2V−4{\displaystyle E\leq 2V-4}. Debido a que no satisface esta desigualdad, el grafo de utilidad no puede ser planar. [ 18 ]

Cambiar las reglas

Solución en una cinta de Möbius
Solución en un toroide
Un toroide permite hasta 4 servicios públicos y 4 casas.

K3,3{\displaystyle K_{3,3}}es un grafo toroidal , lo que significa que puede incrustarse sin cruces en un toro , una superficie de género uno. [ 19 ] Estas incrustaciones resuelven versiones del rompecabezas en las que las casas y las empresas se dibujan en una taza de café u otra superficie similar en lugar de un plano. [ 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 lámina de un material transparente, puede resolverse después de retorcer y pegar la lámina para formar una cinta de Möbius . [ 22 ]

Otra forma de cambiar las reglas del rompecabezas que lo haría resoluble, sugerida por Henry Dudeney , es permitir que las líneas de servicios públicos pasen por otras casas o servicios públicos distintos de los que conectan. [ 3 ]

Propiedades del gráfico de utilidad

Más allá del enigma de la utilidad, el mismo gráficoK3,3{\displaystyle K_{3,3}}Aparece en otros contextos matemáticos, como la teoría de la rigidez , la clasificación de jaulas y grafos bien cubiertos , el estudio de los números de cruce de grafos y la teoría de los menores de grafos .

Rigidez

El gráfico de utilidadK3,3{\displaystyle K_{3,3}}es un grafo de Laman , lo que significa que para casi todas las colocaciones de sus vértices en el plano, no hay forma de mover continuamente sus vértices conservando todas las longitudes de las aristas, excepto mediante un movimiento rígido de todo el plano, y que ninguno de sus subgrafos generadores tiene la misma propiedad de rigidez . Es el ejemplo más pequeño de un grafo de Laman no planar. [ 23 ] A pesar de ser un grafo mínimamente rígido, tiene incrustaciones no rígidas con colocaciones especiales para sus vértices. [ 9 ] [ 24 ] Para incrustaciones de posición general, una ecuación polinómica que describe todas las colocaciones posibles con las mismas longitudes de arista tiene grado 16, lo que significa que en general puede haber como máximo 16 colocaciones con las mismas longitudes. Es posible encontrar sistemas de longitudes de arista para los cuales hasta ocho de las soluciones de esta ecuación describen colocaciones realizables. [ 24 ]

Otras propiedades de la teoría de grafos

K3,3{\displaystyle K_{3,3}}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 longitud cuatro. [ 25 ]

Como 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 el mismo tamaño.K3,3{\displaystyle K_{3,3}}es uno de los siete únicos grafos 3-regulares 3-conectados bien cubiertos. [ 26 ]

Generalizaciones

Dibujo deK3,3{\displaystyle K_{3,3}}con un cruce

Dos caracterizaciones importantes de los grafos planares, el teorema de Kuratowski que dice que los grafos planares son exactamente los grafos que no contienen ningunoK3,3{\displaystyle K_{3,3}}ni el gráfico completoK5{\displaystyle K_{5}}como una subdivisión, y el teorema de Wagner de que los grafos planares son exactamente los grafos que no contienen ningunoK3,3{\displaystyle K_{3,3}}niK5{\displaystyle K_{5}}como un estudiante menor , haga uso de y generalice la no planaridad deK3,3{\displaystyle K_{3,3}}. [ 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.Ka,b{\displaystyle K_{a,b}}en términos del número de vérticesa{\displaystyle a}yb{\displaystyle b}en ambos lados de la bipartición. El gráfico de utilidadK3,3{\displaystyle K_{3,3}}Puede dibujarse con un solo cruce, pero no con cero cruces, por lo que su número de cruces es uno. [ 5 ] [ 28 ]

Referencias

  1. ↑ Gries, David ; Schneider, Fred B. (1993), "Capítulo 19: Una teoría de grafos", A Logical Approach to Discrete Math , Nueva York: Springer, pp. 423–460 , doi : 10.1007/978-1-4757-3837-7 , ISBN  978-1-4419-2835-1, S2CID 206657798 Véase la página 437:K3,3{\displaystyle K_{3,3}}se conoce como el gráfico de utilidad ".
  2. 1 2 Kullman, David (1979), "El problema de las utilidades", Mathematics Magazine , 52 (5): 299– 302, doi : 10.1080/0025570X.1979.11976807 , JSTOR 2689782 
  3. 1 2 Dudeney, Henry (1917), "Problema 251 – Agua, gas y electricidad" , Amusements in mathematics , vol. 100, Thomas Nelson, pág. 73, Bibcode : 1917Natur.100..302. , doi : 10.1038/100302a0 , S2CID 10245524   La solución que se da en las páginas 200-201 consiste en trazar una línea que pase por una de las otras casas.
  4. ↑ Dudeney, Henry (1913), "Perplexidades, con algunos rompecabezas fáciles para principiantes" , The Strand Magazine , vol. 46, pág. 110  
  5. 1 2 3 Beineke, Lowell ; Wilson, Robin (2010), "La historia temprana del problema de la fábrica de ladrillos", The Mathematical Intelligencer , 32 (2): 41– 48, doi : 10.1007/s00283-009-9120-4 , MR 2657999 , S2CID 122588849  
  6. ↑ "Rompecabezas" , Agricultura Exitosa , vol. 13, pág. 50, 1914  « Un enigma sobre un pozo y una casa» , The Youth's Companion , vol. 90, n.º 2, pág. 392, 1916.   .
  7. ↑ "32. El enigma de la fuente" , El libro del mago, o El arte completo de la magia , Nueva York: Dick & Fitzgerald, 1857, pág. 276 
  8. ↑ Loyd, Sam (1959), "82: Los vecinos pendencieros" , en Gardner, Martin (ed.), Rompecabezas matemáticos de Sam Loyd , Dover Books, pág. 79, ISBN  9780486204987{{citation}}: CS1 maint: errores de ISBN ignorados ( enlace )
  9. 1 2 Dixon, AC (1899), "Sobre ciertos marcos deformables" , Messenger of Mathematics , 29 : 1–21 , JFM 30.0622.02 
  10. ↑ Henneberg, L. (1908), "Die graphische Statik der starren Körper" , Encyklopädie der Mathematischen Wissenschaften , vol. 4, págs. 345– 434  Véase en particular la página  403 .
  11. ↑ Thomsen, Julius (julio de 1886), "Die Constitution des Benzols" (PDF) , Berichte der Deutschen Chemischen Gesellschaft , 19 (2): 2944– 2950, ​​doi : 10.1002/cber.188601902285
  12. ↑ Bollobás, Béla (1998), Modern Graph Theory , Graduate Texts in Mathematics, vol. 184, Springer-Verlag, Nueva York, p. 23, doi : 10.1007/978-1-4612-0619-4 , ISBN   0-387-98488-7, MR 1633290 
  13. 1 2 Harary, Frank (1960), "Algunos aspectos históricos e intuitivos de la teoría de grafos", SIAM Review , 2 (2): 123– 131, Bibcode : 1960SIAMR...2..123H , doi : 10.1137/1002023 , MR 0111698 
  14. 1 2 Bóna, Miklós (2011), Un recorrido por la combinatoria: una introducción a la enumeración y la teoría de grafos , World Scientific, pp. 275–277 , ISBN  9789814335232Bóna introduce el rompecabezas (en forma de tres casas que deben conectarse a tres pozos) en la página  275, y escribe en la página  277 que "es equivalente al problema de dibujarK3,3{\displaystyle K_{3,3}}sobre una superficie plana sin cruces".
  15. ^ Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en topologie" (PDF) , Fundamenta Mathematicae (en francés), 15 : 271– 283, doi : 10.4064/fm-15-1-271-283
  16. ↑ Ayres, WL (1938), "Algunos aspectos elementales de la topología", The American Mathematical Monthly , 45 (2): 88– 92, doi : 10.1080/00029890.1938.11990773 , JSTOR 2304276 , MR 1524194  
  17. ↑ Trudeau, Richard J. (1993), Introducción a la teoría de grafos , Dover Books on Mathematics, Nueva York: Dover Publications, págs. 68–70 , ISBN  978-0-486-67870-2
  18. ↑ Kappraff, Jay (2001), Connections: The Geometric Bridge Between Art and Science , K & E Series on Knots and Everything, vol. 25, World Scientific, p. 128, ISBN   9789810245863
  19. ↑ Harary, F. (1964), "Resultados recientes en teoría topológica de grafos", Acta Mathematica , 15 ( 3–4 ): 405–411 , doi : 10.1007/BF01897149 , hdl : 2027.42/41775 , MR 0166775 , S2CID 123170864  ; véase la pág. 409.
  20. ↑ Parker, Matt (2015), Cosas que hacer y crear en la cuarta dimensión: El viaje de un matemático a través de los números narcisistas, los algoritmos óptimos de citas, al menos dos tipos de infinito y más , Nueva York: Farrar, Straus and Giroux, pp. 180–181 , 191–192 , ISBN  978-0-374-53563-6, MR 3753642 
  21. ↑ O'Beirne, TH (21 de diciembre de 1961), " Acertijos y paradojas navideñas, 51: Para niños, hombres y héroes" , New Scientist , vol. 12, n.º 266, págs. 751–753   
  22. ↑ Larsen, Mogens Esrom (1994), "Malinterpretar mis laberintos puede hacerme miserable", en Guy, Richard K.; Woodrow, Robert E. (eds.), Actas de la Conferencia en Memoria de Eugène Strens sobre Matemáticas Recreativas y su Historia, celebrada en la Universidad de Calgary, Calgary, Alberta, agosto de 1986 , MAA Spectrum, Washington, DC: Mathematical Association of America, pp. 289–293 , ISBN  0-88385-516-X, MR 1303141 Véase la figura 7, pág. 292 .
  23. ↑ Streinu, Ileana (2005), "Pseudotriangulaciones, rigidez y planificación de movimiento", Discrete & Computational Geometry , 34 (4): 587–635 , doi : 10.1007/s00454-005-1184-0 , MR 2173930 , S2CID 25281202  . Véase la pág. 600: "No todos los grafos genéricamente mínimamente rígidos tienen incrustaciones como pseudotriangulaciones, porque no todos son grafos planares. El ejemplo más pequeño esK3,3{\displaystyle K_{3,3}}".
  24. 1 2 Walter, D.; Husty, ML (2007), "Sobre un mecanismo de nueve barras, sus posibles configuraciones y condiciones para la movilidad paradójica" (PDF) , en Merlet, Jean-Pierre; Dahan, Marc (eds.), XII Congreso Mundial sobre Mecanismos y Ciencia de Máquinas (IFToMM 2007) , Federación Internacional para la Promoción de los Mecanismos y la Ciencia de Máquinas
  25. ↑ Tutte, WT (1947), "Una familia de grafos cúbicos", Actas de la Sociedad Filosófica de Cambridge , 43 (4): 459– 474, Bibcode : 1947PCPS...43..459T , doi : 10.1017/s0305004100023720 , MR 0021678 , S2CID 123505185  
  26. ↑ Campbell, SR; Ellingham, MN ; Royle, Gordon F. (1993), "Una caracterización de grafos cúbicos bien cubiertos", Journal of Combinatorial Mathematics and Combinatorial Computing , 13 : 193–212 , MR 1220613 
  27. ↑ Little, Charles HC (1976), "Un teorema sobre grafos planares", en Casse, Louis RA; Wallis, Walter D. (eds.), Matemáticas combinatorias IV: Actas de la Cuarta Conferencia Australiana celebrada en la Universidad de Adelaida del 27 al 29 de agosto de 1975 , Lecture Notes in Mathematics, vol. 560, Springer, pp. 136–141 , doi : 10.1007/BFb0097375 , ISBN   978-3-540-08053-4, MR 0427121 
  28. ↑ Pach, János ; Sharir, Micha (2009), "5.1 Cruces: el problema de la fábrica de ladrillos", Geometría combinatoria y sus aplicaciones algorítmicas: las conferencias de Alcalá , Mathematical Surveys and Monographs, vol. 152, American Mathematical Society , pp. 126–127  
Lecturas relacionadas
6 articulos
Rompecabezas matemáticoRompecabezas matemáticoLos acertijos matemáticos constituyen una parte integral de las matemáticas recreativas . Tienen reglas específicas, pero generalmente no implican ...Plano euclidianoPlano euclidianoEn matemáticas , un plano euclidiano es un espacio euclidiano de dimensión dos , denotado como . Es un espacio geométrico en el que se requieren do...Henry DudeneyHenry DudeneyHenry Ernest Dudeney (10 de abril de 1857 - 23 de abril de 1930) fue un autor y matemático inglés especializado en acertijos lógicos y juegos matem...Banda de MöbiusBanda de MöbiusEn matemáticas , una banda de Möbius , cinta de Möbius o bucle de Möbius [a] es una superficie que se puede formar uniendo los extremos de una tira...Teoría de grafos topológicosTeoría de grafos topológicosEn matemáticas , la teoría de grafos topológicos es una rama de la teoría de grafos . Estudia la incrustación de grafos en superficies , las incrus...Grafo bipartito completoGrafo bipartito completoEn el campo matemático de la teoría de grafos , un grafo bipartito completo o biclique es un tipo especial de grafo bipartito donde cada vértice de...