Instancias duras para pruebas de isomorfismo gráfico

¿Es el caso de los gráficos muy regulares el más difícil para las pruebas de GI?

donde "más duro" se usa en algún sentido de "sentido común", o "en promedio", por así decirlo.
Wolfram MathWorld menciona algunos "gráficos patológicamente difíciles". ¿Qué son?

Mi conjunto de muestras de 25 pares de gráficos: http://funkybee.narod.ru/graphs.htm Probé muchos otros pero todos del mismo tipo: SRG o RG de http://www.maths.gla.ac .uk / ~ es / srgraphs.html o de genreg.exe. Si genero, digamos, 1000 gráficos, entonces pruebo los 1000 * (1000 - 1) / 2 pares. Por supuesto, no pruebo casos obvios ("tontos"), por ejemplo, gráficos con diferentes vectores ordenados de grados, etc. Pero el proceso parece interminable y hasta cierto punto huele inútil. ¿Qué estrategia de prueba debo elegir? ¿O esta pregunta es casi igual al problema GI en sí?

Incluso volví a dibujar en papel un gráfico de thesis_pascal_schweitzer.pdf
(sugerido por @ 5501). Su bonita foto: http://funkybee.narod.ru/misc/furer.jpg
No estoy seguro, pero parece exactamente este tipo de gráficos "que el
algoritmo de Weisfeiler-Lehman k-dimensional no puede distinguir".
Pero, caballeros, copiar gráficos en papel desde libros electrónicos es demasiado, incluso para mí.

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

Bounty preguntando:
===========
¿Alguien podría confirmar que los 2 últimos pares (# 34 y # 35 en el área de texto izquierda: http://funkybee.narod.ru/graphs.htm ) son isomorfos?
La cuestión es que se basan en esto: http://funkybee.narod.ru/misc/mfgraph2.jpg de A Counteremplemple in Graph Isomorphism Testing (1987) de M. Furer, pero no pude conseguir que no fueran isomorfos. .

PS # 1
Tomé 4 (debe ser un cuadrado de algún número positivo (m ^ 2)) piezas fundamentales, las encajé en una fila, así que obtuve el primer gráfico global, en su copia intercambié (entrecruzando) 2 centrales bordes en cada una de las 4 piezas, así que obtuve el segundo gráfico global. Pero se convierten en isomorfos. ¿Qué extrañé o entendí mal en el cuento de hadas de Furer?

PS # 2
Parece que lo tengo.
3 pares # 33, # 34 y # 35 (los últimos 3 pares en http://funkybee.narod.ru/graphs.htm ) son casos realmente sorprendentes.

Par # 34:
        G1 y G2 son gráficos no isomórficos.
        En G1: aristas (1-3), (2-4). En G2: aristas (1-4), (2-3).
        No más diferencias en ellos.

Par # 35:
        G11 y G22 son gráficos isomorfos.
        G11 = G1 y G22 es una copia de G2, con solo una diferencia:
        Los bordes (21-23), (22-24) se intercambiaron así: (21-24), (22-23)
        ... y dos gráficos se vuelven isomorfos
        como si 2 intercambios se aniquilaran entre sí.
        Un número impar de tales intercambios hace que los gráficos vuelvan a ser NO isomórficos

El gráfico n. ° 33 (20 vértices, 26 aristas) sigue siendo el siguiente: http://funkybee.narod.ru/misc/mfgraph2.jpg Los
gráficos del n. ° 34, 35 se hicieron simplemente mediante el acoplamiento de 2 gráficos básicos (n. ° 33) - cada uno tiene 40 vértices y 60 = 26 + 26 + 8 aristas. Por 8 nuevos bordes conecto 2 "mitades" de ese nuevo gráfico ("grande"). Realmente sorprendente y exactamente como dice Martin Furer ...

Caso # 33: g = h ("h" es "g con un posible intercambio de bordes en el medio"
                                                  (mira la foto))

Caso # 34: g + g! = G + h (!!!)


Caso # 35: g + g = h + h (!!!)

ds.algorithms graph-isomorphism trg787
fuente

Wolfram MathWorld . Realmente necesita mucho más que gráficos muy regulares para dificultar las pruebas de isomorfismo gráfico, por lo que la respuesta es "no". Pero también me gustaría ver una buena respuesta a esta pregunta; en particular, cómo se construyen o encuentran "gráficos patológicamente difíciles".

Peter Shor

No es apropiado seguir editando la pregunta como un registro de progreso. Si continúa trabajando en esto, debe desconectar la pregunta y publicar una nueva cuando tenga una pregunta clara que hacer.

Suresh Venkat

Ya sabes, @Suresh, en este momento descargué 41 MB de SRG (36-15-6-6). Y probé contra mi algoritmo el 6000 primero de estos gráficos. Significa que probé 18,000,000 pares. Todo estaba bien: no hay isomorfos entre ellos. Pero no dice nada, ni a mí ni a nadie más. Lo que necesito es un contraejemplo.

trg787

Este no es el foro adecuado para eso. Las preguntas de la forma "son estos dos gráficos específicos isomorfos o no" no son el tipo correcto de preguntas para este sitio. Preguntas más generales son.

Suresh Venkat

! ingrese la descripción de la imagen aquí Intenté con la matriz APSP ... se detectó isomorfismo. en el gráfico no 33 (20 vértices) Estas son imágenes, postimg.org/image/o8v892koz/05f762ec Las matrices APSP se reorganizaron entre sí, por lo que los pares de gráficos son isomorfos. ** anteriormente, calculé mal. postimg.org/image/6nzlmfe9v ¡ Intentando con otros!

Jim

Para el par 35 encontré:
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,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
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,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,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,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,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
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
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

Todavía no he terminado de escribir el guión para verificar los resultados.

Mohamed Mimouni
fuente

Instancias duras para pruebas de isomorfismo gráfico

Respuestas: