Graph - Grafos (listas)

graphs - Grafos

Representaciones por Listados

  Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo. , 27 Febrero 2013

 

 

 

 

Descripción

Listado de Adyacencias: Otra forma de representar a los grafos es mediante listas en las que cada lista se corresponde con un “registro” descriptivo del nodo, donde aparecen los vecinos directos de cada nodo y todo aquello que permita un mejor aprovechamiento del grafo. Por ejemplo en un grafo semántico en cada línea podrían aparecer además de un nombre y/o nombres alternativos del nodo, conceptos asociados a la temática particular del nodo. La adyacencia en el ejemplo de la figura se refiere a los “arcos” que “van a” los nodos adyacentes: así el nodo 1 va a sí mismo y a los otros tres mientras que el tres va a uno solo. Estas listas pueden estar desordenadas.   

Listado de Incidencias: es una forma a primera vista redundante en la que se listan vértices por un lado y arcos por otro, los vértices acompañados por sus arcos incidentes y recíprocamente los arcos por sus vértices incidentes. Esta estructura permite la representación de estructuras semánticamente complejas en cuanto a sus contenidos asociados tanto a vértices como a arcos. 

  

En la figura se muestra un listado de incidencias para el ejemplo anterior en el que se aprecia una aparente redundancia respecto a las abstracciones matriciales booleanas y derivadas. Lo que ocurre es que en la realidad representada aplicada a redes semánticas los arcos de (a) a ( i) representan relaciones tales como “es hijo de…”, “genera el proceso….”, “tiene el mismo color que….”, etc., es decir tienen “nombre” y propiedades, Algo similar ocurre con los vértices que suelen tener además nombre y código. Por ello en el listado de vértices se muestran los arcos “salientes” indicando un camino lógico “que va por”: por ejemplo el nodo 1 va por los arcos a, b, c y d a sus nodos vecinos. Compruébese que con cualquiera de los dos listados, el de nodos y el de arcos se puede reconstruir perfectamente la estructura lógica del grafo. Compruébese también lo simple que es eliminar un arco, por ejemplo el arco {d: [1, 4]} borrándolo de la lista de pares y borrando el nombre de uno de los arcos salientes del nodo 1.

Advertencia: Cada una de las formas de representación que hemos visto hasta aquí presenta pros y cons en cuanto a espacio y tiempo de proceso de cómputos, a la complejidad de los algoritmos que las manejan y a la estabilidad de sus soluciones. Tengamos en cuenta que la redes que aparecen hoy en la Web son de miles a centenares de miles de nodos y de millones de arcos y que espacios y tiempos están relacionados al cuadrado de la cantidad de vértices o al producto entre la cantidad de vértices y la cantidad de arcos.

 

Metadata

ES: [listas de incidencias,listas de adyacencias,redes semánticas,vértices, nodo,nodos, arco,arcos,arista,aristas,arcos,matrices versus listas]

EN: [incidence lists,adjacency lists,semantic networks,node,nodes,arc,edges,arcs,edges,matrices versus lists]

Additional information