İki grafik izomorfikse, belirleyicileri eşit mi olacak?
10 köşe grafiği G1 ve G2
Algoritmalar ve Uygulamaları ile Grafik Teorisi'nin 2. bölümündeki alıştırmaları çözüyorum. Şimdiye kadar, izomorfizm için sadece tüm kenarları yazıyorum ve küçük grafikler için yeterli olan modelleri bulmaya çalışıyorum. Bu 2 10 köşeli 30 kenarlı grafik için daha ölçeklenebilir bir şeye ihtiyacım olduğunu düşünüyorum. Her iki grafiği birleşik bir yapıya 'çevirmeyi' denedim, ancak elbette bir vertx'in adı değiştiğinde grafik de farklı görünecektir. Bir model bulmaya çalışan bitişik matrisini yazdım ve bu ikisinin izomorfik olmayabileceğinden şüphelenmeme neden olan bir sütun var. Ancak, sütunların biraz daha benzer görünmesi için her zaman bir köşe adını değiştirebilirim. Her neyse, iki grafiğin (A, B) izomorf olduğunu buldum, eğer A = PBP (t) burada P bir permütasyon matrisi ve P (t) onun transpoze.
Det (P) = 1 veya -1 = det (P (t)) ve det (AB) = det (A) * det (B) olduğundan, eğer A ve B izomorfik ise:
det (A) = 1 | -1 * det (B) * 1 | -1 det (A) = det (B)
iki bitişik matris aynı determinanta sahip olabilir ve izomorfik olamaz mı? veya determinanttaki eşitlik, izomorfizm için yeterli (ve çok daha ölçeklenebilir) bir koşul mudur?
En iyi,
Sergio
Yanıtlar
İzomorfik grafiklerin bitişik matrisinin aynı determinanta sahip olacağı gerçekten doğrudur. Gerçekten, eğer$A = PBP^T$ permütasyon matrisi için $P$, sonra $$ \det(A) = \det(P) \det(B) \det(P^T) = \det(P)^2 \det(B) = \det(B). $$ Aslında daha fazlasını söyleyebiliriz: çünkü $A$ ve $B$benzer matrislerdir, aynı özdeğerlere sahip olacaklardır. İki matris aynı özdeğerlere sahipse, otomatik olarak aynı determinanta sahip olurlar.
Sohbet tutmaz: eğer $A,B$ iki grafiğin bitişik matrisleridir ve bizde $\det(A) = \det(B)$, grafiklerin izomorfik olması şart değildir. Aslında,$A$ ve $B$aynı özdeğerlere sahipse, grafiklerin izomorfik olduğu anlamına gelmez. Bu fenomenin örneklerine izospektral (veya cospektral) grafik çiftleri denir .
No. 2 uzunluğundaki yol (2 kenar, 3 köşe) det 0'a ve 3 köşeli grafikte det 0'a sahiptir.