Posts etiquetados con ‘teoría de grafos’

Otra forma de ver una página web: grafos

Me he encontrado con una página bien curiosa. No tiene utilidad (que a mi se me ocurra), pero como tampoco voy a medir todo por su utilidad… la voy a presentar simplemente porque me ha gustado. Se llama Webpages as Graphs.

En esa página se puede ver cómo su autor, Marcel Salathé, ha creado una aplicación que lee el código html de una página web cualquiera y crea un grafo a partir de esa información. Los nodos representan las diferentes etiquetas que se pueden encontrar en el código y los colorea con el siguiente criterio:

  1. azul: enlaces (corresponde a la etiqueta A),
  2. rojo: tablas (etiquetas TABLE, TR y TD),
  3. verde: etiqueta DIV,
  4. violeta: imágenes (etiqueta IMG),
  5. amarillo: formas (etiquetas FORM, INPUT, TEXTAREA, SELECT y OPTION),
  6. naranja: para saltos de línea y citas (etiquetas BR, P y BLOCKQUOTE),
  7. negro: para el nodo inicial (etiqueta HTML),
  8. gris: el resto de etiquetas.

Por último, el enlace entre dos nodos representa que una etiqueta está anidada dentro de otra. Eso implica que, estrictamente, es un grafo dirigido y los enlaces deberían dibujarse como flechas. Pero, tratándose de un divertimento, tampoco tiene mayor importancia.

¿Cómo luce el grafo asociado a la página web de nuestro grupo de investigación (CSG)?

repositorio

¿Y el de la página web de Madri+d? Pues así de florido.

repositorio

Etiquetas: ,

Cuando saber plantear un problema es casi la solución

En uno de los maravillosos libros del genial divulgador Martin Gardner, ¡Ajá! Inspiración, pude leer, hace ya mucho tiempo, un curioso problema que quiero compartir ahora con los lectores del blog. Tenemos 2 caballos blancos y 2 caballos negros de ajedrez en un tablero 3×3, tal y como muestra la imagen. ¿Cuál es el número mínimo de movimientos necesarios para intercambiar las posiciones de los caballos blancos y negros?

Posición inicial

El problema en sí es sólo un pasatiempo, pero lo presento aquí porque me parece un buen ejemplo de cómo la solución a un problema pasa, en muchas ocasiones, por transformarlo en otro equivalente mucho más fácil de resolver. En este caso encontrar una solución llevará un rato pero se acaba logrando. Sin embargo, si no se cambia de enfoque, es difícil imaginar cómo se demuestra que una solución es mínima.

En la entrada de este blog, “Para comenzar, hablemos un poco de Euler”, se describe cómo Euler fue capaz de resolver el problema de los puentes de Königsberg transformando las diferentes partes de la ciudad y sus puentes en un grafo (un matemático diría que encontró un problema isomorfo). En el problema propuesto, la clave para resolverlo (el “momento ¡ajá!” que diría Martin Gardner) pasa por generar el grafo asociado a los movimientos de los caballos.

¿Y cómo se hace eso? Uniendo con una línea los pares de celdas involucradas en un salto de caballo. Por ejemplo, si numeramos las celdas del 1 al 9, un caballo en 1 puede ir a 6 y a 8, luego dibujamos una línea de 1 a 6 y otra de 1 a 8. Repitiendo el proceso para el resto de celdas obtenemos el siguiente grafo:

Todos los posibles saltos de caballo

Pero ese grafo, que parece un barullo de líneas e inútil para resolver el problema planteado, es en realidad el sencillo grafo de la imagen (¡compruébalo tú mismo!):

Grafo simplificado de los saltos de los caballos

Las celdas del tablero son llamadas nodos en teoría de grafos y las líneas entre pares de celdas, enlaces. Cuando unimos un par de celdas con un enlace, indicamos que ese par de celdas están comunicadas mediante un salto de caballo. La celda 5 queda aislada debido a que no existe salto de caballo que nos lleve a ella, pero las restantes quedan ordenadas en forma de un anillo. Y con esta sencilla, aunque ciertamente inspirada, transformación el problema se resuelve fácilmente: el número mínimo de saltos necesarios para intercambiar los 4 caballos es 16 (¿ves cómo?).

Un planteamiento adecuado hace que un problema, que de otra forma sería difícil, se resuelva cómodamente. Ese es el convencimiento que tenemos quienes nos dedicamos a las Redes Complejas. Hoy día existe una gran cantidad de publicaciones en los que, de forma reiterada, se comprueba que con este enfoque se entienden mejor las intrincadas relaciones entre los constituyentes de sistemas muy diversos. Una extensa lista de referencias se puede encontrar en Physics Report 424, Issue 4-5, February 2006, Pages 175-308.

Etiquetas: ,
Categorias: General

Para comenzar, hablemos un poco de Euler

Es casi una obligación comenzar este Blog sobre Redes Complejas hablando de Leonard Euler, ya que es considerado el padre de la Teoría de Grafos. Euler nació en Basilea en 1707 y fue, junto con Paul Erdös (del que hablaremos próximamente), uno de los matemáticos más prolíficos de la historia. Es de destacar que trabajara en casi todas las disciplinas de las matemáticas, desde geometría, cálculo o  trigonometría, hasta álgebra y teoría de números, realizando incluso diversas incursiones en el campo de la física.

Leonard Euler

Figura 1.- Leonard Euler (Basilea 1707, San Petersburgo 1783). Se puede observar en la imagen cómo uno de sus ojos ya le comenzaba a fallar. Acabaría perdiendo totalmente la visión, lo cual no le impidió seguir investigando y publicando trabajos de gran impacto científico.

Pero vayamos a la historia que, según cuenta la leyenda, dio lugar al origen de la Teoría de Grafos (y más adelante a lo que se conocería como Redes Complejas). A principios del siglo XVII, Königsberg (actualmente Kaliningrado, Rusia) era una tranquila ciudad de la Prusia Oriental. Como muchas otras ciudades europeas, estaba atravesada por un río, el Pregel, que dividía la ciudad en dos mitades, a las que había que sumar dos pequeñas islas debidas a una bifurcación del río.  Para facilitar el paso de una parte a otra de la ciudad, así como a cada una de las islas, se habían construido un total  de siete puentes. El problema de los puentes de Königsberg era sencillo en su planteamiento: ¿es posible visitar a pie todas las zonas de la ciudad, volviendo al punto de partida, pero pasando una única vez por cada puente?

La respuesta es sencilla si se dispone de tiempo y paciencia, ya que se pueden calcular todas las posibles combinaciones de paso por los puentes para llegar a la conclusión de que no es posible: siempre hay que pasar dos veces por uno de los puentes. Como digo, la solución ya era conocida, sin embargo, el mérito de Euler fue encontrar una solución sencilla y elegante, que resolvía no solo el dilema de los puentes de Königsberg, sino también casos mucho más generales. Solo había que transformar a la ciudad y sus puentes en una red.

como proyectar...

Figura 2.- Como proyectar el entramado de puentes de Königsberg en una red.

Si se considera cada una de las zonas de la ciudad como un nodo y cada uno de los puentes que las une como un enlace, es posible obtener una red de 4 nodos y 7 enlaces (ver Figura superior). A partir de ahí, es sencillo demostrar que si queremos iniciar y finalizar el camino en el mismo punto necesitamos dos requisitos: a) que los nodos por los que pasemos tengan un número par de enlaces y b) que en el caso de tener un nodo con un número impar de enlaces, este debía ser el inicio (y final) de nuestro camino. Desgraciadamente, Königsberg no cumplía el primer requisito.

Y fue con este ejemplo tan curioso como Euler creó, sin saberlo, lo que se conoce hoy en día como la Teoría de Grafos. Es interesante como, una vez más, se repite el mecanismo que permite a la ciencia dar saltos de gigante:  si tenemos un problema, ataquémoslo desde  nuevos puntos de vista.

Como curiosidad, Kaliningrado, la antigua Königsberg, conserva hoy en día solo cinco de sus puentes (es lo que tienen las guerras mundiales!). Sin embargo, todavía no es posible realizar lo que se conoce como un “ciclo euleriano”…

Etiquetas: ,