Isomorfismo Flashcards
Rappresentazione parsimoniosa di un grafo e liste di adiacenza.
La matrice di adiacenza di un grafo G contiene n^2 informazioni non tutte utili (es. ci sono gli 0).
Vogliamo minimizzare le informazioni necessarie.
Soluzione: scrivo elenco dei vertici e per ognuno la lista del suo vicinato.
Lista di adiacenza L(vi)= Vk di V | (vi,vk) di E
Grafi Isomorfi
Due grafi semplici G e H sono isomorfi (G =ondina H) se esiste una corrispondenza biunivoca f: G -> H tra i vertici dei grafi tale che se (a,b) è un arco di G allora (f(a),f(b)) è un arco di H.
Condizioni necessarie per l’isomorfismo.
Per essere isomorfi G e H devono necessariamente:
- avere lo stesso ordine e dimensione.
- la distribuzione del grado dei vertici è la stessa: se G ha k vertici di grado d allora H ha k vertici di grado d.
Condizioni sono necessarie ma non sufficienti.
Teo. Grafi isomorfi e Matrice di Permutazione.
2 grafi G e H sono isomorfi se e solo se esiste una matrice di permutazione P tale che A(G)= PtA(H)P.
Una matrice di permutazione è una matrice ottenuta scambiando righe e colonne della matrice identità.
Dim. Grafi isomorfi e Matrice di Permutazione.
1) Ipotesi: G e H isomorfi.
Significa che esiste una permutazione dei vertici di H che fa ottenere G. Di conseguenza esiste una matrice di permutazione tale che A(G)= PtA(H)P.
Dove Pt scambia le colonne e Pt scambia le righe.
2) Ipotesi: esiste una P tale che A(G)= PtA(H)P.
Esiste quindi una biezione f: G->H tale che se (a,b) appartengono a E1 allora (f(a),f(b)) appartengono a E2.
Teo. Grafi Isomorfi e Autovalori e P(lambda)
Siano G e H isomorfi allora gli autovalori di A(G) e A(H) sono uguali e quindi i due polinomi caratteristici sono uguali det(A(G)-λI)= det(A(H)-λI).
Dim. Grafi Isomorfi e Autovalori
Per teo precedente so che
A(G) = PtA(H)P.
So che PPt=I e che det(PPt)=det(I)=1.
Devo verificare che
det(A(G)-λI)= det(A(H)-λI)
det(PtA(H)P-λI)= det(A(H)-λI)
det(A(H)-λI)= det(A(H)-λI)
