Hace ya bastante tiempo pudimos ver en El Pito Doble el juego SuPuzzle:
La presentación del juego es la que aparece en la imagen. El objetivo del mismo es conectar cada una de las casas de la fila superior con los tres círculos de la fila inferior si que ninguna de las líneas de conexión corte a otra. En este punto os dejo intentarlo para ver quién es el primero en conseguirlo.
Si representamos cada uno de los iconos (tanto las casas como los círculos) mediante puntos (vértices) y tomamos también las líneas de conexión (aristas) lo que obtenemos es un grafo.
Llamando a los vértices superiores y
a los inferiores y representando como
a la arista que une el vértice
con el vértice
obtenemos el grafo conocido como
:
Seguís intentando conectar las tres casas con los tres círculos, ¿no? Por intentarlo que no quede, continuad con ello.
Partiendo de que dos aristas de un grafo sólo pueden contarse en un vértice (es decir, que si tenemos dibujados los vértices de antemano dos aristas no pueden cortarse en ningún punto nada más que en ellos) vamos a definir ahora lo que es un grafo plano:
Se dice que un grafo es plano si puede embeberse (algo así como «meterse») en
.
Es decir, un grafo es plano si podemos dibujarlo en un papel sin que ninguna de las aristas corte a otra en un punto que no sea un vértice.
Ahora, antes de dar la solución del juego, vamos a definir otro grafo, :
Es decir, es un grafo que tiene 5 vértices y que tiene como aristas todas las líneas que conectan cada vértice con todos los demás, como podéis ver en la imagen. A este grafo también se le denomina grafo completo de 5 vértices.
Y ahora vamos con la solución del asunto. El matemático polaco Kazimierz Kuratowski demostró lo siguiente (os dejo una versión débil del teorema):
Teorema de Kuratowski:
Un grafo es plano si no contiene como subgrafo a
ni a
.
Es decir, ni ni
son grafos planos (ya que cada uno de ellos se contiene a sí mismo como subgrafo). O lo que es lo mismo, no pueden dibujarse en un papel con la condición de que ninguna arista corte a otra en un punto que no sea desde el principio un vértice.
La demostración de este teorema necesita de ciertos conocimientos previos sobre teoría de grafos relativamente avanzados y es algo complicada, por eso no la adjunto. Yo la conocí en 4º de carrera y la verdad es que me pareció bastante curioso el asunto ya que responde la típica pregunta que mucha gente se hace con las matemáticas: ¿pueden las matemáticas resolver problemas, digamos, tangibles? La respuesta es sí: en este caso las matemáticas nos dicen por qué no podemos realizar ese dibujo con esas condiciones.
Imágenes sacadas de Teorema de Kuratowski en la Wikipedia (español).
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Me suena haber leído en alguna parte que el grafo K3,3 se puede resolver sin cortes entre aristas, si en lugar de construirse sobre un plano, se construye sobre una cinta de Moëbius. ¿Es cierto?
@ÓsQar: creo que es en el TORO en donde sí es posible incluir el grafo…
Si
es el género (=número de asas o agujeros) mínimo de la superficie que permite dibujar el grafo sin que las aristas se corten, entonces
, donde
es el menor entero mayor o igual que x.
Usando la fórmula de Euler-L’Huillier para superficies de cualquier género topológico creo que no es difícil demostrar que
Por tanto
pueden dibujarse en un toro (= un rectángulo en que una linea que sale por un borde aparece a la misma altura del borde opuesto) sin que se corten las aristas.
El teorema es cierto, pero el juego puede completarse. En el juego tenemos ciertos grados de libertad extra. Eso significa que no estamos limitados a dos dimensiones 😉
segundo año de carrera y ya estoy viendo esto!
para el primero en un momento de certamen colocamos que no era plano x tener grado 3 en mas de dos nodos… eso sirve?
Los grafos son herramientas poderosisimas!!!
rmcantin cierto, el juego tal cual está nos permite mediante un truco saltar al espacio tridimensional y completarlo, aunque en el plano no podamos.
solución tiene… basta con llevar el gas mediante bombonas de butano xD
¿Esta correctamente formulado el teorema de Kuratowski? Si no recuerdo mal, no contener a ni es condición necesaria pero no suficiente para que un grafo sea plano. Es decir, si contiene alguno de ellos sabemos que no es plano, pero que no los contenga no nos confirma que lo sea. Nosotros (informática de sistemas) estudiamos grafos en primero: una parte de la asignatura de álgebra es Matemática Discreta y nos los meten ahí. Aunque yo hice álgebra este último año :P. Si mi memoria no falla, el profesor nos afirmó que no hay ningún teorema o fórmula que determine si… Lee más »
ÓsQar, es bastante sencillo resolverlo tanto en un toro como en una botella de klein (bueno, he tenido que usar colores distintos en la botella para no liarme).
Hay una demostración sencilla para el plano y la esfera, aunque hay que hacer un dibujo para verlo. La he encontrado en http://www.cut-the-knot.org/do_you_know/3Utilities.shtml. Si las casas son los vértices A, B, C y los círculos son E, F, G, en una supuesta solución las aristas AE, EB, BF, FC, CG y GA forman una curva cerrada AEBFCGA. Las aristas restantes son AF, BG y CE. Si una de ellas se traza por el interior de AEBFCGA, deja aislados los otros pares de vértices por el interior y no se pueden trazar más aristas por el interior. Si una de ellas… Lee más »
En la cinta de Möbius también se puede hacer
La solución del juego 😉 para q no tengais q buscarlo.
http://es.youtube.com/watch?v=O0RzybS3ZiA
Enhorabuena y gracias por el blog 😀
Gulliver:
Conozco la demostración de la curva de Jordan, me gustaria saber como se puede hacer en la cinta de Mobius.
Jime, se puede construir el grafo en la cinta de Möbius. El resultado es una escalera de Möbius con tres peldaños, es decir una escalera de tres peldaños en la que se une el principio con el final con una torsión. Cuando se circula por el borde de la cinta, se dan dos vueltas a la cinta antes de llegar al mismo punto. Primero se trasladan las casas y los círculos para situarlos cerca del borde, de modo que al recorrer el borde se vaya pasando cerca de ellos en este orden: A-E-B-F-C-G-A. Luego se traza la curva cerrada AEBFCGA… Lee más »
Cuando los puntos del problema se convierten en casas, estos puntos dejan de ser eso, puntos, y se convierten en áreas. Estas áreas, como ya ha dicho rmcantin, le añaden al problema otro grado de libertad extra que permite su resolución. Por cierto, la solución de MaNu2 es válida, pero poco elegante y aparte de que los de la compañia del gas no te iban a dejar meter la acometida del agua por ahí, para el tío de la retro iba a ser un lío. Hay una solución más sencilla (aunque en el fondo sigue el mismo principio) que además… Lee más »
Cuando yo tenía 10 años o asi, mi papi me propuso este problema para resolver.
Yo, tonta de mi, me pasé una semana gastando papel intentando dibujar los caminos :@
@Rosa: tienes un padre un tanto guasón
[…] Para demostrar que el caso de 5 ciudades no se puede hacer sin cruces puedes utilizar la Fórmula de Euler; en este documento (pdf) puedes ver cómo. Este grafo para 5 ciudades se llama grafo completo K_5 y el matemático polaco Kazimierz Kuratowski demostró que es una pieza clave para saber cuándo un grafo se puede dibujar sin cruces. Puedes leer dos entradas interesantes al respecto en este enlace o en este otro. […]
[…] que muchos de vosotros conocéis el problema de las tres casas y los tres suministros. Sí, ése en el que hay que intentar conectar tres casas con tres centrales de suministro de agua, […]
A mí me plantearon el problema de las casas y los gatos como un juego en el colegio. ¡Anda que no perdí horas intentándolo!