Algoritmos Avanzados de Grafos: Cálculo de G² y Técnicas de Búsqueda DFS

T#4: 1. Cálculo de G² mediante Listas y Matrices de Adyacencia

Para calcular G² a partir de la representación de la lista de adyacencia (Adj) de G, se realiza lo siguiente para cada Adj[u]:

• 1. for each vertex v in Adj[u]
• 2. for each vertex w in Adj[v]
• 3. edge(u,w) ∈ E²
• 4. Insert w in Adj2(u)

Donde Adj2 es la representación de la lista de adyacencia de G². Posteriormente, después de haber calculado Adj2, se tienen que eliminar las aristas duplicadas de las listas (puede haber más de una ruta de 2 aristas en G entre 2 vértices). Para cada arista en Adj se barren como máximo |V| vértices; se calcula Adj2 en un tiempo O(VE). La eliminación de aristas duplicadas se realiza en O(V+E). Por lo tanto, el tiempo de ejecución es: O(VE) + O(V+E) = O(VE).

Representación de la Matriz de Adyacencia

Para la representación de la matriz de adyacencia: sea A la que denota la representación de la matriz de adyacencia de G. La representación de la matriz de adyacencia de G² es el cuadrado de A. El cálculo de A² puede ser realizado en tiempo O(V³) (incluso más rápido, teóricamente, que el algoritmo de Strassen, que calcula A² en O(V^lg7)).

Ejemplo del algoritmo para matriz de adyacencia:

G² for an adjacency matrix

• for i=1 to V
• for j=1 to V {
• G²[i][j]=0;
• for k=1 to V
• if(g[i][k]==1 && g[k][j]==1){
• G²[i][j]=1;
• break;
• }
• }

T#4: 2. Recorrido de Aristas mediante Búsqueda en Profundidad (DFS)

Para resolver este problema, se utiliza una variante de la búsqueda en profundidad (DFS). Cada arista se marca la primera y la segunda vez que se recorre con marcas únicas para cada recorrido. Aquellas que se han recorrido dos veces no se pueden volver a tomar. El algoritmo de búsqueda en profundidad debe garantizar que se exploren todas las aristas y que cada una se tome en ambas direcciones.

Para garantizar que se exploran todas, el algoritmo debe asegurar que las aristas inexploradas siempre se toman antes de aquellas que se exploran una sola vez. Para cerciorarse de que las aristas se toman en cada dirección, simplemente retrocedemos cada vez que la búsqueda en profundidad llega a un callejón sin salida. La búsqueda sigue retrocediendo hasta que se encuentra una nueva arista explorada. De esta manera, solo se exploran en la dirección inversa durante el backtracking. La complejidad es O(V+E), ya que:

1. Primero hay que realizar una búsqueda en profundidad de G, comenzando en un vértice arbitrario (la ruta requerida por el problema puede obtenerse según el orden en que DFS explora las aristas en el gráfico).
2. Al explorar una arista (u,v) que va a un nodo no visitado, la arista (u,v) se incluye por primera vez en el camino o ruta.
3. Cuando DFS retrocede a u nuevamente después de que v se convierte en NEGRO, la arista (u,v) es incluida por segunda vez en el camino, esta vez en la dirección opuesta (de V a U).
4. Cuando DFS explora una arista (u,v) que va a un nodo visitado (GRIS o NEGRO), se agrega (u,v) y (v,u) a la ruta. De esta forma, cada arista se agrega al camino exactamente 2 veces.

T#4: 3. Verificación de Conectividad Individual

La conectividad implica alcanzar un vértice desde cualquier otro vértice en el gráfico. Con esta idea se puede proceder de la siguiente manera: para cada vértice u ∈ V, realizar un DFS en el gráfico dado G. Hay que comprobar si hay alguna arista por delante o aristas transversales (en la misma componente) en cualquiera de las búsquedas. Si no existen tales aristas, entonces el gráfico está conectado individualmente; de lo contrario, no lo está. El tiempo obtenido es O(|V|(|V|+|E|)).

Es importante mencionar que el gráfico está conectado de manera individual incluso con las aristas posteriores existentes. Las aristas posteriores implican que hay una ruta u → v y v → u, lo cual es consistente con la definición de conexión única.