Algoritmo para calcular G^2 y búsqueda en profundidad

T#4: 1. 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 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 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). // Para la representación de la matriz de adyacencia: Sea A quien 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 A² en O(V^lg7)).

Un ejemplo de este algoritmo es:

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. Para resolver este problema, se utiliza una variante de búsqueda en profundidad (DFS). Cada arista se marca la primera y la segunda vez que se recorre con marcas únicas para cada recorrido. Y 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 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 backtraking. 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) (v,u) a la ruta. De esta forma, cada arista se agrega al camino exactamente 2 veces.

T#4: 3. La conectividad implica alcanzar un vértice desde cualquier otro vértice en el gráfico, con esta idea se puede seguir al siguiente, es decir, 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 los está. Obteniéndose O(|V|(|V|+|E|)). Es importante mencionar que le 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.