Graficar isomorfismo con relación de equivalencia en el conjunto de vértices

Un gráfico coloreado se puede describir como tupla donde es un gráfico y es el color. Se dice que dos gráficos coloreados y son isomórficos si existe un isomorfismo modo que se obedece el color, es decir, para todos .G c : V ( G ) → N ( G , c ) ( H , d ) π : V ( G ) → V ( H ) c ( v ) = d ( π ( v ) ) v ∈ V ( G $(G,c)$$G$$c : V(G) \rightarrow \mathbb{N}$$(G,c)$$(H,d)$$\pi : V(G) \rightarrow V(H)$$c(v) = d(\pi(v))$$v \in V(G)$

Esta noción captura el isomorfismo de los gráficos coloreados en un sentido muy estricto. Considere el caso en el que tiene dos mapas políticos de la misma región pero usan diferentes conjuntos de colores. Si se pregunta si están coloreados de la misma manera, se supondría que esto significa si existe un mapeo biyectivo entre los dos conjuntos de colores de modo que los colores de ambos mapas coincidan a través de este mapeo. Esta noción se puede formalizar mediante la descripción de los gráficos de colores como tupla donde es una relación de equivalencia en el conjunto de vértices de . Entonces podemos decir que dos de estos gráficos y son isomórficos si existe un isomorfismo tal que para todos los pares∼ G ( G , ∼ 1 ) ( H , ∼ 2 ) π : V ( G ) → V ( H ) v 1 , v 2 ∈ V ( G ) v 1 ∼ 1 v 2  iff  π ( v 1 ) ∼ 2 π ( v 2$(G,\sim)$$\sim$$G$$(G,\sim_1)$$(H,\sim_2)$$\pi : V(G) \rightarrow V(H)$$v_1,v_2 \in V(G)$ sostiene que

Mi pregunta es si este concepto ha sido estudiado previamente para encontrar formas canónicas, etc. y si es así, ¿con qué nombre se conoce?

El problema que describe definitivamente se ha considerado (recuerdo haberlo discutido en la escuela de posgrado, y en ese momento ya se había discutido mucho antes), aunque no puedo señalar ninguna referencia particular en la literatura. Posiblemente porque es linealmente equivalente al isomorfismo gráfico incoloro, como sigue (esto es cierto incluso para las formas canónicas). Llame al problema que describe EQ-GI.

GI es solo el caso especial de EQ-GI donde cada gráfico tiene una sola clase de equivalencia que consiste en todos los vértices.

En la otra dirección, para reducir EQ-GI a GI, dejemos que sea ​​una gráfica con relación de equivalencia con n vértices, m aristas y c clases de equivalencia. Construya un gráfico G ' cuyo conjunto de vértices consista en los vértices de G , junto con los nuevos vértices v 1 , ... , v c , uno para cada clase de equivalencia en = G , así como n + c + 1 nuevos vértices w 0 , ... $(G, \sim_G)$$n$$m$$c$$G'$$G$$v_1, \dotsc, v_c$$=_G$$n+c+1$ . Conecte w i 's en una ruta w 0 - w 1 - w 2 - ⋯ - w n + c , conecte cada v i a w 0 , y para cada vértice en G , conéctelo a la clase de equivalencia correspondiente vértice. Entoncestiene como máximovértices y se puede construir esencialmente en el mismo límite de tiempo. (También tiene como máximo$w_0, \dotsc, w_{n+c}$$w_i$$w_0 - w_1 - w_2 - \dotsb - w_{n+c}$$v_i$$w_0$$G$G ′ n + 2 c + n + 1 ≤ O ( n ) m + n + c + ( n + c + 1 ) ≤ m + 4 n + 1 ≤ O ( m + n ) O ( m ) $v_i$$G'$$n + 2c + n +1 \leq O(n)$$m + n + c + (n+c+1) \leq m + 4n + 1 \leq O(m+n)$bordes, que es para gráficos conectados, pero eso es algo menos relevante ya que la mayoría de los algoritmos GI tienen tiempos de ejecución que esencialmente solo dependen de ).$O(m)$$n$

Actualización : dado que hubo cierta confusión en los comentarios, estoy agregando aquí un bosquejo de la corrección del argumento anterior. Dado y , deje que y sean los gráficos construidos como se arriba; deje que denote el vértice desde arriba en , y el de , y de manera similar para y . Si hay un isomorfismo , debe enviar a para todo( G 2 , ∼ 2 ) G ′ 1 G ′ 2 v i , 1 v i G ′ 1 v i , 2 G ′ 2 w i , 1 w i , 2 G ′ 1 ≅ G ′ 2 w i , 1 w i , 2 i $(G_1, \sim_1)$$(G_2, \sim_2)$$G_1'$$G_2'$$v_{i,1}$$v_i$$G_1'$$v_{i,2}$$G_2'$$w_{i,1}$$w_{i,2}$$G_1' \cong G_2'$$w_{i,1}$$w_{i,2}$$i$, ya que en cada gráfico es el vértice único que es el punto final de cualquier ruta de longitud al menos . En particular, asigna a . Dado que los vecinos de que no son son exactamente , el isomorfismo debe asignar el conjunto al conjunto (y en particular tanto como deben tener el mismo número, , de clases de equivalencia). Tenga en cuenta que el isomorfismo no necesita enviar a para todos n+c+1 w 0 , 1 w 0 , 2 w 0 w 1 v i { v 1 , 1 ,…, v c , 1 }{ v 1 , 2 ,…, v c , 2 } ∼ 1 ∼ 2 c v i , 1 v i , $w_{n+c}$$n+c+1$$w_{0,1}$$w_{0,2}$$w_0$$w_1$$v_i$$\{v_{1,1},\dotsc,v_{c,1}\}$$\{v_{1,2},\dotsc,v_{c,2}\}$$\sim_1$$\sim_2$$c$$v_{i,1}$$v_{i,2}$v G ′ 1 G ′ 2 ( G 1 , ∼ 1 ) ≅ ( G 2 , ∼ 2 ) G ′ 1 ≅ G ′ $i$ , pero está permitido permutar los índices de las siempre que las clases de equivalencia correspondientes puedan asignarse entre sí. Por el contrario, en base a esta descripción de cómo pueden verse los isomorfismos entre y , es fácil ver que si entonces esto da un isomorfismo .$v$$G_1'$$G_2'$$(G_1, \sim_1) \cong (G_2, \sim_2)$$G_1' \cong G_2'$

Leí tu último comentario en la respuesta correcta de Joshua; si necesita transformar EQ-GI a GI de color (es decir, tiene problemas con los colores asignados a las clases de equivalencia) puede usar la siguiente reducción:

$G_1 = (V_1, E_1)$$G_2 = (V_2, E_2)$$q$$|V_1|+1=|V_2|+1$$K'_{|V_1|+1}$ ) y el uso q + 1 colores c 1 , . . . , c q , c q + 1 .$K''_{|V_2|+1}$$q+1$$c_1,...,c_q,c_{q+1}$

$K'$$K''$$q$$c_1,...,c_q$$c_{q+1}$$G_1$$c_{q+1}$$K'$$G_2$$q+1$$K''$

También tenga en cuenta que puede soltar los colores y obtener una instancia de IG equivalente :-)

La reducción correspondiente al ejemplo en su comentario