Si deux graphes sont isomorphes, leurs déterminants seront-ils égaux?
10 graphes de sommets G1 et G2
Je résous les exercices du chapitre 2 de la théorie des graphes avec les algorithmes et ses applications. Jusqu'à présent, pour l'isomorphisme, j'écris simplement toutes les arêtes et j'essaie de trouver les motifs, ce qui suffit pour les petits graphiques. Pour ces 2 graphiques à 30 arêtes de 10 sommets, je pense que j'ai besoin de quelque chose de plus évolutif. J'ai essayé de `` traduire '' les deux graphiques en une structure unifiée, mais bien sûr, si un vertx change de nom, le graphique sera également différent. J'ai écrit la matrice de contiguïté en essayant de trouver un modèle, et il y a une colonne qui me rend suspect que ces deux ne soient peut-être pas isomorphes. Cependant, je pourrais toujours changer le nom d'un sommet pour rendre les colonnes un peu plus similaires. Quoi qu'il en soit, j'ai trouvé que deux graphes (A, B) sont isomorphes si A = PBP (t) où P est une matrice de permutation, et P (t) est sa transposée.
Puisque det (P) = 1 ou -1 = det (P (t)) et det (AB) = det (A) * det (B) alors si A et B sont isomorphes:
det (A) = 1 | -1 * det (B) * 1 | -1 det (A) = det (B)
deux matrices de contiguïté pourraient-elles avoir le même déterminant et ne pas être isomorphes? ou est-ce que l'égalité dans le déterminant est une condition suffisante (et beaucoup plus évolutive) pour l'isomorphisme?
Meilleur,
Sergio
Réponses
Il est en effet vrai que la matrice de contiguïté des graphes isomorphes aura le même déterminant. En effet, si$A = PBP^T$ pour une matrice de permutation $P$, puis $$ \det(A) = \det(P) \det(B) \det(P^T) = \det(P)^2 \det(B) = \det(B). $$ En fait, on peut en dire plus: parce que $A$ et $B$sont des matrices similaires, elles auront les mêmes valeurs propres. Notez que si deux matrices ont les mêmes valeurs propres, elles ont automatiquement le même déterminant.
L'inverse ne tient pas: si $A,B$ sont les matrices de contiguïté de deux graphes et nous avons $\det(A) = \det(B)$, cela ne veut pas nécessairement dire que les graphes sont isomorphes. En fait, même si$A$ et $B$ont les mêmes valeurs propres, cela ne veut pas nécessairement dire que les graphes sont isomorphes. Des exemples de ce phénomène sont appelés paires de graphiques isospectrales (ou cospectrales) .
Non, le chemin de longueur 2 (2 arêtes, 3 sommets) a det 0, et le graphe avec 3 sommets et pas d'arêtes a également det 0.