Also available in English

Inf@Vis!

La revista digital de InfoVis.net

Grafos
por Juan C. D√ľrsteler [mensaje nļ 137]

Los grafos son la representación natural de las redes, en las que estamos cada vez más incluidos. Exploramos qué son los grafos, para qué sirven y algunas reglas para dibujarlos bien.
RedMetroBCN.gif (35432 bytes)
La red de metro de Barcelona. Los mapas de las líneas del ferrocarril metropolitano son grafos que muestran la conectividad de las estaciones. 
Fuente: TMB (Transports Metropolitans de Barcelona).
Pulse en la imagen para agrandarla.

Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole. Un grafo simple está formado por dos conjuntos:

  • Un conjunto V de puntos llamados v√©rtices o nodos.

  • Un conjunto de pares de v√©rtices que se llaman aristas o arcos y que indican qu√© nodos est√°n relacionados.

De una manera m√°s informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos.

En un grafo simple entre dos nodos sólo hay un arco. Si hay más de un arco hablamos de un multigrafo. Si los arcos se pueden recorrer en una en una dirección concreta pero no en la contraria lo llamamos grafo dirigido o dígrafo y los arcos son entonces aristas, si los arcos salen y llegan al mismo punto formando un bucle el grafo resultante se llama pseudografo. 

A pesar de que un grafo parece una estructura muy elemental, hay much√≠simas propiedades de los grafos cuyo estudio ha dado lugar a una completa teor√≠a matem√°tica. (Para m√°s informaci√≥n v√©ase por ejemplo el glosario de grafos de Chris Caldwell o la introducci√≥n en espa√Īol de la wikipedia o la m√°s extensa en ingl√©s)

Fue Leonhard Euler quien ideó los grafos como una manera muy potente y elegante de resolver el problema de los puentes de Königsberg. 

K√∂nigsberg (hoy Kaliningrado en Rusia) era en tiempos de Euler (siglo XVIII) una ciudad prusiana cruzada por siete puentes. Durante la √©poca se suscit√≥ la cuesti√≥n no resuelta de si era posible recorrer toda la ciudad cruzando cada uno de los puentes una y s√≥lo una vez. Si hacemos una representaci√≥n esquem√°tica de la ciudad vemos que los puentes unen cuatro porciones de tierra. La b√ļsqueda por prueba y error no conduce a ning√ļn resultado.¬†

Konigsberg.gif (13261 bytes) KonigsGraph.gif (6624 bytes)
El problema de los puentes de K√∂nigsberg. ¬†Esta ciudad esta recorrida por el r√≠o Pregel que crea dos islas. ¬ŅSe puede recorrer toda la ciudad pasando una sola vez por todos y cada uno de los 7 puentes que unen la parte insular de la ciudad con el resto?
Fuente: gr√°fico por el autor.
La solución de Euler. El famoso matemático abstrajo los detalles de la forma de la ciudad y sus puentes para quedarse con la conectividad, dando lugar a una de los primeros grafos. El orden de todos los vértices es impar, lo que implica que es imposible recorrerlos pasando una sola vez por cada uno.
Fuente:
gr√°fico por el autor.

Euler realizó una abstracción del problema representando mediante puntos las cuatro porciones de terreno y dibujando un arco entre cada dos puntos por cada puente. Llamó orden de cada vértice al numero de arcos que se reunían en el y se percató que el orden de cada vértice visitado en un recorrido sin saltos ha de ser par (sale un enlace y entra otro) excepto para dos puntos del grafo: aquellos donde se inicia y donde se acaba el recorrido, que han de tener orden impar. Si el vértice donde se inicia y se acaba son el mismo entonces todos los vértices han de ser de orden par.

En el problema de Königsberg el orden de todos los nodos es 3, esto es impar, por lo que quedó claro que no existía solución para el problema. No había un camino que recorriese todos los puentes pasando una sola vez por cada uno de ellos.

El interés de este ejemplo es que además de dar lugar a una teoría matemática muy potente los grafos se dibujan y resultan muy intuitivos, especialmente cuando los vértices son pocos. Ejemplos de grafos que todos conocemos son los organigramas que explicitan la estructura formal de la empresa, los árboles genealógicos o la circuitería de los chips electrónicos. Se usan regularmente para resolver problemas en la eficiencia del transporte, en sociología, electrónica y electricidad, detección de fraude y en general en aquellos campos en los que la conectividad es importante.

De hecho vivimos en una sociedad interconectada en la que, por definición, las redes (que son simplemente una forma de grafos dirigidos en los que cada arco tiene un valor) forman cada vez más parte de nuestra experiencia diaria. Internet es el arquetipo de la red y su conectividad nos perfunde a todos.

Como anécdota, al parecer la captura de Saddam Hussein se realizó en parte gracias a la labor de construcción del grafo de su red de soporte, basada en las relaciones funcionales de Saddam con miembros de su partido pero sobre todo de las relaciones tribales y familiares que le unen a su ciudad natal de Tikrit. Véase por ejemplo "Learning to break the rules" por Bruce Berkowitz o "How Army Sleuths Stalked the Adiviser who led to Hussein" por Eric Schmitt ambos para el New York Times (debo la información a Jim Wise)

No es fácil representar apropiadamente un grafo. De hecho no es fácil representar bien prácticamente cualquier cosa que tenga utilidad. Sin embargo el estudio de las grandes posibilidades que ofrece la representación automática de grafos ha dado lugar a una serie de reglas que vale la pena citar aquí. 

Seg√ļn Kozo Sugiyama en su libro ‚ÄúGraph Drawing and Applications‚ÄĚ* las reglas est√°ticas (que sirven para dibujar un solo grafo y no una sucesi√≥n de ellos de forma din√°mica) se dividen en¬†

  • Reglas b√°sicas: se refieren a aspectos elementales como el solapamiento entre aristas vertices o ambos.
Reglas B√°sicas
KO OK KO OK KO OK
No solapar vértices No solapar aristas  No solapar vértices con aristas
  • Reglas sem√°nticas: son reglas de posicionamiento de v√©rtices y de dibujo de arcos o aristas (enrutado) derivadas del significado de v√©rtices y aristas. Por ejemplo dibujar el tama√Īo de un v√©rtice o el grosor de una arista en funci√≥n de su importancia. Suelen venir dadas por el usuario o son deducidas de la informaci√≥n de sus etiquetas asociadas.
Reglas Sem√°nticas
Alinear v√©rtices espec√≠ficos Disponer v√©rtices espec√≠ficos en curva Dibujar v√©rtices espec√≠ficos con distinto tama√Īo
Emplazar vértices específicos en la frontera Agrupar vértices específicos Centrar vértices específicos
  • Reglas estructurales: son reglas de posicionamiento y enrutado relacionadas s√≥lo con las propiedades de la teor√≠a de grafos. Por ejemplo colocar los v√©rtices de mayor orden en el centro del dibujo o minimizar la longitud total de aristas, minimizar el numero de cruces entre v√©rtices, etc.
Reglas estructurales
KO OK OK KO                     OK KO OK
Centrar los vértices con orden alto Colocar los grafos isomorfos 
(igual forma) de idéntica manera.
Emplazar en forma jer√°rquica
KO OK KO OK KO OK
Minimizar los cruces de aristas Buscar equilibrio en las dimensiones del dibujo Organizar simétricamente
KO OK KO OK KO OK
Minimizar las esquinas en aristas Dibujar caras como polígons convexos Colocar los hijos simétricamente
KO OK KO OK KO OK
Evitar cruces de ramas diferentes Emplazamiento uniforme Minimizar el √°rea de dibujo
KO OK KO OK KO OK
Minimizar la longitud total de aristas Minimizar la diferencia de tama√Īo de los v√©rtices Minimizar la longitud media de las aristas
Todos los dibujos realizados por el autor, inspirados en los presentes en el libro de Sugiyama

Estas reglas persiguen la optimizaci√≥n del dibujo y pretenden facilitar la representaci√≥n de la forma m√°s sencilla y clara posible. Que ello no es f√°cil dan cuenta los avances que cada a√Īo se muestran en las conferencias sobre representaci√≥n de grafos (la de este a√Īo¬† se har√° en New York en Septiembre).


‚ÄúGraph Drawing and Applications‚ÄĚ by Kozo Sugiyama, World Scientific Series on Software Engineering and Knowledge Engineering Vol 11.¬†¬†

Enlaces de este artŪculo:

http://www.tmb.net/cast/metro/metro_planol.jsp   Mapa de la red de metro de Barcelona
http://www.utm.edu/departments/math/graph/glossary.html   Glosario de teor√≠a de grafos de Chris Caldwell
http://es.wikipedia.org/wiki/Teor√≠a_de_grafos   Entrada sobre grafos en espa√Īol de la Wikipedia
http://en2.wikipedia.org/wiki/Graph_theory   Entrada sobre grafos en ingl√©s de la Wikipedia (m√°s extenso)
http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Euler.html   Biograf√≠a de Leonhard Euler
http://www.rand.org/commentary/121903NYT.html   "Learning to break the rules" por Bruce Berkowitz
http://209.157.64.200/focus/f-news/1043834/posts   "How Army Sleuths Stalked the Adiviser who led to Hussein" por Eric Schmitt
http://www.gd2004.org/   Conferencia Graph Drawing 2004
http://www.wspc.com/books/compsci/4902.html   El libro "Graph Drawing and Applications" por Kozo Sugiyama
© Copyright InfoVis.net 2000-2018