Teoría de grafos

El año pasado di en l asignatura de Matemáticas I la teoría de grafos. La verdad es que es una parte de las matemáticas que me parece bastante chula, sobre todo por su facilidad. Por ejemplo, sirve para solucionar los dichosos pasatiempos esos de hacer un dibujo sin levantar el lápiz del papel. Quizás el más famoso de estos pasatiempos es el de la casita.


Si tratais de hacerlo, vereis que por más que lo intenteis no lo lograreis hacer. En cambio si unis el punto 3 con el 5, et voila! ya hay solución.

Para llegar a la solución hay que tener ciertas nociones básicas:
Las figuras pueden contener o contienen los siguientes elementos
- Vértices: Mundialmente conocidos, son esos puntitos donde terminan cada línea
- Aristas: Son las líneas que unen dos vértices
- Arcos: Son líneas que unen dos vértices. En este caso, tienen dirección y el camino sólo se puede tomar en un sentido (el que indique la flecha)
- Lazo: Son caminos que unen un vértice consigo mismo sin pasar por ningún otro vértice

Otros términos de interés son:
- Grado (de un vértice): es el número de aristas que inciden sobre ese vértice
- Ingrado: es el número de arcos que tienen al vértice como final
- Exgrado: es el número de arcos que tienen al vértice como principio
- Cola euleriana: Es una cola que recorre todas las aristas del dibujo sin repetir ninguna de ellas

Pues bien, estos conceptos son básicos para resolver este tipo de pasatiempos (conocidos científicamente como circuito euleriano)
Según el teorema de euler, como el circuito recorre todas las aristas, cada vez que se accede a un vértice por una arista se sale por otra distinta, luego el grado de cada vértice debe ser par.

Estos serán los circuitos más fáciles de resolver y los que nunca nos habrán suponido problema.

Sin embargo hay unos distintos que son aquellos que poseen dos vértices de grado impar y los demás de grado par. Para resolver cualquier tipo de cola euleriana utilizamos el algoritmo de Fleury:

1.- Empezar en un vértice de grado impar. Si no lo hay, empezar en cualquier vértice.
2.- Si el grado del vértice es 0, pues paramos
3.- Si el grado es 1, corremos la arista que nos da ese grado y pasamos a 5
4.- Si el grado es mayor de 1, cogemos una arista que no nos cierre camino
5.- Volvemos a empezar en 1

Pues bien, esta es la mecánica, por ejemplo, en el ejemplo de la casita habría que empezar en el vértice 1 o 2 para conseguirlo. (Si os fijais, el final del circuito se encuentra en el vértice impar que no habías elegido para empezar a dibujarlo)

Pues una vez que os he dado la teoría, os toca llevarlo a la práctica. Os pongo aquí un juego que sigue estos patrones. Solo teneis que modificar los vértices por ventanas encendidas y ya está


NOTA: En el gráfico de la casita habría que cambiar los arcos por aristas