Hispanopedia Wiki
Articulo de referencia

Grafo (tipo de dato abstracto)

Un grafo dirigido con tres vértices (círculos azules) y tres aristas (flechas negras). En informática , un grafo es un tipo de dato abstracto que tiene como objetivo implementar...

Hispanopedia WikiContenido en espanolLectura gratuita
Un grafo dirigido con tres vértices (círculos azules) y tres aristas (flechas negras).

En informática , un grafo es un tipo de dato abstracto que tiene como objetivo implementar los conceptos de grafo no dirigido y grafo dirigido del campo de la teoría de grafos dentro de las matemáticas .

Una estructura de datos de grafo consta de un conjunto finito (y posiblemente mutable) de vértices (también llamados nodos o puntos ), junto con un conjunto de pares no ordenados de estos vértices para un grafo no dirigido o un conjunto de pares ordenados para un grafo dirigido. Estos pares se conocen como aristas (también llamadas enlaces o líneas ), y para un grafo dirigido también se conocen como aristas , pero a veces también como flechas o arcos . Los vértices pueden formar parte de la estructura del grafo o pueden ser entidades externas representadas por índices enteros o referencias .

Una estructura de datos de grafo también puede asociar a cada arista algún valor , como una etiqueta simbólica o un atributo numérico (coste, capacidad, longitud, etc.).

Operaciones

Diagrama de clases UML de un grafo (tipo de dato abstracto)
Diagrama de clases UML de un grafo (tipo de dato abstracto)

Las operaciones básicas proporcionadas por una estructura de datos de grafo G generalmente incluyen: [ 1 ]

  • adyacente( G , x , y ) : comprueba si existe una arista desde el vértice x al vértice y ;
  • vecinos( G , x ) : enumera todos los vértices y tales que hay una arista desde el vértice x al vértice y ;
  • add_vertex( G , x ) : agrega el vértice x , si no está presente;
  • remove_vertex( G , x ) : elimina el vértice x , si existe;
  • add_edge( G , x , y , z ) : agrega la arista z del vértice x al vértice y , si no está allí;
  • remove_edge( G , x , y ) : elimina la arista del vértice x al vértice y , si existe;
  • get_vertex_value( G , x ) : devuelve el valor asociado al vértice x ;
  • set_vertex_value( G , x , v ) : establece el valor asociado al vértice x a v .

Las estructuras que asocian valores a los bordes también suelen proporcionar: [ 1 ]

  • get_edge_value( G , x , y ) : devuelve el valor asociado con la arista ( x , y );
  • set_edge_value( G , x , y , v ) : establece el valor asociado con la arista ( x , y ) a v .

Estructuras de datos comunes para la representación de grafos

Lista de adyacencia [ 2 ]
Los vértices se almacenan como registros u objetos, y cada vértice almacena una lista de vértices adyacentes. Esta estructura de datos permite almacenar información adicional sobre los vértices. Se puede almacenar información adicional si las aristas también se almacenan como objetos; en ese caso, cada vértice almacena sus aristas incidentes y cada arista almacena sus vértices incidentes.
Matriz de adyacencia [ 3 ]
Una matriz bidimensional, donde las filas representan los vértices de origen y las columnas los vértices de destino. Los datos sobre aristas y vértices deben almacenarse externamente. Solo se puede almacenar el costo de una arista entre cada par de vértices.
Matriz de incidencia [ 4 ]
Una matriz bidimensional, donde las filas representan los vértices y las columnas las aristas. Las entradas indican la relación de incidencia entre el vértice de una fila y la arista de una columna.

La siguiente tabla muestra la complejidad temporal de realizar diversas operaciones en grafos, para cada una de estas representaciones, donde | V | es el número de vértices y | E | el número de aristas. En las representaciones matriciales, las entradas codifican el coste de seguir una arista. Se supone que el coste de las aristas que no están presentes es infinito.

Las listas de adyacencia se prefieren generalmente para la representación de grafos dispersos , mientras que una matriz de adyacencia se prefiere si el grafo es denso; es decir, el número de aristas.|mi|{\displaystyle |E|}es cercano al número de vértices al cuadrado,|V|2{\displaystyle |V|^{2}}, o si uno debe poder comprobar rápidamente si existe una arista que conecta dos vértices. [ 5 ] [ 6 ]

Representación más eficiente de conjuntos de adyacencia

La complejidad temporal de las operaciones en la representación de lista de adyacencia se puede mejorar almacenando los conjuntos de vértices adyacentes en estructuras de datos más eficientes, como tablas hash o árboles de búsqueda binaria balanceados (esta última representación requiere que los vértices se identifiquen mediante elementos de un conjunto ordenado linealmente, como enteros o cadenas de caracteres). Una representación de vértices adyacentes mediante tablas hash conduce a una complejidad temporal promedio amortizada deO(1){\displaystyle O(1)}para probar la adyacencia de dos vértices dados y eliminar una arista y una complejidad temporal promedio amortizada [ 7 ] deO(grados⁡(incógnita)){\displaystyle O(\deg(x))}eliminar un vértice x dado de gradogrados⁡(incógnita){\displaystyle \deg(x)}La complejidad temporal de las demás operaciones y el requisito de espacio asintótico no cambian.

Representaciones paralelas

La paralelización de problemas de grafos enfrenta desafíos significativos: cálculos basados ​​en datos, problemas no estructurados, localidad deficiente y alta relación de acceso a datos respecto al cálculo. [ 8 ] [ 9 ] La representación de grafos utilizada para arquitecturas paralelas juega un papel importante para afrontar estos desafíos. Las representaciones mal elegidas pueden aumentar innecesariamente el costo de comunicación del algoritmo, lo que disminuirá su escalabilidad . A continuación, se consideran arquitecturas de memoria compartida y distribuida.

Memoria compartida

En el caso de un modelo de memoria compartida , las representaciones gráficas utilizadas para el procesamiento paralelo son las mismas que en el caso secuencial, [ 10 ] ya que el acceso paralelo de solo lectura a la representación gráfica (por ejemplo, una lista de adyacencia ) es eficiente en la memoria compartida.

Memoria distribuida

En el modelo de memoria distribuida , el enfoque habitual es particionar el conjunto de vértices.V{\displaystyle V}del gráfico enpag{\displaystyle p}conjuntosV0,…,Vpag−1{\displaystyle V_{0},\dots ,V_{p-1}}. Aquí,pag{\displaystyle p}es la cantidad de elementos de procesamiento (PE) disponibles. Las particiones del conjunto de vértices se distribuyen a los PE con índice coincidente, además de a las aristas correspondientes. Cada PE tiene su propia representación de subgrafo , donde las aristas con un extremo en otra partición requieren atención especial. Para interfaces de comunicación estándar como MPI , el ID del PE que posee el otro extremo debe ser identificable. Durante el cálculo en algoritmos de grafos distribuidos, el paso de información a través de estas aristas implica comunicación. [ 10 ]

La partición del grafo debe hacerse con cuidado: existe un compromiso entre la baja comunicación y la partición de tamaño uniforme [ 11 ]. Pero la partición de un grafo es un problema NP-difícil, por lo que no es factible calcularlas. En su lugar, se utilizan las siguientes heurísticas.

Particionamiento 1D: Cada procesador obtienenorte/pag{\displaystyle n/p}vértices y las aristas salientes correspondientes. Esto puede entenderse como una descomposición por filas o por columnas de la matriz de adyacencia. Para los algoritmos que operan sobre esta representación, esto requiere un paso de comunicación de todos a todos, así comoO(metro){\displaystyle {\mathcal {O}}(m)}tamaños de búfer de mensajes, ya que cada PE potencialmente tiene aristas salientes a todos los demás PE. [ 12 ]

Particionamiento 2D: Cada procesador recibe una submatriz de la matriz de adyacencia. Supongamos que los procesadores están alineados en un rectángulo.pag=pagr×pagdo{\displaystyle p=p_{r}\times p_{c}}, dóndepagr{\displaystyle p_{r}}ypagdo{\displaystyle p_{c}}son la cantidad de elementos de procesamiento en cada fila y columna, respectivamente. Luego, cada procesador obtiene una submatriz de la matriz de adyacencia de dimensión(norte/pagr)×(norte/pagdo){\displaystyle (n/p_{r})\times (n/p_{c})}Esto se puede visualizar como un patrón de tablero de ajedrez en una matriz. [ 12 ] Por lo tanto, cada unidad de procesamiento solo puede tener aristas salientes hacia PE en la misma fila y columna. Esto limita la cantidad de socios de comunicación para cada PE apagr+pagdo−1{\displaystyle p_{r}+p_{c}-1}fuera depag=pagr×pagdo{\displaystyle p=p_{r}\times p_{c}}posibles.

Representaciones comprimidas

Los grafos con billones de aristas aparecen en el aprendizaje automático , el análisis de redes sociales y otras áreas. Se han desarrollado representaciones de grafos comprimidas para reducir los requisitos de E/S y memoria. Se pueden aplicar técnicas generales como la codificación de Huffman , pero la lista de adyacencia o la matriz de adyacencia se pueden procesar de maneras específicas para aumentar la eficiencia. [ 13 ]

Aplicaciones de los gráficos

La búsqueda en amplitud (BFS) y la búsqueda en profundidad (DFS) son dos enfoques estrechamente relacionados que se utilizan para explorar todos los nodos de un componente conectado dado . Ambos comienzan con un nodo arbitrario, la " raíz ". [ 14 ] Los componentes fuertemente conectados también se pueden encontrar mediante recorridos de grafos utilizando algoritmos como el algoritmo de Kosaraju , que es una DFS modificada.

Búsqueda de rutas

El algoritmo de Dijkstra es un algoritmo de búsqueda de rutas que se puede utilizar en grafos con pesos positivos (es decir, donde el peso de todas las aristas debe ser mayor o igual a cero) y/o grafos dirigidos. Se puede usar para encontrar la ruta más corta entre dos nodos elegidos arbitrariamente, lo cual se aplica comúnmente en problemas de enrutamiento.

Véase también

Referencias

  1. 1 2 Véase, por ejemplo, Goodrich y Tamassia (2015) , Sección 13.1.2: Operaciones con grafos, pág. 360. Para un conjunto de operaciones más detallado, véase Mehlhorn, K.; Näher, S. (1999). «Capítulo 6: Grafos y sus estructuras de datos». LEDA: Una plataforma para computación combinatoria y geométrica (PDF) . Cambridge University Press. págs. 240–282 . 
  2. ^ Cormen et al. (2001) , págs. 528–529; Goodrich y Tamassia (2015) , págs. 361-362.
  3. ^ Cormen et al. (2001) , págs. 529–530; Goodrich y Tamassia (2015) , pág. 363.
  4. ↑ Cormen et al. (2001) , Ejercicio 22.1-7, pág. 531.
  5. ↑ Cormen, Thomas H.; Leiserson , Charles E.; Rivest , Ronald L .; Stein, Clifford (2001). «Sección 22.1: Representaciones de grafos». Introducción a los algoritmos (Segunda edición). MIT Press y McGraw-Hill. págs. 527–531 . ISBN   0-262-03293-7.
  6. ↑ Goodrich, Michael T .; Tamassia, Roberto (2015). «Sección 13.1: Terminología y representaciones de grafos». Diseño y aplicaciones de algoritmos . Wiley. págs. 355–364 . ISBN  978-1-118-33591-8.
  7. ↑ Cormen, Thomas H.; Leiserson , Charles E.; Rivest , Ronald L .; Stein, Clifford (2009). Introducción a los algoritmos (3.ª ed.). Instituto Tecnológico de Massachusetts. págs. 253–280 . ISBN   978-0-262-03384-8.
  8. ↑ Bader, David; Meyerhenke, Henning; Sanders, Peter; Wagner, Dorothea (enero de 2013). Particionamiento y agrupamiento de grafos . Matemáticas contemporáneas. Vol. 588. Sociedad Matemática Americana. doi : 10.1090/conm/588/11709 . ISBN  978-0-8218-9038-7.
  9. ↑ Lumsdaine, Andrew; Gregor, Douglas; Hendrickson, Bruce; Berry, Jonathan (marzo de 2007). "Desafíos en el procesamiento paralelo de grafos". Parallel Processing Letters . 17 (1): 5– 20. doi : 10.1142/s0129626407002843 . ISSN 0129-6264 . 
  10. 1 2 Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Algoritmos y estructuras de datos secuenciales y paralelos: La caja de herramientas básica . Springer International Publishing. ISBN 978-3-030-25208-3.
  11. ↑ "Procesamiento paralelo de grafos" (PDF) . Archivado del original (PDF) el 25 de agosto de 2021. Consultado el 9 de marzo de 2020 .
  12. 1 2 Buluç, A.; Madduri, Kamesh (2011). "Aplicaciones". Búsqueda paralela en amplitud en sistemas de memoria distribuida . Conferencia Internacional de 2011 sobre Computación de Alto Rendimiento, Redes, Almacenamiento y Análisis. CiteSeerX 10.1.1.767.5248 . doi : 10.1145/2063384.2063471 . ISBN  978-1-4503-0771-0. S2CID 6540738 . 
  13. ↑ Besta, Maciej; Hoefler, Torsten (27 de abril de 2019). "Estudio y taxonomía de la compresión de grafos sin pérdidas y representaciones de grafos eficientes en espacio". arXiv : 1806.01799 [ cs.DS ].
  14. ↑ Purti (julio-septiembre de 2018). "Recorridos de grafos y sus aplicaciones" (PDF) . Revista internacional de investigación y análisis . 5 (3): 2.
  • Biblioteca gráfica Boost: una potente biblioteca gráfica de C++ de Boost (bibliotecas de C++)
  • Networkx: una biblioteca gráfica de Python
  • GraphMatcher es un programa Java para alinear grafos dirigidos y no dirigidos.
  • GraphBLAS: Especificación para una interfaz de biblioteca para operaciones en grafos, con especial atención a los grafos dispersos.