Se due grafici sono isomorfi, le loro determinanti saranno uguali?
Grafici a 10 vertici G1 e G2
Sto risolvendo gli esercizi nel capitolo 2 della Teoria dei grafi con gli algoritmi e le sue applicazioni. Finora, per l'isomorfismo scrivo solo tutti i bordi e provo a trovare i modelli, che per piccoli grafici è sufficiente. Per questi 2 grafici a 10 vertici e 30 bordi penso di aver bisogno di qualcosa di più scalabile. Ho provato a "tradurre" entrambi i grafici in una struttura unificata, ma ovviamente se un vertx cambia nome, anche il grafico avrà un aspetto diverso. Ho scritto la matrice di adiacenza cercando di trovare uno schema, e c'è una colonna che mi fa sospettare che questi due possano non essere isomorfi. Tuttavia, potrei sempre cambiare il nome di un vertice per rendere le colonne un po 'più simili. Ad ogni modo, ho trovato che due grafici (A, B) sono isomorfi se A = PBP (t) dove P è una matrice di permutazione e P (t) è la sua trasposizione.
Poiché det (P) = 1 o -1 = det (P (t)) e det (AB) = det (A) * det (B) allora se A e B sono isomorfi:
det (A) = 1 | -1 * det (B) * 1 | -1 det (A) = det (B)
due matrici di adiacenza potrebbero avere lo stesso determinante e non essere isomorfiche? o l'uguaglianza nel determinante è una condizione sufficiente (e molto più scalabile) per l'isomorfismo?
Migliore,
Sergio
Risposte
È infatti vero che la matrice di adiacenza dei grafi isomorfi avrà lo stesso determinante. Infatti, se$A = PBP^T$ per una matrice di permutazione $P$, poi $$ \det(A) = \det(P) \det(B) \det(P^T) = \det(P)^2 \det(B) = \det(B). $$ In effetti, possiamo dire di più: perché $A$ e $B$sono matrici simili, avranno gli stessi autovalori. Si noti che se due matrici hanno gli stessi autovalori, hanno automaticamente lo stesso determinante.
Il contrario non vale: se $A,B$ sono le matrici di adiacenza di due grafici e abbiamo $\det(A) = \det(B)$, non sostiene necessariamente che i grafici siano isomorfi. In effetti, anche se$A$ e $B$hanno gli stessi autovalori, non significa necessariamente che i grafici siano isomorfi. Esempi di questo fenomeno sono chiamati coppie di grafici isospettrali (o cospettrali) .
No. Il percorso di lunghezza 2 (2 bordi, 3 vertici) ha det 0 e anche il grafico con 3 vertici e nessun bordo ha det 0.