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).

Print Friendly, PDF & Email
0 0 votes
Article Rating

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉