Czy przypadek bardzo regularnych grafów jest najtrudniejszy do testowania GI?
gdzie „najtrudniejszy” jest używany w pewnym sensie „zdrowego rozsądku” lub „średnio”, że tak powiem.
Wolfram MathWorld wspomina o niektórych „patologicznie trudnych grafach”. Czym oni są?
Mój przykładowy zestaw 25 par wykresów: http://funkybee.narod.ru/graphs.htm Testowałem wiele innych, ale wszystkie tego samego rodzaju - SRG lub RG z http://www.maths.gla.ac .uk / ~ es / srgraphs.html lub genreg.exe. Jeśli wygeneruję powiedzmy 1000 grafów, przetestuję wszystkie 1000 * (1000 - 1) / 2 pary. Oczywiście nie testuję oczywistych („głupich”) przypadków, np. Wykresów z różnymi sortowanymi wektorami stopni itd. Ale proces ten wydaje się nie mieć końca i do pewnego stopnia pachnie daremnie. Jaką strategię testowania wybrać? Czy to pytanie jest prawie równe samemu problemowi z OG?
Narysowałem nawet na papierze wykres z thesis_pascal_schweitzer.pdf
(sugerowany przez @ 5501). Ładne zdjęcie: http://funkybee.narod.ru/misc/furer.jpg
Nie jestem pewien, ale wydaje mi się, że dokładnie tego rodzaju wykresy „których k-wymiarowy
algorytm Weisfeiler-Lehman nie potrafi odróżnić”.
Ale, panowie, kopiowanie wykresów na papier z e-książek to dla mnie zbyt wiele.
25 0100000000000000000000000 1010000000000000000000000 0101000000000000000000100 0010100000000010000000000 0001010000001000000000000 0000101000000000000000000 0000010100000000000000000 0000001010000000000000000 0000000101000000000000000 0000000010100000000000000 0000000001010000000000000 0000000000101000000000100 0000100000010000000000010 0000000000000010000001010 0001000000000101000000000 0000000000000010100000000 0000000000000001010000000 0000000000000000101000000 0000000000000000010100000 0000000000000000001010000 0000000000000000000101000 0000000000000100000010100 0010000000010000000001000 0000000000001100000000001 0000000000000000000000010 0100000000000000000000000 1010000000000000000000000 0101000000000000000000100 0010100000000010000000000 0001000000001000000010000 0000001000000000000001000 0000010100000000000000000 0000001010000000000000000 0000000101000000000000000 0000000010100000000000000 0000000001010000000000000 0000000000101000000000100 0000100000010000000000010 0000000000000010000001010 0001000000000101000000000 0000000000000010100000000 0000000000000001010000000 0000000000000000101000000 0000000000000000010100000 0000000000000000001010000 0000100000000000000100000 0000010000000100000000100 0010000000010000000001000 0000000000001100000000001 0000000000000000000000010
Pytanie o nagrodę :
===========
Czy ktoś mógłby potwierdzić, że dwie ostatnie pary (# 34 i # 35 w lewym polu tekstowym: http://funkybee.narod.ru/graphs.htm ) są izomorficzne?
Chodzi o to, że są one oparte na tym: http://funkybee.narod.ru/misc/mfgraph2.jpg z A Counterexample in Graph Isomorphism Testing (1987) M. Furera, ale nie mogłem uzyskać NON-izomorficznego. .
PS # 1
Wziąłem 4 (musi być nawet kwadrat o pewnej dodatniej liczbie (m ^ 2)) fundamentalne elementy, połączyłem je w rzędzie, - więc dostałem pierwszy globalny wykres, w jego kopii zamieniłem (krzyżowanie) 2 centralne krawędzie w każdym z 4 kawałków - więc mam drugi globalny wykres. Ale zamieniają się w izomorficzne. Co przeoczyłem lub źle zrozumiałem w bajce Furera?
PS # 2
Wygląda na to, że to rozumiem.
3 pary # 33, # 34 i # 35 (ostatnie 3 pary na http://funkybee.narod.ru/graphs.htm ) to naprawdę niesamowite przypadki.
Para nr 34:
G1 i G2 są grafami nieizomorficznymi.
W G1: krawędzie (1-3), (2-4). W G2: krawędzie (1-4), (2-3).
Nigdy więcej w nich różnic.
Para nr 35:
G11 i G22 są wykresami izomorficznymi.
G11 = G1, a G22 jest kopią G2, z tylko jedną różnicą:
Krawędzie (21–23), (22–24) zamieniono w następujący sposób: (21–24), (22–23)
... a dwa wykresy stają się izomorficzne
tak jakby 2 zamiany unicestwiały się nawzajem.
Dziwna liczba takich zamian powoduje, że wykresy znów NIE są izomorficzne
Wykres nr 33 (20 wierzchołków, 26 krawędzi) jest nadal taki: http://funkybee.narod.ru/misc/mfgraph2.jpg
Wykresy z ## 34, 35 powstały właśnie przez połączenie 2 podstawowych wykresów (# 33) - każdy ma 40 wierzchołków i 60 = 26 + 26 + 8 krawędzi. Przez 8 nowych krawędzi łączę 2 „połówki” tego nowego („dużego”) wykresu. Naprawdę niesamowite i dokładnie tak, jak mówi Martin Furer ...
Przypadek # 33: g = h („h” to „g z jedną możliwą zamianą krawędzi na środku”
(Zobacz zdjęcie))
Przypadek # 34: g + g! = G + h (!!!)
Przypadek # 35: g + g = h + h (!!!)
źródło
Odpowiedzi:
Wszelkie linki do innych wyników będą mile widziane.
źródło
Dla pary 35 znalazłem:
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
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,22,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
14: 1,2,3,4,21,22,23,24
15: 6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39
16: 6,7,9,10,15,16,18,19 , 26, 22, 29, 30, 35, 36, 38, 39
: 17, 1,
2, 3, 2, 2, 22, 23, 24 , 25, 23,
31 , 33,33,34,37,40 19: 6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39
20 : 5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40
21: 5,8,11,12,13,14,17,20, 25, 23, 31, 33,33,34,37,40
22: 5,8,11,12,13,14,17,20,25,28,31,32,32,33,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,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,33,34,37,40
31: 6,7,9,10,15,16,18,19 , 26, 23, 29, 30, 35, 36, 38, 39
32: 1,2,3,4,21,22,22,24
33: 6,7,9,10,15,16,18,19 , 26, 22, 29,
30,
35 , 36, 38, 39 34: 5,8,11,12,13,14,17,20,25,28,31,32,33,34,3 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, 22,
29, 30,
35, 35, 36, 38, 37: 5,8,11,12,13,14,17,20,25,28,31,32,33,34,3 40: 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
Jeszcze nie skończyłem pisać skryptu, aby zweryfikować wyniki.
źródło