Este problema no tiene solución, como ya hemos visto por aquí, y la teoría de grafos nos dice por qué. La cuestión es que este problema se puede modelizar mediante grafos. El grafo que queremos construir se denomina
(la K es en honor a Kazimierz Kuratowski), por lo que el problema ahora sería el siguiente: ¿podemos construir el grafo en un plano de forma que no haya dos aristas que se corten (en un punto que no sea un vértice)? Pues la respuesta es no, no se puede. El propio Kuratowski demostró que
no es plano (no se puede dibujar en un plano sin que haya cortes entre
aristas en puntos que no son vértices), por lo que el “problema de los
suministros” no tiene solución en un plano.
con varios cortes en puntos que no son vértices.)En la imagen siguiente podemos ver tres puntos azules cerrados, que harán el papel de “casas”, y tres puntos negros abiertos, que simbolizarán los “suministros”. Como podéis ver, al conectar casas con suministros “de la forma habitual” quedan dos conexiones sin hacer. Para hacerlas utilizamos que las líneas no están dibujadas “en uno de los dos lados de la banda” sino “en el único lado de la banda” (recordemos, tiene una sola cara). Es decir, tanto los puntos como las líneas están algo así como “incrustados” en la propia banda. Por tanto, podemos dibujar las líneas que aparecen hacia la derecha, que saldrán de manera inversa por el otro lado de la banda, consiguiendo así que no se crucen. Aquí lo vemos con la banda “desplegada”
y aquí con la banda ya “plegada”
Sencillo a la par que curioso, ¿verdad?
Más de uno estaré ahora pensando en otro grafo de Kuratowski que tampoco es plano. Sí, me refiero a
,
el grafo completo de cinco vértices. Es un grafo con cinco vértices en
el que cada uno de los vértices está conectado mediante una arista con
los otros cuatro:
con varios cortes en puntos que no son vértices.)Como hemos dicho antes, se sabe que este grafo no puede representarse en un plano sin que haya cortes entre las aristas en puntos que no sean vértices (invito a quien no lo crea a que lo intente). ¿Podrá representarse en una banda de Möbius? Pues, como antes, la respuesta vuelve a ser un rotundo sí.
Utilizando de nuevo que la banda de Möbius tiene una única cara podemos representar
en ella. Aquí la podéis ver “sin montar”:
y aquí “montada”, en la que se ve que los vértices A y C están unidos con una arista de color azul y los vértices B y D con una de color negro que no se cortan:
Y para finalizar es interesante comentar que ni mucho menos la banda de Möbius es la única superficie donde se pueden representar
y sin que haya cortes entre aristas en puntos que no sean vértices. Por ejemplo, también puede hacerse esto en un toro, y aquí tenéis cómo hacerlo con
.Fuente:
Gaussianos
