Conectando ciudades sin cortarse

Por razones que ahora no son importantes, quiero tener la posibilidad de viajar de manera directa desde Puertollano a Valdepe?as, Manzanares y Villanueva de los Infantes cuando la ocasi¨®n lo requiera. Conozco a alguien que quiere tener la misma posibilidad, pero viaja desde Ciudad Real, y ambos sabemos de otra persona que desea tener la misma opci¨®n, pero partiendo de Tomelloso. La situaci¨®n de todas estas ciudades en el mapa la pod¨¦is ver en la siguiente imagen:

Es f¨¢cil crear caminos directos entre las ciudades que queremos conectar, pero hay una condici¨®n a tener en cuenta en este caso: no nos queremos encontrar. No nos llevamos bien y no queremos que se d¨¦ el caso de que nos encontremos por la carretera en ninguno de nuestros viajes, aunque eso suponga tener que hacer m¨¢s kil¨®metros de los necesarios. Por tanto, las carreteras que deber¨ªan construirse no pueden cortarse. Suponiendo que ninguna se construye de forma elevada (vamos, que todas van por el suelo), ?c¨®mo podr¨ªamos resolver este problema?

Bien, quiz¨¢s ordenando un poco las ciudades las cosas se vean mejor. Vamos a representar cada una de ellas con un punto y cada una de las carreteras con una l¨ªnea. Dibuj¨¢ndolas todas como segmentos, la cosa quedar¨ªa as¨ª:

Como pod¨¦is ver, en esta imagen las carreteras se cortan. La idea es que no se corten, por lo que habr¨ªa que dibujar alguna de las carreteras de otra forma (curva, poligonal¡­). Os dejo que las dibuj¨¦is como quer¨¢is. Venga, papel y l¨¢piz y a dibujar un ratito antes de seguir leyendo.

Seguro que a m¨¢s de uno le suena este problema como el problema de las casas y los suministros, en el que se desea conectar tres casas con los suministros de luz, agua y gas sin que las conexiones entres casas y suministros se corten entre s¨ª. Y seguro que muchos os hab¨¦is dado cuenta de que, al representar las ciudades con puntos y las carreteras con l¨ªneas, la situaci¨®n hipot¨¦tica (o no, vete t¨² a saber¡­) que describ¨ªamos en los primeros p¨¢rrafos nos ha llevado de un problema ¡°geogr¨¢fico¡± a un problema de teor¨ªa de grafos, teor¨ªa de la cual ya hemos hablado en este blog aplicada a la ¡°adivinaci¨®n¡± de la letra del DNI y cuando estudiamos cu¨¢ndo se pod¨ªan hacer dibujos en un solo trazo.

?Ya lo hab¨¦is intentado? ?Qu¨¦ tal ha ido la cosa? Voy a intentar adivinar: no hab¨¦is conseguido lo que os ped¨ªa. Si es as¨ª, pod¨¦is estar tranquilos, ya que no se puede hacer lo que os he os requer¨ªa al principio (si pens¨¢is que lo hab¨¦is conseguido, os recomiendo que revis¨¦is vuestro dibujo, seguro que hay algo mal). Como mucho, podemos conectar dos ciudades de uno de los grupos (el rojo, por ejemplo) con las tres del otro grupo y conectar la tercera ciudad del primer grupo con dos del otro grupo, pero nos faltar¨ªa una carretera que colocar y ya no tendremos opci¨®n de evitar que corte con alguna de las ya colocadas. En la imagen ten¨¦is un ejemplo de ello:

Para explicar la imposibilidad de realizar esta construcci¨®n, vamos a meternos de lleno en teor¨ªa de grafos. El grafo que representa la situaci¨®n que plante¨¢bamos, el que aparece en la primera imagen, se conoce como K_3,3. Su definici¨®n es precisamente la que ilustra nuestro problema: dos grupos distintos de tres v¨¦rtices cada uno (sin v¨¦rtices comunes) tal que cada uno de los de un grupo est¨¢ conectado solamente con los tres del otro grupo. Es un caso particular de los grafos tipo K_m,n, que se definen de manera an¨¢loga.

Lo que asegura que nuestra construcci¨®n es imposible es que est¨¢ demostrado que este grafo no es plano (un grafo es plano cuando cualesquiera dos aristas se cortan solamente en un v¨¦rtice o no se cortan), y tambi¨¦n est¨¢ demostrado que K₅ (el grafo de cinco v¨¦rtices en el que cada v¨¦rtice est¨¢ conectado con los otros cuatro) tampoco es plano.

?A cuento de qu¨¦ introducimos ahora el grafo K₅ en el juego? Aunque parece que no tiene mucho que ver con nuestro K_3,3, en realidad est¨¢n muy relacionados. Ambos grafos son los protagonistas del conocido como teorema de Kuratowski, demostrado por el matem¨¢tico polaco Kazimierz Kuratowski en 1930. Dicho teorema dice lo siguiente:

¡°Un grafo es plano si y s¨®lo si no contiene ning¨²n subgrafo que sea una subdivisi¨®n elemental de K_3,3 o de K₅.¡±

Como no merece la pena entrar ahora en detalles en lo que respecta a eso de subdivisi¨®n elemental, vamos a dejar el teorema en que un grafo es plano si no contiene una parte que sea esencialmente igual que K_3,3 o que K₅. Es decir, este teorema nos dice, sin ninguna duda, si un grafo es plano o no lo es (es, por tanto, una caracterizaci¨®n de los grafos planos). En nuestro caso, como es el propio K_3,3, el grafo que representa las carreteras por las que queremos viajar no es un grafo plano, por lo que si queremos hacer lo que ped¨ªamos en los primeros p¨¢rrafos no tenemos otra opci¨®n que dejar al menos un punto de intersecci¨®n en el que, aunque no nos guste, corremos el peligro de encontrarnos.

Y nos da igual lo grande que sea el grafo en lo que a v¨¦rtices y aristas se refiere: si hay K_3,3 o K₅, el grafo no es plano; y si no encontramos a ninguno de ellos, entonces el grafo s¨ª es plano. Otra cosa es lo f¨¢cil o dif¨ªcil que sea encontrar alguno de estos grafos de Kuratowski (sab¨¦is ya de d¨®nde viene la K que aparece en el nombre de estos grafos, ?verdad?) dentro de un grafo muy grande y complejo, pero eso ya es otra cuesti¨®n.

En este art¨ªculo, adem¨¢s de presentaros el concepto de grafo plano y a los grafos de Kuratowski, quer¨ªa mostraros lo sencillo que es traspasar un problema real a la teor¨ªa de grafos, y lo ¨²til que es esto a la hora de estudiar dicho problema. Actualmente, la teor¨ªa de grafos es una de las teor¨ªas matem¨¢ticas con m¨¢s aplicaciones pr¨¢cticas, y una de las que m¨¢s resultados interesantes (tanto resueltos como sin resolver) posee.

Seguro que vosotros conoc¨¦is m¨¢s situaciones concretas en las que la teor¨ªa de grafos nos nos aporta soluciones. Si quer¨¦is compartir esas aplicaciones pr¨¢cticas con nosotros, los comentarios (como siempre) son vuestros.