algorithm - rectangulo - triangulo isosceles

¿Cómo encontrar un triángulo dentro de una gráfica?

Question

Aquí hay un ejercicio en el Manual de Diseño de Algoritmos .

Considere el problema de determinar si un gráfico no dirigido G = (V, E) contiene un triángulo o un ciclo de longitud 3.

(a) Da una O (| V | ^ 3) para encontrar un triángulo si existe.

(b) Mejore su algoritmo para ejecutarse en el tiempo O (| V | · | E |). Puedes asumir | V | ≤ | E |.

Observe que estos límites le dan tiempo para convertir entre la matriz de adyacencia y las representaciones de la lista de adyacencia de G.

Aquí están mis pensamientos:

(a) Si la gráfica se presenta como una lista de adyacencia, puedo convertir la lista a matriz mediante O (| V | ^ 2). Entonces lo hago:

for (int i = 0;i < n;i++) 
   for (int j = i+1;j < n;j++) 
   if (matrix[i][j] == 1) 
      for (int k = j+1;k < n;k++) 
         if (matrix[i][k] == 1 && matrix[j][k] == 1)
             return true;

Esto debería dar una O (| V | ^ 3) para probar el triángulo.

(b) Mi primer intuición es que si la gráfica se presenta como una lista de adyacencia, haré un bfs. Cuando se encuentra un borde cruzado, por ejemplo, if yx is a cross edge , check whether parent[y] == parent[x], if true, then a triangle is found .

¿Alguien podría decirme si mi pensamiento es correcto o no?

También por este (b), no estoy seguro de su complejidad. ¿Debería ser O (| V | + | E |), verdad?

¿Cómo puedo hacerlo en O (| V | * | E |)?

Answer 1

Esto es lo que pienso:

La solución BFS original es incorrecta como se señaló anteriormente. Pero podemos modificar el DFS. Asigne números a los nodos visitados a medida que visitamos cada vértice en el DFS. Ahora, si alcanzamos un vértice (en la pregunta que vi bordes cruzados, no hay ninguno en un gráfico no dirigido), verificamos su lista de adyacencia y suponemos que se descubre un vértice (pero no se procesa, no puede suceder), luego verificamos su número . Si la diferencia es 2, entonces hay un ciclo de longitud 3.

Answer 2

Realmente me gusta la solución de multiplicación de matrices que se analiza en esta publicación del blog .

Sea a = la matriz de adyacencia

• Las adyacencias en una matriz * a (a2) multiplicadas son los números de rutas de 2 longitudes
• Las adyacencias en a2 * una matriz multiplicada son los números de rutas de 3 longitudes

El problema es que la multiplicación de matrices es lenta ... Sin embargo, puede usar GPGPU para realizar la multiplicación de matrices y puede tener una solución de alto rendimiento en arquitecturas modernas que incluyen una GPU.

Answer 3

Si tiene una matriz de adyacencia, puede encontrar triángulos al cuadrar la matriz y ver si la matriz original y la matriz cuadrada tienen una entrada distinta de cero en el mismo lugar.

Una multiplicación de matrices ingenua toma tiempo O(n^3) , pero hay algoritmos de multiplicación de matrices rápidos que funcionan mejor. Uno de los más conocidos es el algoritmo Coppersmith-Winograd , que se ejecuta en tiempo O(n^2.4) . Eso significa que el algoritmo va algo así como:

• Use el tiempo O(V^2) para convertir a una matriz de adyacencia.
• Use el tiempo O(V^2.4) para calcular el cuadrado de la matriz de adyacencia.
• Use el tiempo O(V^2) para verificar en las matrices las entradas coincidentes que no sean cero.
• El índice de la fila y la columna donde encuentra las entradas que no coinciden con cero en (si las hay) le indica dos de los nodos involucrados.
• Use el tiempo O(V) para reducir el tercer nodo común a los dos nodos conocidos.

Entonces, en general, esto toma tiempo O(V^2.4) ; de manera más precisa, toma lo que lleve la multiplicación de matriz larga. Puede cambiar dinámicamente entre este algoritmo y el algoritmo if-any-edge-end-have-a-common-vecino que amit explica en su respuesta para mejorar eso a O(V min(V^1.4, E)) .

Aquí hay un documento que profundiza más en el problema .

Es un poco claro qué tan dependiente de los descubrimientos teóricos es este problema. Si las conjeturas acerca de la multiplicación de matrices que en realidad son cuadráticas resultan ser verdaderas, obtendríamos un límite de tiempo realmente agradable de O(V^2) u O(V^2 log(V)) o algo por el estilo. Pero si las computadoras cuánticas funcionan, podremos hacerlo incluso mejor que eso (algo como O(V^1.3) )!

Answer 4

Una posible solución O(|V||E|) , es la misma idea de la fuerza bruta en (a):

for each edge (u, v):
  for each vertex w:
     if (v, w) is an edge and (w, u) is an edge:
          return true
return false

compruebe todos los bordes y no todos los pares de vértices (con otro vértice que forme un triángulo) es suficiente información para determinar si el borde y el vértice forman una solución viable.

Ejemplo de contador a la solución BFS:

       A
     / | /
    /  |  /
   B   C   D
   |   |   |
   |   |   |
   F---G---H
   |       |
   ---------
    (F, H) is also an edge

Tenga en cuenta que el father[F] != father[G] != father[H] , por lo tanto, el algoritmo devolverá falso, pero, sin embargo, (F, G, H) es una solución factible.