Pengantar lembut untuk isomorfisme grafik untuk grafik kelambu terbatas

17

Saya membaca tentang kelas graf yang Graph isomorfisma ( ) dalam P . Salah satu kasus tersebut adalah grafik valensi terikat (maksimum lebih dari derajat setiap simpul) seperti yang dijelaskan di sini . Tapi saya merasa terlalu abstrak. Saya akan berterima kasih jika ada yang bisa menyarankan saya beberapa referensi yang bersifat ekspositori. Saya tidak memiliki latar belakang yang kuat dalam teori grup, jadi saya lebih suka makalah yang menggunakan teori grup dengan cara yang lembut (latar belakang saya di CS).GIP

DurgaDatta
sumber
1
Saya tidak punya buku (sayangnya), tetapi The Graph Isomorphism Problem: Its Structural Complexity oleh Johannes Köbler, Uwe Schöning, dan Jacobo Torán dapat berisi bukti untuk kasus tingkat terikat. Anda mungkin ingin memeriksanya.
Tsuyoshi Ito
2
@TsuyoshiIto: Walaupun itu adalah buku yang sangat bagus yang memberikan pengantar yang baik untuk GI dan sedikit kompleksitas struktural umum, itu tidak mengandung banyak (jika ada) tentang kasus gelar terbatas. Saya tidak tahu pengantar yang lembut untuk kasus gelar terbatas, tetapi sangat erat terkait dengan metode teori kelompok sehingga saya ragu ada eksposisi yang menggunakan teori grup "hanya dengan lembut" (seperti yang diminta oleh OP).
Joshua Grochow
Saya ingin memberikan Tinjauan, saya akan segera melakukannya!
Jim

Jawaban:

14

Algoritma untuk isomorfisme grafik tingkat-terikat sangat erat terkait dengan teori grup (permutasi) sehingga saya ragu ada pengantar yang menggunakan grup "hanya dengan lembut." Namun, Anda dapat berkonsultasi dengan Ph.D. Paolo Codenotti tesis untuk latar belakang yang lebih lengkap. Dia tidak membahas isomorfisme grafik tingkat terbatas persis, tetapi mencakup alat yang diperlukan untuk itu (dan sisa tesis adalah tentang hypergraphs peringkat terbatas, memperluas algoritma yang paling terkenal untuk isomorfisme grafik umum ke kasus hypergraph terikat-peringkat) .

Anda juga dapat menemukan buku Algoritma Group-Theoretic dan Graph Isomorphism berguna, karena mencakup sebagian besar latar belakang yang diperlukan (Bab 2, "Konsep Dasar", adalah 47 halaman) dan merupakan eksposisi yang jauh lebih santai daripada sebagian besar makalah yang diterbitkan pada topik.

Joshua Grochow
sumber
1

Notasi: Misalkan menjadi grafik, e = ( v 1 , v 2 ) keunggulan dari X . Himpunan titik V k adalah himpunan simpul dari jarak k dari e , dan biarkan h menjadi tinggi X .X=(V,E)e=(v1,v2)XVkkehX

Menurut definisi , V = V 0V 1 ... V h dan V ( h + 1 ) = . Mari, bagian E k dari tepi X ( 0 k h ) adalah didefinisikan sebagai-VkV=V0V1VhV(h+1)=EkX(0kh)

Ek={(u,w)|uVk,wVkV(k+1)}.

Subgraf didefinisikan sebagai-Xi

Xk=(V0V1Vk,E0E1E(k1)}

Misalnya, X2={(V0V1V2,E0E1)}

adalah kelompok automorfisme dari grafik X di mana e ditetapkan. Jika B adalah generating set dari A u t e ( X k ) , kita menulisB = A u t e ( X k ) , misalnya, jelas bahwa A u t e ( X 0 ) = ( v 1 , v 2Aute(X)XeBAute(Xk)B=Aute(Xk) Mana ( v 1 , v 2 ) adalah permutasi dari simpul v 1 , v 2 dari X .Aute(X0)=(v1,v2)(v1,v2)v1,v2X

Prinsip Membangun set himpunan kelompok automorfisme adalah masalah lengkap GI (grafik isomorfisme) [1]. Jadi, jika kita dapat menghitung himpunan kelompok automorfisme X (yang telah membatasi kelambu pada waktu polinomial), kita dapat menyelesaikan GI dalam waktu polinomial. Jadi, kami ingin menentukan A u t e ( X ) .XXAute(X)

Teknik:

Kami akan membuat . Untuk masing-masing, X k kita akan membangun A u t e ( X ( k ) )X0,X1.....XhXkAute(X(k))

Perhatikan bahwa, permutasi dapat diperluas ke automorfisme A u t e ( X ( k + 1 ) ) .Aute(X(k))Aute(X(k+1))

Jadi, generator dapat diperoleh dari generator untuk A u t e ( X k ) .Aute(X(k+1))Aute(Xk)

Generator membangun, struktur-jenis dimanipulasi. Struktur-jenis E k dapat dibagi ke dalam kelas yang terbatas. Misalnya, dalam kasus trivalen, hanya ada enam jenis (hanya lima dari kasus tersebut yang benar-benar dapat terjadi).EkEk

Kami akan mengklasifikasikan tepi di ke dalam jenis dan kelompok kehendak mereka ke dalam keluarga. Ini membantu untuk membuat sejumlah label unik.Ek

Aute(X(k))Aute(X(k))Aute(X(k+1))Aute(X)

Jim
sumber
[1] Mathon, Rudolf. , Catatan pada grafik menghitung masalah isomorfisma, Inform. Proses. Lett. 8 (1979), no. 3, 131–132.
Jim