Grafos de Kuratowski

Hace ya bastante tiempo pudimos ver en El Pito Doble el juego SuPuzzle:

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 u_1,u_2,u_3 a los vértices superiores y v_1,v_2,v_3 a los inferiores y representando como u_iv_j a la arista que une el vértice u_i con el vértice v_j obtenemos el grafo conocido como K_{3,3}:

K_{3,3}= \lbrace u_iv_j / i,j=1,2,3 \rbrace

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 \mathbb{R}^2.

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, K_5:

K_5= \lbrace u_iu_j / i=1,2,3,4,5 \rbrace

Es decir, K_5 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 K_5 ni a K_{3,3}.

Es decir, ni K_5 ni K_{3,3} 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).

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

18 Comentarios

  1. 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?

    Publica una respuesta
  2. Si g(G) 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 g(K_{m,n}) = \left \lceil \dfrac{(m-2)(n-2)}{4} \right \rceil = A , donde \lceil x \rceil 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 g(K_{m,n}) \ge A

    Por tanto K_{3,3}, \ \ K_{3,6} \ \ y  \ \ K_{4,4} 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.

    Publica una respuesta
  3. 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 😉

    Publica una respuesta
  4. 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!!!

    Publica una respuesta
  5. rmcantin cierto, el juego tal cual está nos permite mediante un truco saltar al espacio tridimensional y completarlo, aunque en el plano no podamos.

    Publica una respuesta
  6. solución tiene… basta con llevar el gas mediante bombonas de butano xD

    Publica una respuesta
  7. ¿Esta correctamente formulado el teorema de Kuratowski? Si no recuerdo mal, no contener a K_{3,3} ni K_{5} 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 un grafo es realmente plano, salvo encontrar una inmersión plana que lo demuestre.

    Por cierto, ya que estamos, en los repositorios de Ubuntu está el juego gplanarity, consistente en ordenar los vértices de enormes grafos hasta encontrar una inmersión plana de los mismos. Una chorradilla, pero que para un rato muerto te entretiene.

    Publica una respuesta
  8. Ó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).

    Publica una respuesta
  9. 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 se traza por el exterior ocurre lo mismo. Así que de las aristas AF, BG y CE, a lo sumo se puede trazar dos sin cortar a las demás, una por el interior de AEBFCGA y otra por el exterior, la tercera debe cruzar otras aristas.

    Publica una respuesta
  10. Gulliver:
    Conozco la demostración de la curva de Jordan, me gustaria saber como se puede hacer en la cinta de Mobius.

    Publica una respuesta
  11. 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 que sigue el borde y por tanto da dos vueltas a la cinta. Los pares A-F, B-G, C-E, quedan ahora uno enfrente del otro, a cada lado de la cinta, y basta con trazar líneas que los unan (los peldaños).

    Publica una respuesta
  12. 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 te permite resolver el problema con un número indefinido de casas y compañías, ya sabéis:
    ¡a por él!

    Publica una respuesta
  13. 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 :@

    Publica una respuesta
  14. 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!

    Publica una respuesta

Trackbacks/Pingbacks

  1. Puntos, rectas y un problema sin resolver que cualquier niño puede entender | Cifras y Teclas - [...] Para demostrar que el caso de 5 ciudades no se puede hacer sin cruces puedes utilizar la Fórmula de…
  2. El problema de las tres casas y los tres suministros y la banda de Möbius - Gaussianos - [...] que muchos de vosotros conocéis el problema de las tres casas y los tres suministros. Sí, ése en el…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *