Grafe (tipo de datos abstracto)

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En informática, un grafo es un tipo de datos abstracto que está destinado a implementar los conceptos de gráfico no dirigido y gráfico dirigido del campo de la teoría de gráficos dentro de las matemáticas.

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

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

Operaciones

Las operaciones básicas proporcionadas por una estructura de datos gráfica G generalmente incluyen:

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

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

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

Estructuras de datos comunes para la representación gráfica

lista de adyacenciaLos vértices se almacenan como registros u objetos, y cada vértice almacena una lista de vértices adyacentes. Esta estructura de datos permite el almacenamiento de datos adicionales en los vértices. Se pueden almacenar datos adicionales si los bordes también se almacenan como objetos, en cuyo caso cada vértice almacena sus bordes incidentes y cada borde almacena sus vértices incidentes.Matriz de adyacenciaUna matriz bidimensional, en la que las filas representan los vértices de origen y las columnas representan 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 incidenciaUna matriz bidimensional, en la que las filas representan los vértices y las columnas representan los bordes. Las entradas indican la relación de incidencia entre el vértice de una fila y el borde de una columna.

La siguiente tabla da el costo de complejidad de tiempo de realizar varias operaciones en gráficos, para cada una de estas representaciones, con | V | el número de vértices y | mi | el número de aristas. En las representaciones matriciales, las entradas codifican el costo de seguir un borde. Se supone que el costo de los bordes que no están presentes es ∞.

	lista de adyacencia	Matriz de adyacencia	Matriz de incidencia
Guardar gráfico	$O(\|V\|+\|E\|)$	$O(\|V\|^{2})$	$O(\|V\|cdot \|E\|)$
Agregar vértice	$O(1)$	$O(\|V\|^{2})$	$O(\|V\|cdot \|E\|)$
Agregar borde	$O(1)$	$O(1)$	$O(\|V\|cdot \|E\|)$
Eliminar vértice	$O(\|E\|)$	$O(\|V\|^{2})$	$O(\|V\|cdot \|E\|)$
Quitar borde	$O(\|V\|)$	$O(1)$	$O(\|V\|cdot \|E\|)$
¿Los vértices x e y son adyacentes (suponiendo que se conocen sus posiciones de almacenamiento)?	$O(\|V\|)$	$O(1)$	$O(\|E\|)$
Observaciones	Lento para eliminar vértices y aristas, porque necesita encontrar todos los vértices o aristas	Lento para agregar o eliminar vértices, porque la matriz debe cambiarse de tamaño/copiarse	Lento para agregar o eliminar vértices y bordes, porque la matriz debe cambiarse de tamaño/copiarse

Las listas de adyacencia generalmente se prefieren para la representación de gráficos dispersos, mientras que se prefiere una matriz de adyacencia si el gráfico es denso; es decir, el número de aristas | mi | está cerca del número de vértices al cuadrado, | V |, o si uno debe poder mirar hacia arriba rápidamente si hay un borde que conecta dos vértices.

Representaciones paralelas

La paralelización de problemas de grafos enfrenta desafíos significativos: Cálculos basados en datos, problemas no estructurados, mala localidad y alta proporción de acceso a datos y cómputo. La representación gráfica utilizada para arquitecturas paralelas juega un papel importante para enfrentar esos 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 las 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, 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 dividir el conjunto $V$ de vértices del gráfico en $pags$ conjuntos ${displaystyle V_{0},puntos,V_{p-1}}$ . Aquí, $pags$ está la cantidad de elementos de procesamiento disponibles (PE). Las particiones del conjunto de vértices se distribuyen luego a los PE con índice coincidente, además de los bordes correspondientes. Cada PE tiene su propia representación de subgrafo, donde los bordes con un punto final en otra partición requieren atención especial. Para las interfaces de comunicación estándar como MPI, la ID del PE propietario del otro punto final debe ser identificable. Durante el cálculo en algoritmos de gráficos distribuidos, pasar información a lo largo de estos bordes implica comunicación.

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

Particionamiento 1D: cada procesador obtiene $notario público$ vértices y los bordes salientes correspondientes. Esto puede entenderse como una descomposición por filas o por columnas de la matriz de adyacencia. Para los algoritmos que operan en esta representación, esto requiere un paso de comunicación de todos a todos, así como ${mathcal {O}}(m)$ tamaños de búfer de mensajes, ya que cada PE tiene potencialmente bordes de salida a todos los demás PE.

Particionamiento 2D: cada procesador obtiene una submatriz de la matriz de adyacencia. Suponga que los procesadores están alineados en un rectángulo ${displaystyle p=p_{r}veces p_{c}}$ , donde ${displaystyle p_{r}}$ y ${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 ${ estilo de visualización (n/p_{r})times (n/p_{c})}$ . Esto se puede visualizar como un patrón de tablero de ajedrez en una matriz. Por lo tanto, cada unidad de procesamiento solo puede tener bordes salientes a los PE en la misma fila y columna. Esto limita la cantidad de socios de comunicación para cada PE de ${displaystyle p_{r}+p_{c}-1}$ entre ${displaystyle p=p_{r}veces p_{c}}$ los posibles.

Representaciones comprimidas

Los gráficos con billones de bordes ocurren en el aprendizaje automático, el análisis de redes sociales y otras áreas. Se han desarrollado representaciones gráficas comprimidas para reducir los requisitos de E/S y memoria. Son aplicables técnicas generales como la codificación de Huffman, pero la lista de adyacencia o la matriz de adyacencia se pueden procesar de formas específicas para aumentar la eficiencia.

Contenido relacionado

Más resultados...