Friday, November 06, 2009

GRAFOS

Los grafos



……¨ grafos y redes tienen propiedades, ocultas bajo su estructura, que limitan o multiplican nuestra capacidad para hacer cosas con ellas ¨
L Barabasi
Es muy difícil tomar conciencia de la importancia que han tenido y tienen los juegos en todos los órdenes de nuestra vida y lo es mas aun, saber que ellos han sido durante milenios un acicate encubierto del conocimiento científico. Tal vez aquello, lo de la importancia de los juegos, sea una buena excusa o una buena defensa para los que se pasan la vida jugando o que creen que la vida es solo un juego.

Pero no es la parte exclusivamente lúdica de los juegos lo que quiero compartir con Uds., como tampoco la historia de los juegos de azar, la cual si bien es también muy importante, por su intima relación con el calculo probabilidades, tiene su propia historia y ella no es menos interesante. En realidad, tampoco las fronteras entre las distintas formas de jugar son muy rígidas.

Con la modestia que da conocer los propios limites, lo que quiero simplemente es relatar de manera muy sintéticamente lo que comenzó siendo solo en apariencias únicamente un pasatiempo, y que le permitió a una mente preparada avanzar y ver mucho mas allá de lo que veían el común de los habitantes de un determinado lugar en el norte de Europa.

Lamentablemente esta meta visión nos es negada a la mayoría de los seres comunes, pero ello no es un impedimento para que tratemos de caminar pisando las huellas de los iluminados.

La historia rescata un hecho que aconteció siglos atrás y nos permite comprobar como aquello que era solo un juego inocente de algunos lugareños aburridos e ingeniosos, se transformo en un desafió para los habitantes y los visitantes de Koenisberg, convirtiéndose posteriormente en el germen que dio nacimiento a la teoría de los grafos, ciencia que esta íntimamente relacionada con la topología, rama de la matemática tan extraña como su madre.
No es tan frecuente conocer cual es el problema que da nacimiento a una disciplina, felizmente acá se nos brinda la oportunidad.

Topologicamente, triángulos, cuadrados, círculos y otras muchas figuras adquieren una semejanza impensada que les otorga generosamente esta nueva geometría, mas interesada en las relaciones que en los números, hecho este que ocupa un lugar que le negara la aritmética desde hacen milenios. ¿Sorprende? A mi si.

Ambas disciplinas, la de los grafos y la topología, se constituirían en un matrimonio que con el tiempo se convertiría en un instrumento imprescindible para la ciencia de las redes.
Esta ultima, la ciencia de las redes, tiene como objeto el estudio de los sistemas conectados, lo cual es una manera pálida pero apropiada de representar la estructura compleja de la realidad en la que estamos inmersos y de la que somos parte.


Pero veamos concretamente en que consistía el jueguito que contribuyo al nacimiento de una nueva ciencia.

En Koenigsberg (hoy Kaliningrado,) el río Pregel que rodea la ciudad dividiéndose
en dos brazos, posibilitaba la unión del territorio mediante siete puentes, esto para
los habitantes, por aquellos años, era motivo de distracción ,en la actualidad seria una ingenuidad incluso para los mas chicos.

En fin, el desafió consistía en unir la ciudad sin pasar dos veces por el mismo puente.




Este problema no es diferente a aquellos juegos que con figuras hechas a mano alzada, la mayoría de nosotros hemos resuelto con mayor o menor dificultad durante nuestra infancia o adolescencia. Una de aquellas figuras a las que me refiero consistía en dibujar un sobre abierto sin pasar dos veces por la misma línea, el problema se tornaba imposible de resolver cuando se debía dibujar el sobre cerrado.

Pienso que tal vez algún matemático introdujo el problema que representan estas figuras y otras muchas con la esperanza, vana, de que alguno se interesara en el desafió y buscara en profundidad.

Hoy podemos acceder al conocimiento, a través de nuestra querida matemática, ella generosamente nos dice que figuras podemos y que figuras no podemos hacer respetando las reglas que nos impone. Las situaciones posibles o imposibles son muy numerosas.

Creo obvio decir, que aquellos lugareños estaban muy lejos de imaginar la complejidad implícita en este juego que habían inventado y propuesto a propios y extraños, ratificando que los problemas muchas veces superan la imaginación de los creadores. Un pasatiempo intrascendente para muchos y también para muchos pensadores, fue sin embargo un nuevo Caballo de Troya que encerraba y encierra numerosos problemas y soluciones.

La serendipidad, es ese don esquivo solo reservado a pocos, a aquellos que ante lo casual ven causalidades, a esos quienes poseen un poder de abstracción que los ubica en la categoría de genios.

En palabras comunes y apropiadas de un pensador cuyo nombre no recuerdo y que viene al caso, acuerdo con firmeza que :

¨ El poder observar lo que se oculta bajo la superficialidad de las apariencias no es patrimonio del democrático sentido común ¨.


El personaje iluminado e iluminador de nuestra historia fue L Euler, considerado el príncipe de la matemática, fue quien resolvió el problema de los siete puentes de Koenisberg sin caminar un solo paso, pero provisto del instrumento intelectual mas importante que tiene una persona, y que mencionáramos más arriba, la capacidad de abstracción.

L Euler vio nodos y enlaces en lugar de las áreas de la ciudad y los siete puentes que la unían, y dio por terminado el desafió al descubrir que ese pasatiempo matemáticamente no tenia solución.

La grandeza de su descubrimiento no quedo dentro de los limites de Koenisberg , presento su trabajo en la Academia de Ciencias de San Petersburgo, ciudad cercana que tuve oportunidad de conocer en 2006, y su presentación académica es considerada hoy como el germen de la Teoría de los Grafos, que como decía mas arriba tiene estrechas e indisolubles relaciones con la topología y la ciencia de las redes .

A la topología Leibniz la bautizo con el nombre de geometría de la posición y es conocida entre otras cosas además como la geometría de la página de goma o el análisis de sitio.

Este menage a trois integrado por grafo-topológia-redes, tiene múltiples aplicaciones, mas de la que imaginamos a simple vista, y nos permite solucionar una cantidad de problemas cuyo espectro va desde los de orden absolutamente practicos y cotidianos a los mas sofisticados y complejos.

En los mapas comunes de una ciudad sin saberlo, cambiamos alegre y oportunamente la exactitud de la geométrica clásica que requerimos forzosamente para otras disciplinas, por la utilidad que nos brinda la información grafico-topológica.
Si no nos resulta claro ver de que se trata el cambio, pensemos en la complicación, casi sin solución, que seria poder comprender y utilizar el mapa mas simple de una ciudad, aun aquel de la mas pequeña, si priorizamos la precisión de todos los datos sobre la utilidad de los mismos.

Un mundo o la realidad absolutamente precisa puede llegar a ser con seguridad intolerable, Borges lo expresa por supuesto mucho mejor;

……………..Era el solitario y lucido espectador de un mundo multiforme, instantáneo y casi intolerablemente preciso.
………..Pensar es olvidar las diferencias, es generalizar, abstraer. En el abarrotado mundo de Funes no había sino detalles casi inmediatos.
( Funes el memorioso)

Esta breve mención de Borges es más que clara acerca de la significación que confiere a la abstracción, de la importancia de conceptualizar y que no siempre podemos considerar como beneficio ser muy precisos como evidencia el caso de Funes el personaje de ficción , para el cual la precisión paso a ser su rutina obligada.


La complejidad y los grafos

Uno de los desafíos de nuestro siglo es enfrentar la complejidad, A. L. Barabasi lo expresa de manera muy entendible al decir que debemos unir lo conocido con lo desconocido, lo archisabido con lo sorprendente, lo previsible con lo inesperado.

Con este criterio y separando solo provisoriamente, para evitar que el bosque nos impida ver el árbol y que aquel no nos impida ver este, vamos a referirnos a los usos, las características básicas y la teoría de los grafos cuya aparente simpleza como decía mas arriba es solo un engaño.



Utilidad de los grafos:

Los grafos son una forma de representación natural de las redes y estas a su vez lo son de la realidad, son artificios matemáticos que nos permiten expresar de manera sencilla y visual las relaciones entre elementos de muy diversa índole y nos habilitan a que podamos preguntarnos infinidad de cosas y empezar además a comprender, lo que tienen de común Hormigas, neuronas, ciudades y software,
(subtitulo del libro Sistemas Emergentes de S Johnson).
.
Creo que este comentario es tan abarcativo y sus consecuencias tan importantes que nos brindan un horizonte de posibilidades, universalidad que la hace merecedora del esfuerzo de tener aunque sea una idea aproximada de su formalización simbólico-matemática para poder comprender mejor su omnipresencia y su ubicuidad.
Dejando como un desafió personal para quien lo desee, la profundización de su base matemática, recordemos solamente que su aplicación en la resolución de problemas comprende todas aquellas áreas donde la conectividad es importante y que por lo tanto incluye distintos sistemas como los educativos, los sistemas de salud , los sistemas de información. la geografía, las distintas redes de servicios públicos , carreteras ,redes de agua ,de gas electricidad, de transporte, de semáforos , redes sociales, etc.
En 1847 Gustavo Kirchhoff formula las leyes de electricidad que llevan su nombre y desarrolla en las redes de electricidad la noción de árbol, un tipo especial de grafo cuya utilidad fue recogiendo adeptos en la química, la biología, la teoría de decisiones, de la información, de las comunicaciones, y muchas otras áreas y disciplinas que aceptaron rápidamente el convite y sumaron a sus desarrollos las utilidades de los grafos la topología y las redes


¿Pero que es un grafo?

Esto es casi como comenzar por el final, pero esa fue la intención, generar el interés antes que intentar su definición.
Podemos definir el grafo como; una representación, un modelo, compuesto por un número determinado de vértices (nodos) y un número de arcos (aristas) que los relacionan, cada arista o arco tiene la capacidad de relacionar nodos.


Las normas del diseño

Existen una serie de reglas para diseñar los grafos cuya fundamentacion teórica esta disponible y aguarda a los osados que pretendan profundizar el tema, yo solo mencionare unos pocos conceptos, dejando la llave o mejor el llavero en las manos de los interesados

Un vértice o nodo se dice que es impar si de él parten un número impar aristas, este concepto es importante porque fue el que le permitió a Euler descartar de plano el problema de los puentes.


a) Si todos los vértices son pares, el punto de partida para una figura puede ser cualquiera.
b) la figura se puede hacer sin pasar dos veces por la misma arista cuando no hay más de dos vértices impares, uno al comienzo del recorrido, y el otro vértice impar al final.

Glosario

Árbol: es un grafo conexo que no tiene ciclos y que conecta a todos los puntos, es un grafo dirigido acicilico (GDA),el vértice inicial se llama raíz , los vértices con una sola arista se llaman hojas.
Camino: secuencia de nodos en que cada nodo es adyacente y nos permite una serie de medidas ; la distancia entre nodos, la longitud es decir como el numero de enlaces para ir de un nodo a otro , la longitud menor o camino geodésico , el peso o la conectividad.
Ciclo se define en teoría de grafos como un camino cerrado en un grafo, es decir, en que el nodo de inicio y el nodo final son el mismo.
Ciclo euleriano es aquel camino que recorre todos los vértices (nodos) de un grafo pasando una y sólo una vez por cada arista (arco) del grafo, siendo condición necesaria que regrese al vértice inicial de salida (ciclo = camino en un grafo donde coinciden vértice inicial o de salida y vértice final o meta). Una definición más formal lo define como: "aquel ciclo que contiene todas las aristas de un grafo solamente una vez".
Camino (path): secuencia de nodos y relaciones en la cual cada nodo sólo
puede ser usado una vez.
Camino euleriano: se dice que un grafo admite un camino euleriano cuando tiene exactamente dos nodos de grado impar (conexos a los caminos)
Camino hamiltoniano: es un camino que recorre todos los vértices de un grafo sin pasar dos veces por el mismo vértice. El camino hamiltoniano no impone regresar al vértice de partida,
Caras: conjunto poligonales de aristas cerradas que forman figuras poligonales sin vértices en el interior.
Cercanía (closeness): índice de la cercanía de un nodo con el resto de la red.
Ciclo hamiltoniano: camino hamiltoniano cerrado En el caso de que se pueda recorrer todos los enlaces sin pasar dos veces por el mismo nodo, el nodo de comienzo y el final será el mismo y todos los nodos han de ser necesariamente de orden par.Un ejemplo clásico es recorrer un museo grande visitando todas las salas una sola vez, para lo cual se deberá hacer o buscar un grafo con un ciclo hamiltoniano en el cual los vértices son las salas, y las aristas los corredores
Conexo: se refiere en relación a los grafos a aquellos en los que es posible conectar cualquier pareja de vértices por medio de un camino o en los que se puede pasar de un vertice a otro a través de uno o varias aristas sin levantar el lápiz del papel
Diámetro del grafo: es su distancia máxima, la longitud de su geodésico máximo, siendo este ultimo el camino mas corto entre dos nodos.
Dígrafo: son aquellos en los que el enlace se representa como una flecha que determina una dirección concreta, se denomina también grafo dirigido
Densidad: proporción de lazos existentes en relación con los posibles.
Diámetro de una red: geodésico más grande.
Distancia geodésica: distancia más corta entre dos nodos.
Geodésico: camino más corto entre dos nodos.
Grado de intermediación (betweenness): índice que muestra la suma de todos geodésicos, es decir, los caminos más cortos entre dos vértices que incluyen el nodo en cuestión.
Grafo: Un grafo es una representación, un modelo, que esta compuesto por un número determinado, finito, de vértices (nodos) y un número finito de arcos (aristas) que los relacionan. Cada arista o arco, tiene la capacidad de relacionar dos nodos. El grafo formado por dos conjuntos, a) nodos o vértices b) aristas, enlaces o arcos, que nos indican las relaciones de los nodos.
Grafo euleriano: si se pueden recorrerse de un solo trazo todas las aristas sin pasar dos veces por una misma de ellas, admite un ciclo euleriano
Grafo hamiltoniano: existe un recorrido según aristas del mismo que pase por todos los vértices del grafo una sola vez aunque queden aristas sin recorrer
Grafo orientado: grafo en el cual los caminos siguen una dirección.
Intermediario (broker): persona con un alto índice de intermediación. Si se quita de la red ésta se divide en componentes.
Lazos débiles: expresión popularizada por Granovetter que indica relaciones especializadas entre dos actores sociales.
Lazos fuertes: a diferencia de los lazos débiles indican relaciones sociales cercanas y solidarias.
Mosaico: grafo que se extiende a todo el plano (teselado)
Nodo adyacente: se dice de nodos en los que existe un enlace que los conecte
Orden del grafo: es el número de arcos que sale del nodo .En Koenisberg el orden de todos los (cuatro) nodos son impares. Solo se puede recorrer un grafo cualquiera sin pasar dos veces por el mismo enlace, si únicamente dos nodos impares y se comienza en uno de estos y se termina el recorrido en el otro nodo impar.
Red semántica: es un grafo en donde los vértices representan conceptos o clases de objetos
Relación fundamental: en todo grafo del plano aristas menos vértices más caras es igual a 1
Relación dirigida: relación que parte de un nodo hacia otro. Se presenta con una flecha apuntado al nodo receptor.
Relación valorada: relación calificada con un valor ordinal o de rango. Se opone a la relación binaria (presencia o ausencia) y permite gradaciones.
Relación recíproca: relación idéntica para cada uno de los dos nodos. Suele representarse con una línea sin flechas.
Seudo grafo: si los enlaces salen de un nodo y vuelven al punto de partida después de pasar
por otros y forman un bucle.
Vértice: unidad fundamental de la que están formados los grafos. Los vértices son tratados como un objeto indivisible y sin propiedades, aunque puedan tener una estructura adicional dependiendo de la aplicación por la cual se usa el grafo



Bibliografia
F Capra. La trama de la vida. Una nueva perspectiva de los sistemas vivos. Anagrama 1998
L Santalo y colaboradores. Enfoques. Troquel Ediciones 1994
J Gribbin . Asi de Simple. Drakontos 2006
A.L, Barabasi. Linked Penguin Group 2003
V Hernandez Forte. Mapas Conceptuales la Gestión del Conocimiento en la didactica. Alfaomega 2007
M Jenicek Epidemiologia la logica de la medicina moderna Masson 1996

No comments: