Jika dua grafik isomorfik, apakah determinannya akan sama?
10 buah grafik simpul G1 dan G2
Saya menyelesaikan latihan di bab 2 dari Teori Grafik dengan Algoritma dan Aplikasinya. Sejauh ini, untuk isomorfisme saya hanya menulis semua tepi dan mencoba menemukan polanya, yang untuk grafik kecil sudah cukup. Untuk 2 grafik 10-simpul 30-sisi ini saya rasa saya membutuhkan sesuatu yang lebih terukur. Saya mencoba 'menerjemahkan' kedua grafik tersebut ke dalam satu kesatuan struktur, namun tentunya jika salah satu simpul mengubah nama grafik tersebut juga akan terlihat berbeda. Saya menulis matriks ketetanggaan mencoba menemukan pola, dan ada kolom yang membuat saya curiga bahwa keduanya mungkin tidak isomorfik. Namun, saya selalu bisa mengubah nama simpul untuk membuat kolom terlihat sedikit lebih mirip. Bagaimanapun, saya menemukan bahwa dua grafik (A, B) isomorfik jika A = PBP (t) di mana P adalah matriks permutasi, dan P (t) adalah transposenya.
Karena det (P) = 1 atau -1 = det (P (t)) dan det (AB) = det (A) * det (B) maka jika A dan B isomorfik:
det (A) = 1 | -1 * det (B) * 1 | -1 det (A) = det (B)
dapatkah dua matriks adjacency memiliki determinan yang sama dan tidak isomorfik? atau apakah kesetaraan dalam determinan merupakan kondisi yang cukup (dan jauh lebih terukur) untuk isomorfisme?
Terbaik,
Sergio
Jawaban
Memang benar bahwa matriks ketetanggaan grafik isomorfik akan memiliki determinan yang sama. Memang, jika$A = PBP^T$ untuk matriks permutasi $P$, kemudian $$ \det(A) = \det(P) \det(B) \det(P^T) = \det(P)^2 \det(B) = \det(B). $$ Sebenarnya, kita dapat mengatakan lebih banyak: karena $A$ dan $B$adalah matriks yang serupa, mereka akan memiliki nilai eigen yang sama. Perhatikan bahwa jika dua matriks memiliki nilai eigen yang sama, maka keduanya secara otomatis memiliki determinan yang sama.
Kebalikannya tidak berlaku: jika $A,B$ adalah matriks ketetanggaan dari dua grafik dan kami punya $\det(A) = \det(B)$, tidak selalu berarti bahwa grafik tersebut isomorfik. Bahkan jika$A$ dan $B$memiliki nilai eigen yang sama, tidak selalu berarti grafik tersebut isomorfik. Contoh dari fenomena ini disebut pasangan grafik isospektral (atau kospektral) .
No. Path dengan panjang 2 (2 sisi, 3 simpul) memiliki det 0, dan graf dengan 3 simpul dan tanpa sisi juga memiliki det 0.