Conjunto de adyacencia:Representación de relaciones de gráficos
An Conjunto de adyacencia es una forma de representar la estructura de un gráfico. Para cada vértice (nodo) en el gráfico, el conjunto de adyacencia contiene todos los vértices a los que está conectado directamente (sus vecinos). En otras palabras, es un conjunto que contiene todos los vértices adyacentes a un vértice dado.
Definición formal:
Para un gráfico g =(v, e), donde v es el conjunto de vértices y e es el conjunto de bordes, el conjunto de adyacencia de un vértice * v * ∈ V, denotado como adj (v), se define como:
Adj (v) ={u ∈ V | (v, u) ∈ E}
Ejemplo:
Considere un gráfico simple no dirigido con los vértices A, B, C y D, y los bordes:
* (A, B)
* (A, C)
* (B, C)
* (CD)
Los conjuntos de adyacencia para cada vértice serían:
* Adj (a) ={b, c}
* Adj (b) ={a, c}
* Adj (c) ={a, b, d}
* Adj (d) ={c}
Lista de adyacencia vs. adyacencia:
Si bien es similar en concepto, es crucial diferenciar un conjunto de adyacencia de una lista de adyacencia.
* Conjunto de adyacencia: Utiliza un set Estructura de datos para cada vértice, que implica ningún orden entre los vecinos y garantizar que cada vecino aparezca solo una vez. Esto es ideal cuando el pedido no es importante y desea pruebas de membresía eficientes (por ejemplo, verificar si el vértice 'x' es un vecino de 'y'). No puede almacenar múltiples bordes entre los mismos dos vértices (multigráfico).
* Lista de adyacencia: Utiliza una lista Estructura de datos para cada vértice, lo que permite ordenar a los vecinos y potencialmente aparecen varias veces (representando múltiples bordes entre los mismos vértices). Es más flexible, pero puede no ser tan eficiente para las pruebas de membresía si necesita evitar duplicados.
Ventajas del uso de conjuntos de adyacencia:
* Prueba de membresía eficiente: Comprobación de si un vértice * u * es un vecino de Vértice * V * (es decir, si * u * ∈ ADJ (v)) es típicamente o (1) en promedio usando una implementación de hash establecido.
* Representación simple: Fácil de entender e implementar.
* Sin bordes duplicados: Por definición, un conjunto no puede contener elementos duplicados.
Desventajas del uso de conjuntos de adyacencia:
* Orden no conservado: El orden en el que se almacenan los vecinos no está garantizado.
* Complejidad espacial: Puede usar más espacio que representaciones alternativas como matrices de adyacencia, especialmente para gráficos dispersos. En el peor de los casos (gráfico completo), la complejidad del espacio es O (| V | * | V |).
* No es adecuado para multigraphs: No se puede representar múltiples bordes entre los mismos dos vértices.
Relación con la conectividad de red
Los conjuntos de adyacencia juegan un papel importante en la determinación de la conectividad de la red porque definen explícitamente las conexiones directas entre los vértices. Según estas conexiones, podemos inferir varias propiedades de conectividad:
1. Determinación de componentes conectados: Al atravesar el gráfico utilizando los conjuntos de adyacencia, podemos identificar componentes conectados. Un componente conectado es un subgrafio donde cada vértice es accesible desde cualquier otro vértice dentro de ese subgrafio. Los algoritmos como la búsqueda de profundidad primero (DFS) o la búsqueda de amplitud (BFS) se pueden implementar de manera eficiente utilizando conjuntos de adyacencia para explorar el gráfico e identificar estos componentes. Si un gráfico tiene solo un componente conectado, significa que el gráfico está conectado.
2. Calcular las rutas más cortas: Algoritmos como el algoritmo o BFS de Dijkstra se pueden usar con conjuntos de adyacencia para encontrar las rutas más cortas entre dos vértices. Estos algoritmos se basan en explorar los vecinos de un vértice (proporcionado por el conjunto de adyacencia) para descubrir las rutas.
3. Ciclos de detección: Los DF se pueden emplear con conjuntos de adyacencia para detectar ciclos en un gráfico. Al rastrear los vértices actualmente en la pila de recursión, podemos identificar los bordes posteriores, lo que indica la presencia de ciclos.
4. Comprobación de bipartitidad: Podemos usar conjuntos de adyacencia junto con algoritmos de coloración de gráficos (por ejemplo, usando DFS o BFS) para determinar si un gráfico es bipartito. Un gráfico bipartito es uno en el que los vértices se pueden dividir en dos conjuntos de disjunto de tal manera que cada borde conecta un vértice en un conjunto a un vértice en el otro conjunto.
5. Evaluación de robustez/resiliencia: Los conjuntos de adyacencia nos permiten analizar cómo la eliminación de ciertos vértices o bordes afecta la conectividad de la red. Podemos simular estas eliminaciones y luego volver a calcular los componentes conectados para ver si la red se fragmenta.
En resumen:
Los conjuntos de adyacencia proporcionan una forma fundamental de representar relaciones gráficas. Su eficiencia en las búsquedas vecinas los convierte en una herramienta valiosa para varios algoritmos gráficos que son cruciales para comprender y analizar la conectividad de la red. Nos permiten determinar si los vértices son accesibles entre sí, encontrar rutas entre los vértices, identificar componentes conectados y evaluar la conectividad general y la resiliencia de una red. Si bien tienen limitaciones con respecto a los multigraphs y el uso potencial del espacio, siguen siendo una representación poderosa y ampliamente utilizada para muchos problemas relacionados con los gráficos.