Détection de cycles dans une matrice d'adjacence
Laisser A
être la matrice d'adjacence du graphe G = (V,E)
. A(i,j) = 1
si les nœuds i
et j
sont reliés par une arête, A(i,j) = 0
autrement.
Mon objectif est celui de savoir si la G
est acyclique ou pas. Un cycle est défini de la manière suivante:
i
etj
sont connectés:A(i,j) = 1
j
etk
sont connectés:A(j,k) = 1
k
eti
sont connectés:A(k,i) = 1
J'ai mis en œuvre une solution qui navigue dans la matrice comme suit:
- Démarrer à partir d'un bord
(i,j)
- Sélectionnez le jeu
O
de bords, qui sont les sortants dej
c'est à dire, toutes les 1s dans lej
-ième ligne deA
- Naviguer
O
dans un DFS de mode - Si l'un des chemins générés à partir de cette navigation mène vers le nœud
i
puis un cycle est détecté
Évidemment, cette solution est très lent, depuis que j'ai ont à évaluer tous les chemins d'accès dans la matrice. Si A
est très grand, les frais généraux est très grand. Je me demandais si il existe un moyen de naviguer sur la matrice de contiguïté, de manière à trouver des cycles sans l'aide d'un coûteux algorithme tel que DFS.
J'aimerais implémenter ma solution dans MATLAB.
Merci d'avance,
Eleanore.
source d'informationauteur Eleanore
Vous devez vous connecter pour publier un commentaire.
Basé sur l'observation de Danilvous devez calculer
A^n
un peu plus de moyen efficace de le faire estJe suis tombé sur cette question au moment de répondre à cette les mathématiques.stackexchange question. Pour les futurs lecteurs, j'ai l'impression que je dois faire remarquer (comme d'autres l'ont déjà fait) que Danil Asotsky la réponse est incorrecte, et de fournir une approche alternative. Le théorème de Danil est fait référence à la (i,j) de l'entrée d'Un^k compte le nombre de promenades de longueur k allant de i à j dans G. L'élément clé ici est qu'un pied est permis de répéter les sommets. Ainsi, même si une diagonale d'entrées d'Un^k est positif, chaque marche de l'entrée est de comptage peut contenir répété sommets, et donc ne compte pas comme un cycle.
Contre-exemple: Un chemin de longueur 4 contient un 4-cycle selon Danil de réponse (ne pas oublier que cette réponse implique P=NP, car il permettrait de résoudre le Hamilton cycle de problème).
De toute façon, ici, c'est une autre approche. Un graphe est acyclique si et seulement si c'est une forêt, c'est à dire, il a c composants et exactement n-c bords, où n est le nombre de sommets. Heureusement, il existe un moyen de calculer le nombre de composants à l'aide de la Laplacien de la matrice L, ce qui est obtenu en remplaçant le (i,i) l'entrée de la somme des entrées dans la ligne i de A (c'est à dire, le degré d'un sommet étiqueté i). Ensuite, il est connu que le nombre de composantes de G est n-rang(L) (c'est à dire, la multiplicité de 0 comme valeur propre de L).
Alors G a un cycle si et seulement si le nombre d'arêtes est au moins n-(n-rang(L))+1. D'autre part, par l'établissement de la liaison lemme, le nombre d'arêtes est exactement la moitié de la trace(L). Donc:
Si A est la matrice de contiguïté de la destinée ou non orienté, graphe G, alors la matrice
A^n
(c'est à dire, la matrice produit de n copies de A) a la propriété suivante: l'entrée dans la ligne i et la colonne j donne le nombre de (réalisé ou non orienté) les horizons de la longueur n du sommet i au sommet j.E. g. si, pour un entier n de la matrice A^n contient au moins un non-zéro diagonale d'entrée, que le graphe de cycle de taille n.
Plus de moyen facile de vérifier pour les non-zéro éléments de la diagonale de la matrice est de calculer la matrice
trace(A) = sum(diag(A))
(dans notre cas, les éléments de la matrice de puissance sera toujours négative).Matlab solution peuvent être les suivants:
Cette approche utilise DFS, mais est très efficace, parce que nous ne répétez pas les nœuds dans la suite DFS.
De haut niveau de l'approche:
Initialiser les valeurs de tous les noeuds
-1
.Faire un DFS de chaque inexploré nœud de paramètre valeur du nœud à celle d'une auto-incrémenté de la valeur à partir de
0
.Pour ces DFS, mise à jour de chaque nœud de la valeur avec
previous node's value + i/n^k
où ce nœud est lei
th enfant du nœud précédent etk
est la profondeur explorée, sautant déjà exploré les nœuds (sauf pour la vérification de la valeur plus grande).Comme un exemple pour
n = 10
:Vous pouvez également utiliser
i/branching factor+1
pour chaque nœud à réduire les chiffres significatifs des nombres, mais qui nécessite plus de calculs pour déterminer.Donc au-dessus de nous n'a un DFS de
i
qui avait 2 enfantsj
etm
.m
n'avait pas d'enfants,j
eu 2 enfants, .... Puis nous avons terminé aveci
et a commencé un autre DFS à partir de la prochaine inexploré nœudq
.Chaque fois que vous rencontrez une valeur plus grande, vous savez qu'un cycle s'est produite.
Complexité:
Vous de vérifier chaque nœud au plus une fois, et à chaque nœud n de vérifications, de sorte que la complexité est
O(n^2)
qui est la même que la recherche à chaque entrée dans la matrice une fois (que vous ne pouvez pas faire beaucoup mieux que).Remarque:
Je vais juste noter qu'un liste d'adjacence sera probablement plus rapide qu'une matrice de contiguïté, sauf si c'est un tissu très dense de graphique.
Qui est le problème, je trouve aussi. L'explication, je pense, est la suivante:
lorsque nous parlons de cycle, implicitement, nous entendons dirigé cycles. La matrice de contiguïté que vous avez a un tout autre sens lorsque l'on considère le graphe orienté; il est en effet réalisé un cycle de longueur 2. Donc, la solution de $A^n$ est en fait pour les graphes orientés. Pour les graphes non dirigés, je suppose qu'un correctif serait juste de considérer la partie supérieure triangulaire version de la matrice (le reste rempli de zéro) et répétez la procédure. Permettez-moi de savoir si c'est la bonne réponse.
Si le digraphe G est représenté par sa matrice d'Adjacence M alors M'=(I - M ) sera singulier si il y a un cycle.
I : matrice d'identité du même ordre de M
Peu plus de réflexions sur l'approche de la matrice... L'exemple cité est la matrice de contiguïté pour la déconnexion d'un graphe (les nœuds 1&2 sont connectés, et les nœuds 3&4 sont connectés, mais ni la paire est connecté à l'autre de la paire). Lorsque vous calculer A^2, la réponse (comme indiqué) est la matrice identité. Toutefois, puisque la Trace(A^2) = 4, ce qui indique qu'il y a 2 boucles de chaque de longueur 2 (qui est correcte). Calculer A^3 n'est pas permis jusqu'à ce que ces boucles sont correctement identifiées et supprimées à partir de la matrice. C'est un procédure nécessitant plusieurs étapes et est bien détaillé par R. L. Norman, "Une Méthode de la Matrice pour l'Emplacement de Cycles d'un Graphe orienté," AIChE J, 11-3 (1965), pp. 450-452. Veuillez noter: il est difficile de dire à l'auteur que cette approche est la garantie de trouver TOUS les cycles, l'UNIQUE cycles et/ou des cycles ÉLÉMENTAIRES. Mon expérience montre qu'il n'a certainement pas d'identifier un SEUL et unique cycles.