Apakah kasus grafik sangat teratur yang paling sulit untuk pengujian GI?
di mana "paling sulit" digunakan dalam beberapa arti "akal sehat", atau "rata-rata", untuk berbicara.
Wolfram MathWorld menyebutkan beberapa "grafik yang sulit secara patologis". Apakah mereka?
Kumpulan sampel saya yang terdiri dari 25 pasang grafik: http://funkybee.narod.ru/graphs.htm Saya menguji banyak yang lain tetapi semuanya dari jenis yang sama - SRG atau RG dari http://www.maths.gla.ac .uk / ~ es / srgraphs.html atau dari genreg.exe. Jika saya menghasilkan, katakanlah, 1000 grafik maka saya menguji semua 1000 * (1000 - 1) / 2 pasangan. Tentu saja, saya tidak menguji kasus yang jelas ("konyol"), misalnya, grafik dengan berbagai vektor derajat yang diurutkan, dll. Tetapi prosesnya sepertinya tidak ada habisnya dan sampai batas tertentu baunya sia-sia. Strategi pengujian apa yang harus saya pilih? Atau apakah pertanyaan ini hampir sama dengan masalah GI itu sendiri?
Saya bahkan menggambar ulang di atas kertas grafik dari thesis_pascal_schweitzer.pdf
(disarankan oleh @ 5501). Ini gambar yang bagus: http://funkybee.narod.ru/misc/furer.jpg
Saya tidak yakin tetapi tampaknya persis seperti ini grafik "yang
tidak dapat dibedakan oleh algoritma Weisfeiler-Lehman k-dimensional ."
Tapi, tuan-tuan, untuk menyalin grafik ke kertas dari e-book itu terlalu berat bagi saya.
25 0100000000000000000000000 101000000000000000000000000 0101000000000000000000100100 001010000000001000000000000 0001010000001000000000000 000010100000000000000000000 0000010100000000000000000 0000001010000000000000000 0000000101000000000000000 0000000010100000000000000 0000000001010000000000000 0000000000101000000000100 0000100000010000000000010 000000000000001000000101010 0001000000000101000000000 0000000000000010100000000 0000000000000001010000000 0000000000000000101000000 0000000000000000010100000 0000000000000000001010000 0000000000000000000101000 0000000000000100000010100 0010000000010000000001000 0000000000001100000000001 0000000000000000000000010 0100000000000000000000000 101000000000000000000000000 0101000000000000000000100100 001010000000001000000000000 000100000000100000001000000 0000001000000000000001000 0000010100000000000000000 0000001010000000000000000 0000000101000000000000000 0000000010100000000000000 0000000001010000000000000 0000000000101000000000100 0000100000010000000000010 000000000000001000000101010 0001000000000101000000000 0000000000000010100000000 0000000000000001010000000 0000000000000000101000000 0000000000000000010100000 0000000000000000001010000 0000100000000000000100000 0000010000000100000000100100 0010000000010000000001000 0000000000001100000000001 0000000000000000000000010
Bounty bertanya:
=========== Adakah yang
bisa mengkonfirmasi bahwa 2 pasangan terakhir (# 34 dan # 35 di textarea kiri: http://funkybee.narod.ru/graphs.htm ) isomorfik?
Masalahnya adalah bahwa mereka didasarkan pada ini: http://funkybee.narod.ru/misc/mfgraph2.jpg dari A Counterexample di Graph Isomorphism Testing (1987) oleh M. Furer tetapi saya tidak bisa mendapatkannya NON-isomorphic. .
PS # 1
Saya mengambil 4 (harus kuadrat dari beberapa bilangan positif (m ^ 2)) potongan mendasar, menyambungkannya berturut-turut, - jadi saya mendapatkan grafik global 1, dalam salinannya saya bertukar (saling silang) 2 pusat tepi di masing-masing 4 buah - jadi saya mendapat grafik global ke-2. Tetapi mereka berubah menjadi isomorfik. Apa yang saya lewatkan atau salah pahami dalam dongeng Furer?
PS # 2
Sepertinya saya mengerti.
3 pasang # 33, # 34 dan # 35 (3 pasangan terakhir di http://funkybee.narod.ru/graphs.htm ) adalah kasus yang sangat menakjubkan.
Pasangan # 34:
G1 dan G2 adalah grafik non-isomorfik.
Dalam G1: edge (1-3), (2-4). Dalam G2: edge (1-4), (2-3).
Tidak ada lagi perbedaan di dalamnya.
Pasangan # 35:
G11 dan G22 adalah grafik isomorfik.
G11 = G1 dan G22 adalah salinan G2, dengan hanya satu perbedaan:
Edges (21-23), (22-24) ditukar seperti ini: (21-24), (22-23)
... dan dua grafik mendapatkan isomorfik
seolah-olah 2 swap saling memusnahkan.
Jumlah ganjil dari swap semacam itu membuat grafik kembali menjadi NON-isomorfik
Grafik # 33 (20 simpul, 26 tepi) masih seperti ini: http://funkybee.narod.ru/misc/mfgraph2.jpg
Grafik dari ## 34, 35 dibuat hanya dengan menggabungkan 2 grafik dasar (# 33) - masing-masing mendapatkan 40 simpul dan 60 = 26 + 26 + 8 tepi. Dengan 8 tepi baru saya menghubungkan 2 "bagian" dari grafik baru ("besar") itu. Sangat menakjubkan dan persis seperti yang dikatakan Martin Furer ...
Kasus # 33: g = h ("h" adalah "g dengan satu sisi yang memungkinkan bertukar di tengahnya"
(Lihat gambarnya))
Kasus # 34: g + g! = G + h (!!!)
Kasus # 35: g + g = h + h (!!!)
sumber
Jawaban:
Setiap tautan ke hasil lain akan sangat dihargai.
sumber
Untuk pasangan 35 saya menemukan:
1: 6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39
2: 6,7,9,10, 15,16,18,19,26,27,29,30,35,36,38,39
3: 1,2,3,4,21,22,23,24 16: 6,7,9,10, 15,16,18,19,26,27,29,30,35,36,38,39 17: 1,2,3,4,21,22,23,24 18: 5,8,11,12, 13,14,17,20,25,28,31,32,33,34,37,40 19: 6,7,9,10,15,15,16,18,19,26,27,29,30,35,35 , 36,38,39 20: 5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40 31: 6,7,9,10,15 , 16,18,19,26,27,29,30,35,36,38,39 32: 1,2,3,4,21,22,23,24 33: 6,7,9,10,15 , 16,18,19,26,27,29,30,35,36,38,39 34: 5,8,11,12,13,14,17,20,25,28,31,32,33, 34,37,40 35: 5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40 36: 6,7,9,10,15, 16,18,19,26,27,29,30,35,36,38,39
4: 5,8,11,12, 13,14,17,20,25,28,31,32,33,34,37,40
5: 5,8,11,12,13,14,17,20,25,28,31,32,33 , 34,37,40
6: 5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40
7: 5,8,11,12,13 , 14,17,20,25,28,31,32,33,34,37,40
8: 6,7,9,10,15,16,18,19,26,27,29,30,35, 36,38,39
9: 6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39
10: 6,7,9,10,15, 16,18,19,26,27,29,30,35,36,38,39
11: 1,2,3,4,21,22,23,24
12: 5,8,11,12,13, 14,17,20,25,28,31,32,33,34,37,40
13: 5,8,11,12,13,14,17,20,25,28,31,32,33,34 , 37,40 15: 6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39
14: 1,2,3,4,21,22,23,24
21: 5,8,11,12,13,14,17,20,, 25,28,31,32,33,34,37,40
22: 5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40
23: 5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40
24: 6,7,9,10,15,15,16,18,19,26 , 27,29,30,35,36,38,39
25: 6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39
26: 1 , 2,3,4,21,22,23,24
27: 6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39
28: 5 , 8,11,12,13,14,17,20,25,28,31,32,33,34,37,40
29: 1,2,3,4,21,22,23,24
30: 5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40 37: 5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40 38: 1,2,3,4,21,22,23,24 39: 6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39 40: 6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39,39 Saya belum selesai menulis naskah untuk memverifikasi hasilnya.
sumber