matlab - titulo - Detectando ciclos en una matriz de adyacencia

plot matlab

Question

Sea A la matriz de adyacencia para el gráfico G = (V,E) . A(i,j) = 1 si los nodos i y j están conectados con un borde, A(i,j) = 0 caso contrario.

Mi objetivo es el de entender si G es acíclico o no. Un ciclo se define de la siguiente manera:

• i y j están conectados: A(i,j) = 1
• j y k están conectados: A(j,k) = 1
• k y i estamos conectados: A(k,i) = 1

Implementé una solución que navega por la matriz de la siguiente manera:

• Comience desde un borde (i,j)
• Seleccione el conjunto O de los bordes que son salientes de j , es decir, todos los 1 en la j -ésima fila de A
• Navegue O de una manera DFS
• Si una de las rutas generadas desde esta navegación conduce al nodo i , se detecta un ciclo

Obviamente, esta solución es muy lenta, ya que tengo que evaluar todas las rutas en la matriz. Si A es muy grande, la sobrecarga requerida es muy grande. Me preguntaba si hay una forma de navegar la matriz de adyacencia para encontrar ciclos sin usar un algoritmo costoso como DFS.

Me gustaría implementar mi solución en MATLAB.

Gracias por adelantado,

Eleanore.

Answer 1

Ese es el problema que también encontré. La explicación, pensé, es la siguiente:
cuando hablamos de ciclo, implícitamente nos referimos a ciclos dirigidos. La matriz de adyacencia que tiene tiene un significado diferente cuando se considera el gráfico dirigido; de hecho, es un ciclo dirigido de longitud 2. Entonces, la solución de $ A ^ n $ es en realidad para gráficos dirigidos. Para gráficos no dirigidos, supongo que una solución sería solo considerar la versión triangular superior de la matriz (el resto se llena con cero) y repetir el procedimiento. Avísame si esta es la respuesta correcta.

Answer 2

Este enfoque utiliza DFS, pero es muy eficiente, porque no repetimos los nodos en DFS posteriores.

Enfoque de alto nivel:

Inicialice los valores de todos los nodos a -1 .

Realice un DFS desde cada nodo no explorado, estableciendo el valor de ese nodo en el de un valor autoincrementado comenzando desde 0 .

Para estos DFS, actualice el valor de cada nodo con previous node''s value + i/n^k donde ese nodo es el i ésimo hijo del nodo anterior k es la profundidad explorada, omitiendo nodos ya explorados (excepto para verificar un valor mayor) .

Entonces, un ejemplo para n = 10 :

   0.1   0.11   0.111
   j   - k    - p
0 /    / 0.12
i / 0.2  l
    m

1   1.1
q - o
...

También puede usar i/branching factor+1 para cada nodo para reducir los dígitos significativos de los números, pero eso requiere cálculos adicionales para determinar.

Así que arriba hicimos un DFS de i , que tenía 2 hijos j y m . m no tenía hijos, j tenía 2 hijos, .... Luego terminamos con i y comenzamos otro DFS desde el siguiente nodo inexplorado q .

Cada vez que encuentre un valor mayor, sabrá que se produjo un ciclo.

Complejidad:

Revisa cada nodo como máximo una vez, y en cada nodo lo hace n comprueba, entonces la complejidad es O(n^2) , que es lo mismo que mirar cada entrada en la matriz una vez (que no puede hacer mucho mejor que )

Nota:

También notaré que una lista de adyacencia probablemente sea más rápida que una matriz de adyacencia a menos que sea un gráfico muy denso.

Answer 3

Si A es la matriz de adyacencia del gráfico dirigido o no dirigido G, entonces la matriz A^n (es decir, el producto matriz de n copias de A) tiene la propiedad siguiente: la entrada en la fila i y la columna j da el número de (dirigido o sin dirección) camina de longitud n desde el vértice i hasta el vértice j.

Por ejemplo, si para un entero n matriz A ^ n contiene al menos una entrada diagonal distinta de cero, entonces el gráfico tiene un ciclo de tamaño n.

La forma más fácil de verificar los elementos diagonales distintos de cero de la matriz es calcular la trace(A) = sum(diag(A)) matriz trace(A) = sum(diag(A)) (en nuestro caso, los elementos de la potencia de la matriz siempre serán no negativos).

La solución de Matlab puede ser siguiente:

for n=2:size(A,1)
   if trace(A^n) ~= 0
      fprintf(''Graph contain cycle of size %d'', n)
      break;
   end
end

Answer 4

Algunas ideas más sobre el enfoque matricial ... El ejemplo citado es la matriz de adyacencia para un gráfico desconectado (los nodos 1 y 2 están conectados, y los nodos 3 y 4 están conectados, pero ninguno de los pares está conectado al otro par). Cuando calcule A ^ 2, la respuesta (como se dijo) es la matriz de identidad. Sin embargo, dado que Trace (A ^ 2) = 4, esto indica que hay 2 bucles cada uno de longitud 2 (que es correcto). No se permite calcular A ^ 3 hasta que estos bucles se identifiquen correctamente y se eliminen de la matriz. Este es un procedimiento involucrado que requiere varios pasos y está muy bien explicado por RL Norman, "Un método de matriz para la ubicación de ciclos de un gráfico dirigido", AIChE J, 11-3 (1965) pp. 450-452. Tenga en cuenta: no está claro por parte del autor si se garantiza que este enfoque encuentre TODOS los ciclos, ciclos ÚNICOS y / o ciclos ELEMENTALES. Mi experiencia sugiere que definitivamente no identifica SOLO ciclos únicos.

Answer 5

Si el dígrafo G está representado por su matriz de adyacencia M entonces M ''= (I - M) será singular si hay un ciclo en él. I: matriz de identidad del mismo orden de M

Answer 6

Me encontré con esta pregunta al responder esta pregunta math.stackexchange . Para futuros lectores, siento que debo señalar (como ya lo han hecho otros) que la respuesta de Danil Asotsky es incorrecta y proporcionar un enfoque alternativo. El teorema al que se refiere Danil es que la entrada (i, j) de A ^ k cuenta el número de caminatas de longitud k de i a j en G. La clave aquí es que una caminata permite repetir vértices. Por lo tanto, incluso si las entradas diagonales de A ^ k son positivas, cada caminata que cuente la entrada puede contener vértices repetidos y, por lo tanto, no contaría como un ciclo.

Contraejemplo: una ruta de longitud 4 contendría un ciclo de 4 ciclos de acuerdo con la respuesta de Danil (sin mencionar que la respuesta implicaría P = NP porque resolvería el problema del ciclo de Hamilton).

De todos modos, aquí hay otro enfoque. Un gráfico es acíclico si y solo si es un bosque, es decir, tiene componentes c y exactamente nc bordes, donde n es el número de vértices. Afortunadamente, hay una manera de calcular el número de componentes utilizando la matriz L de Laplacian , que se obtiene reemplazando la entrada (i, i) de -A con la suma de entradas en la fila i de A (es decir, el grado de vértice etiquetado i). Entonces se sabe que el número de componentes de G es n-rank (L) (es decir, la multiplicidad de 0 como un autovalor de L).

Así que G tiene un ciclo si y solo si el número de aristas es al menos n- (n-rank (L)) + 1. Por otro lado, mediante el lema de handshaking, el número de bordes es exactamente la mitad del trazo (L). Asi que:

G es acíclico si y solo si 0.5 * trace (L) = rank (L). Equivalentemente, G tiene un ciclo si y solo si 0.5 * trace (L)> = rank (L) +1.

Answer 7

Basándose en la observación de Danil , necesita calcular A^n , una forma ligeramente más eficiente de hacerlo es

n = size(A,1);
An = A; 
for ii = 2:n
     An = An * A; % do not re-compute A^n from skratch
     if trace(An) ~= 0
        fprintf(1, ''got cycles/n'');
     end
end