jueves, 21 de junio de 2012

Unos grafos que no son planos y la banda de Möbius

Una página que puedo recomendar ampliamente es Cut the Knot. Recientemente la redescubrí porque andaba buscando un modelo para realizar un "manifiesto matemático"; algo así como el "A Mathematician's Lament" de Lockhart, pero menos enfocado a la educación y más a la "defensa" de la Matemática como un arte, como una actividad no solo útil sino intrínseca a la humanidad. Ahí está uno, y de momento no puedo mejorarlo.

Pero no es eso de lo que quiero hablar en esta entrada. Antes de continuar, vale decir que un grafo básicamente es un montón de puntos conectados con líneas (no necesariamente rectas), y se dice plano si se puede redibujar en el plano euclidiano de modo que las líneas no se crucen (¡pero sin desconectar lo que originalmente está conectado, ojo!).

Resulta que hurgando en el susodicho sitio sobre la no-planaridad del grafo bipartito completo $K_{3,3}$ (y que popularmente está asociado al "problema del agua, luz y electricidad"), Stuart Anderson sugiere que una forma de demostrarla es embebiendo  $K_{3,3}$ en una banda de Möbius sin que se crucen sus aristas. Más aún: el mismo truco sirve para demostrar que el grafo completo de cinco vértices tampoco es plano.

Buscando en la red encontré que Maxim Rytin hizo un programa en Mathematica para ver la construcción de manera interactiva, y no sólo en la banda de Möbius, sino también en un toro. Mejor aún: ¡incluyó el maravilloso grafo de Petersen!

Sin embargo, sus embebimientos no son muy simétricos o satisfactorios desde mi punto de vista, así que decidí hacer los míos.
El grafo bipartito $K_{3,3}$. Noten la bella simetría que le proporciona la banda de Möbius. Los vértices con número par forman una parte y los impares la otra.
El grafo de Petersen. Bueno, tal vez debiera ser de Kempe, pero esa es otra historia.  El camino de las orillas puede pensarse como el pentágono exterior en los dibujos clásicos de este grafo, y el de en medio como el pentagrama interior.
El grafo completo $K_{5}$. De hecho, es la triangulación simplicial más pequeña de la banda de Möbius.
Espero se hayan dado cuenta de que los vértices están numerados con la notación de punto y barra (aprovecho para insistir en que no la inventaron los mayas). Esto es porque los símbolos son muy simétricos y aptos para el caso en que se dibujen sobre un material transparente. De hecho, es mejor construir así una banda de Möbius, porque el papel opaco "esconde" el hecho de que este espacio topológico solamente tiene una cara. Para que se puedan ver los vértices de los grafos apropiadamente, tuve que dibujarlos por los dos lados de la cinta antes de pegarla.

Es muy interesante que $K_{5}$ divide a la banda en triángulos, $K_{3,3}$ en rectángulos y el grafo de Petersen en "pentágonos". Como la característica de Euler (caras menos aristas más vértices) de la banda de Möbius es $0$, sucede que $K_{5}$ tiene $5$ caras triangulares, $K_{3,3}$ tres caras rectangulares y el grafo de Petersen $10$ caras pentagonales.

Si pulsan en los enlaces abajo de cada fotografía encontrarán unos archivos en formato PDF para imprimir y armar.


Esta entrada participa en la edición 3.14159 del Carnaval de Matemáticas, cuya bitácora anfitriona es Scientia.

7 comentarios:

Mago Moebius dijo...

Fantástica entrada!

Anónimo dijo...

La primera cinta està mal. Si partes del . i resignes por detrás de la cinta llegas al ...

Octavio dijo...

Híjole...

¡Muchas gracias! :D

De verdad que su comentario ya hizo que valiera la pena entrarle al Carnaval de Matemática(s).

Ciertamente es un gran honor que le haya agradado mi contribución.

Otra vez, gracias.

Octavio dijo...

Ah, y me refería al comentario de Mago Moebius. El segundo comentario llegó casi al mismo tiempo que escribía el tercero.

Octavio dijo...

No tengo comentarios sobre el segundo comentario, salvo que si llego a ver el error, lo corregiré.

Anónimo dijo...

Hola Octavio, soy el segundo comentario.
Creo que en tu cinta representas las 'casas' con ., .. y ... (punto, punto punto y punto punto punto). Pues bien, has conectado la 'casa' . (punto) con la casa ... (punto punt punto) ciando debería estar conectada con un 'suministrador'(agua, luz o electricidad que tu representas con barras o algo así ). Tengo dudas que la cinta 'solucione' el problema del primer grafo plano.

http://beutil.blogspot.com

Octavio dijo...

Respecto al comentario anónimo:

1) ¿Leíste que los vértices están numerados con la notación de punto y barra? Los puntos valen 1, las barras valen 5.

2) ¿Leíste que los números pares forman una parte y los impares la otra? Eso quiere decir que el 2, 4 y 6 podrían pensarse como las "casas" y 1, 3 y 5 como los "suministradores". O al revés, si se quiere.

3) ¿Construíste la banda según el modelo que proporciono? Con ella se ve muy claramente que cada par está conectado con todos los impares y viceversa.

:D