Acertijo matemático. Problema de los suministros


Es muy conocido el siguiente acertijo del que voy a hablar en esta entrada, conocido como problema de los suministros:

Dado el siguiente diagrama:

Acertijo

Acertijo

Hay que intentar unir los tres puntos de arriba con los tres de abajo mediante lineas (rectas o curvas) de manera que cada vector de arriba esté conectado con todos los de abajo y viceversa, y de manera que las lineas no se corten. Es decir, hay que hacer la siguiente imagen:

¿Puedes?

¿Puedes?

Pero de manera que las lineas no se corten entre si. Inténtalo, y luego sigue leyendo para saber la solución.

Y hablé en un post anterior sobre grafos, y puesto que este acertijo no podría entrar mejor en la definición de grafo, usaremos esa teoría para tratar el problema.

En este caso tenemos un grafo con una sola componente conexa, y lo que queremos saber es si el grafo es plano. Un grafo es plano cuando se puede dibujar de manera que sus aristas no se corten entre si, que es justo lo que queremos hacer. Por ejemplo, los siguientes grafos son planos, puesto que se pueden dibujar sin que se corten sus aristas:

Grafos planos

Grafos planos

Fíjate en que en el último grafo hay dos aristas que se cortan en el medio, sin embargo este grafo sigue siendo plano porque si una de las aristas la hacemos pasar por fuera, entonces ya no se cortan:

grafo3b

De modo que un grafo es plano no cuando sus aristas no se cortan, sino cuando es posible dibujarlo sin que se corten.

Para resolver esto primero hemos de pasar por un paso intermedio: Este paso intermedio consiste en encontrar una fórmula que es común para todos los grafos planos, y luego veremos si nuestro grafo la cumple. Esa fórmula es conocida como fórmula de Euler para poliedros (o para grafos planos, puesto que un grafo plano puede verse como la proyección de las caras de un tipo de poliedros), y es la siguiente:

V-E+R=2

V es el número de vértices, E es el número de aristas, y R es el número de regiones que separan las aristas. Esa fórmula debe cumplirse para cualquier grafo plano.

La manera más sencilla de demostrar que esa fórmula es cierta es mediante el principio de inducción sobre las tres variables. Este principio se basa en lo siguiente: supongamos que tenemos una propiedad sobre los números naturales: \mathbb{N}=\lbrace 1,2,3,4,... \rbrace , es decir, que dado un número, la propiedad sea cierta o falsa para ese número, si podemos demostrar los siguientes dos puntos, entonces la propiedad se cumple para TODOS los números naturales:

  1. La propiedad se cumple para el número 1
  2. Si la propiedad se cumple para el número k, entonces se cumple para k+1

Es evidente: Si la propiedad se cumple para el número 1, entonces por el segundo punto se cumple para el número 2, y como se cumple para el número dos, de nuevo por el segundo punto se cumple para el 3, y así podemos seguir subiendo hasta cualquier número, de manera que se cumple para todos los números.

Pues bien, para demostrar la fórmula de Euler eso será lo que haremos, ahora no tenemos números, y hacer equivaler un grafo con números puede no ser del todo trivial, pero lo pasaremos un poco por alto. Demostraremos que la propiedad se cumple para el grafo más simple: 1 vértice. Es evidente: ya que en ese caso tenemos 1 vértice, 0 aristas, y 1 región que es la que ocupa todo el espacio, de manera que V-E+R=1-0+1=2: se cumple. Ahora hay que demostrar el punto 2, es decir, si tenemos un grafo para el que se cumple la fórmula $latex V-E+R=2$ y le añadimos bien un vértice, o bien una arista, sigue cumpliéndose:

Si le añadimos 1 vértice, para que siga siendo conexo debemos conectarlo al grafo mediante una nueva arista, así que añadimos en total 1 vértice y una arista, pero ninguna región, de manera que V'-E'+R=V+1-(E+1)+R=V-E+R+1-1=V-E+R=2

Si en cambio le queremos añadir una arista entre dos vértices ya existentes, podemos separar dos casos

  1. Caso 1: entre los dos vértices no hay ningún ciclo. En este caso no hay ningún ciclo, sin embargo debe haber un camino que una ambos vértices porque el grafo es conexo. Eso significa que al unirlos directamente creamos un ciclo que pasa por ambos vértices, y por lo tanto estamos separando una región interna al ciclo de una externa. En este caso añadimos una arista, no añadimos ningún vértice puesto que los dos vértices que unimos ya existían, y como hemos separado una región en dos, hemos añadido una región: V-E'+R'=V-(E+1)+R+1=V-E+R=2, se cumple. Este primer caso se puede observar en la siguiente imagen

    No existe ningún ciclo que pase por los dos vértices superiores, al crearlo añadimos una arista y conseguimos una región más

    No existe ningún ciclo que pase por los dos vértices superiores, al crearlo añadimos una arista y conseguimos una región más

  2. El segundo caso es que ya haya un ciclo entre ambos vértices. En este caso ocurre en realidad lo mismo, al hacer pasar la arista entre dos vértices de manera que no corte a ninguna otra arista estaremos creando un nuevo ciclo y separando una región en dos, de manera que ocurre lo mismo, como podemos observar aquí
En este caso ya existía un  ciclo y había una región "interna" definida. Al añadir la arista la partimos por la mitad, consiguiendo una arista más

En este caso ya existía un ciclo y había una región “interna” definida. Al añadir la arista la partimos por la mitad, consiguiendo una arista más

Ya hemos demostrado que añadiendo vértices o aristas de manera que el grafo siga siendo plano, entonces si la fórmula se cumplía debe seguir cumpliéndose. Como se cumple también para el grafo formado por un sólo vértice, y podemos formar cualquier otro grafo plano a partir de este, entonces esa fórmula debe cumplirse para todos los grafos planos, concluimos entonces que:

Si un grafo es plano, entonces cumple la fórmula de Euler: V-E+R=2.

Ahora veamos, ¿cumple nuestro primer grafo la fórmula de Euler? Nuestro grafo del acertijo tiene 6 vértices, y si queremos que cada uno de los tres vértices de arriba estén conectado con los tres de abajo, entonces debe tener 9 aristas, eso significa que:

6-9+R=2

R=2+9-6=5

Es decir, si nuestro grafo es plano, debe tener 5 regiones al dibujarlo sin que se corten sus aristas.

Vamos a intentar calcular el mayor número posible de regiones que puede tener nuestro grafo: observemos el grafo de nuevo:

grafo2

Hay que fijarse en que si queremos formar un ciclo entre dos vértices, el menor número de aristas que debemos recorrer es 4: si empezamos arriba, un vértice de arriba está conectado con los tres de abajo, de modo que primero hemos de bajar, porque no queda otra, luego hemos de subir, pero a un vértice distinto, y volvemos a estar arriba, como los vértices de arriba no están conectados entre si, no podemos ir a nuestro vértice inicial, hay que bajar de nuevo a otro distinto, y ahora si tenemos la seguridad de que el vértice de abajo está conectado con el de arriba de modo que podemos terminar el ciclo: en conclusión, los ciclos tiene como poco 4 aristas. Un ejemplo de un ciclo se ve aquí:

Ejemplo de ciclo mínimo en el grafo: tiene 4 aristas

Ejemplo de ciclo mínimo en el grafo: tiene 4 aristas

Ahora bien, como queremos calcular el mayor número posible de regiones, y lo cuantos más pequeños sean los ciclos más regiones tendremos, supongamos que todos los ciclos son del menor número de aristas: 4. En este caso, como cada arista está en contacto con 2 regiones, y cada ciclo determina dos regiones (interior y exterior), el mayor número posible de regiones es:

\frac{9\; aristas*2}{4\; aristas/region}=4.5 regiones

El número máximo posible de regiones que ese grafo puede tener es 4.5, sin embargo para que fuese plano tendría que tener 5, que es mayor que 4.5, y por lo tanto el grafo no puede ser plano.

Esto demuestra que ese acertijo es imposible de resolver, no se puede dibujar ese grafo de manera que sus aristas no se corten.

¿Imposible del todo? Analicemos un poco lo anterior. Esa demostración que hemos hecho se basa en la fórmula de Euler: V-E+R=2, y en la demostración por inducción de esa fórmula hemos usado una cierta propiedad de los grafos:

Al unir dos vértices de un grafo plano, conseguimos una región más, ya que creamos un nuevo ciclo.

¿Es esto cierto? Pues bien, en el plano es evidente que sí como se veía en los grafos de más arriba, sin embargo, hay espacios en los que esto no es cierto. Un buen ejemplo es el famoso toroide:

Toroide, superficie con forma de Donut

Toroide, superficie con forma de Donut

¿Podemos crear un grafo plano en el que creemos un ciclo y sigamos teniendo el mismo número de regiones? La respuesta es sí, nos podemos aprovechar del agujero del medio para hacerlo de la siguiente manera: rodeando el anillo del toroide con un ciclo. Como se observa en la imagen, en la superficie del toroide hemos creado un ciclo pero sigue habiendo una única región:

Ciclo que no separa regiones

Ciclo que no separa regiones

Eso significa que en un toro la formula de Euler es falsa, ya que, si por ejemplo en el ciclo anterior metemos dos vértices de manera que tengamos un grafo, tenemos 2 vértices, 3 aristas y 1 región: V-E+R=2-2+1=1\neq 2, y por lo tanto toda nuestra demostración de que el acertijo es imposible de resolver es falsa si nos encontramos en un toroide. ¿Es entonces posible resolver el acertijo en este espacio? De nuevo, la respuesta es sí, podemos aprovecharnos del agujero para hacer pasar por ahí una de las aristas, de manera que lo completamos sin cortar ninguna arista:

Acertijo resuelto en la superficie de un toroide

Acertijo resuelto en la superficie de un toroide

Si contamos regiones, veremos que hay 3, y como esperábamos, en este caso la fórmula de Euler no se cumple: V-E+R=6-9+3=0\neq 2

De modo que es imposible resolver el acertijo en un plano, pero sí en otro tipo de superficies en los que no se cumpla la fórmula de Euler. ¿Existen más superficies de este tipo? Sí, la famosa banda de Möbius es otro ejemplo. Para quien no conozca esta superficie, aquí dejo su enlace en la Wikipedia: Banda de Möbius. Es una de las llamadas superficies no orientables, ya que a diferencia de, por ejemplo, un papel, la banda de Möbius tiene una sóla cara, no dos, y un sólo borde: en este tipo de superficies es imposible definir un vector perpendicular a ella que define su orientación porque cabe la posibilidad de mover el vector sin salir de la misma cara y llegar al mismo punto pero con el vector en sentido contrario. En este caso el acertijo se puede resolver así, si cortas una banda de papel y lo dibujas de la siguiente manera antes de construir la banda, lo tienes resuelto:

Una de las caras del papel al construir la banda

Una de las caras del papel al construir la banda

Unes los dos extremos para formar la banda Möbius y puesto que no es orientable puntos opuestos son en realidad el mismo, haciendo así que las líneas coincidan entre sí. El resultado final es este:

Problema resuelto en una banda de Möbius

Problema resuelto en una banda de Möbius

En este caso volvemos a resolver el problem, y si contamos las regiones contaremos 4, de modo que V-E+R=6-9+4=1 y la fórmula de Euler vuelve a fallar.

¿Puedes encontrar más superficies en las que podamos resolver esto? Como pista, observa que en los dos ejemplos se cumplía que podíamos formar ciclos que no separasen regiones, y esos ciclos son circunferencias, que en un lenguaje más técnico, no son homótopas a ningún punto de la superficie. Eso significa que no se pueden encoger hasta un punto sin salirse de la superficie. Intenta construir más superficies en las que existan este tipo de ciclos.

Como última nota, quiero decir que la demostración que hemos hecho arriba sobre que esto es imposible en el plano está contemplado dentro de un teorema más general que se encuentra en teoría de grafos, conocido como Teorema de Kuratowski, que además de decir lo que decimos nosotros, lo dice también del grafo completo de 5 vértices: K_5, y el teorema va en doble sentido, es decir:

Teorema de Kuratowski

Un grafo es plano si y sólo si no contiene ninguna subdivisión isomorfa a K_5 o a K_{3,3}

K_{3,3} es el grafo del que hemos estado hablando, el grafo del acertijo, y se llama grafo bipartito de orden 3. Una subdivisión de un grafo se obtiene elminando aristas, vértices, o ambos, o eliminando vértices de dos aristas. Por ejemplo el siguiente grafo no es plano, ya que si quitamos los dos vértices marcados en rojo y dejamos que las aristas unan los dos vértices inferiores y superiores de los dos extremos, obtenemos K_{3,3}:

Grafo no plano

Grafo no plano

Bueno, pues hasta aquí. Ta lue…

Anuncios
Esta entrada fue publicada en Matemáticas y etiquetada , , , , , , , , , , , , , , . Guarda el enlace permanente.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s