Biarkan menjadi grafik. Untuk titik , mendefinisikan menjadi (terbuka) lingkungan dari di . Yaitu, . Tentukan dua simpul dalam menjadi kembar jika dan memiliki tetangga yang sama, yaitu, jika .x ∈ V N ( x ) x G N ( x ) = { y ∈ Vu , v Gv N ( u ) = N ( v )
Diberikan grafik pada simpul dan tepi sebagai input, seberapa cepat kita dapat menemukan sepasang kembar di , jika pasangan seperti itu ada?n m G
Kita dapat memeriksa apakah dua simpul yang diberikan adalah kembar dalam waktu , dengan membandingkan lingkungan mereka. Algoritma yang mudah adalah untuk menemukan si kembar dengan demikian untuk memeriksa, untuk setiap pasangan simpul, apakah mereka kembar. Ini membutuhkan waktu (dan juga menemukan semua pasangan kembar). Apakah ada cara yang jauh lebih cepat untuk menemukan (jika ada) sepasang kembar dalam grafik? Adakah karya yang diketahui dalam literatur yang membahas masalah ini?O ( n 3 )
Jawaban:
Kembar dalam sebuah grafik hanyalah modul ukuran 2. Penguraian modular dari sebuah grafik dapat ditemukan dalam waktu . Pohon dekomposisi modular secara implisit mewakili semua modul grafik dan terdiri dari tiga jenis node internal: seri, paralel dan node utama, dan daun terdiri dari masing-masing node. Satu set setidaknya dua simpul adalah modul jika dan hanya jika itu adalah beberapa simpul di pohon atau penyatuan beberapa anak-anak dari rangkaian atau simpul paralel.S ⊂ VO ( n + m ) S⊂ V
Jadi untuk menemukan sepasang node kembar, jika ada, kita dapat membangun pohon dekomposisi modular dalam waktu . Kemudian lihat dedaunan, jika induk dari sembarang daun adalah seri atau simpul paralel maka simpul tersebut harus memiliki setidaknya dua anak yang membentuk pasangan kembar. Jadi total waktu berjalan adalah linier.O ( n + m )
http://en.wikipedia.org/wiki/Modular_decomposition
sumber
Masalahnya setara dengan menentukan apakah ada dua baris yang sama dalam matriks grafik. Kita dapat membuat trie pada baris-baris matriks grafik. Compleixty waktu akan menjadi O (n ^ 2)
sumber
EDIT: solusi oleh @MikleB dan @Travis jauh lebih pintar. Maaf atas jawaban berlebihan.
Tampaknya masalah dapat direduksi menjadi masalah perkalian matriks pada matriks adjacency dari grafik, dengan mengganti perkalian dengan EQU (yaitu, NXOR) dan penambahan dengan AND. Jadi jika ada sepasang kembar dalam grafik, maka matriks yang dihasilkan tidak akan menjadi matriks identitas, dan indeks mana nilai bukan nol persis kembar pasangan node.A A T ( i , j ) a i , jSEBUAH A AT ( saya , j ) Sebuahsaya , j
Sejauh pengetahuan saya, masalah multiplikasi matriks dapat diselesaikan dalam waktu dengan oleh algoritma Coppersmith-Winograd . Jika solusi praktis diperlukan, setiap algoritma multiplikasi matriks berfungsi dengan baik dalam praktiknya bagus.α ≈ 2.376O ( nα) α ≈ 2.376
sumber
Karena sistem gila di situs ini saya tidak dapat berkomentar secara langsung, tetapi saya memiliki beberapa pengamatan pada jawaban yang ada.
Aku cukup yakin kebutuhan solusi Hsien-Chih Chang untuk benar ke . A A TSEBUAH2 A AT
Pengamatan TheMachineCharmer 4 adalah kembali ke depan (contoh konter: [0,0,1], [0,1,0], [0,1,1] memiliki determinan 0 tetapi tidak kembar. Jika kembar ada maka determinannya adalah nol.
sumber
Utas ini cukup lama; namun, tampaknya tidak ada yang berhasil dalam pendekatan yang paling elegan dan sederhana. Secara Lexicographically mengurutkan adjacency-list dalam O (n + m) waktu kemudian memeriksa duplikat (lihat Aho, Hopcroft, Ullman, 74 '). Anda dapat menggunakan dekomposisi modular, tetapi ini adalah pembunuhan total yang berlebihan.
sumber
Utas ini sudah tua dan pertanyaan OP telah dijawab tetapi saya ingin menambahkan algoritma lain untuk menemukan semua pasangan seperti itu dalam waktu linier. Tidak ada yang menyebutkan Perbaikan Partisi !
Algoritma ini menemukan kelas kesetaraan dari kembar palsu. Algoritma ini bergantung pada prosedur yang efisien yang memperbaiki partisi. Diberikan satu set
S
dan partisiP = {X1, ..., Xn}
.refine(P, S) = {X1 ^ S, X1 - S, X2 ^ S, X2 - S, ..., Xn ^ S, Xn - S}
.^
menunjukkan set persimpangan dan-
set perbedaan. Partisi stabil jika tidak dapat disempurnakan lebih lanjut. Prosedur ini membutuhkan waktu O (| S |) (lihat artikel Wikipedia tentang perbaikan partisi), jadi ini cepat.Total waktu adalah O (| V | + | E |). Ini mudah diprogram juga.
sumber
Beberapa pengamatan yang mungkin membantu
Jika kembar ada maka determinan dari matriks adjacency adalah nol.
Ide mewah:
Dicuri dariTerinspirasi oleh algoritma kompresi Huffman! :)sumber