İki grafik izomorfikse, belirleyicileri eşit mi olacak?

Aug 18 2020

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

9 BenGrossmann Aug 17 2020 at 22:47

İ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 .

1 JCAA Aug 17 2020 at 23:04

No. 2 uzunluğundaki yol (2 kenar, 3 köşe) det 0'a ve 3 köşeli grafikte det 0'a sahiptir.