Isomorfismo de gráfico com relação de equivalência no conjunto de vértices

9

Um gráfico colorido pode ser descrito como tupla (G,c) onde G é um gráfico c:V(G)N é a coloração. Diz-se que dois gráficos coloridos (G,c) e (H,d) são isomórficos se existir um isomorfismo π:V(G)V(H) modo que a coloração seja obedecida, ou seja, c(v)=d(π(v)) para todosvV(G) .

Essa noção captura o isomorfismo de gráficos coloridos em um sentido muito estrito. Considere o caso em que você tem dois mapas políticos da mesma região, mas eles usam conjuntos de cores diferentes. Se alguém perguntar se as cores são da mesma maneira, assumiremos que isso significa se existe um mapeamento bijetivo entre os dois conjuntos de cores, de modo que as cores dos dois mapas coincidam com esse mapeamento. Esta noção pode ser formalizadas descrevendo gráficos coloridos como tuplo (G,) em que é uma relação de equivalência sobre o conjunto de vértice G . Podemos então dizer dois desses gráficos (G,1) e (H,2) são isomórficos se existe um isomorfismoπ:V(G)V(H) tal que para todos os paresv1,v2V(G) sustenta que

v11v2 iff π(v1)2π(v2)

Minha pergunta é se esse conceito foi estudado anteriormente, encontrando formas canônicas etc. e, em caso afirmativo, com que nome ele é conhecido.

John D.
fonte
3
Por favor, não use a notação " " para nada além da relação de igualdade! =
David Richerby

Respostas:

9

O problema que você descreve foi definitivamente considerado (lembro-me de discuti-lo na escola de pós-graduação, e na época já havia sido discutido muito antes disso), embora não possa apontar para nenhuma referência específica na literatura. Possivelmente porque é linearmente equivalente ao isomorfismo gráfico incolor, da seguinte forma (isso é verdade mesmo para formas canônicas). Chame o problema que você descreve EQ-GI.

GI é apenas o caso especial de EQ-GI, em que cada gráfico possui apenas uma classe de equivalência composta por todos os vértices.

Na outra direção, para reduzir EQ-GI a GI, seja um gráfico com relação de equivalência com n vértices, m arestas ec classes de equivalência. Construa um gráfico G cujo conjunto de vértices consiste nos vértices de G , juntamente com os novos vértices v 1 , , v c , um para cada classe de equivalência em = G , bem como n + c + 1 novos vértices w 0 , ,(G,G)nmcGGv1,,vc=Gn+c+1 . Ligue o w i 's num caminho w 0 - W 1 - W 2 - - w n + c , ligar cada v i a w 0 , e para todos os vértices de L , ligá-lo à correspondente equivalência classe vértice v i . Então G tem no máximo n + 2 c + n + 1 O ( n )w0,,wn+cwiw0w1w2wn+cviw0GviGn+2c+n+1O(n)vértices e podem ser construídos essencialmente ao mesmo tempo. (Ele também possui no máximo arestas - que é O ( m ) para gráficos conectados - mas isso é um pouco menos relevante uma vez que a maioria dos algoritmos GI tem tempos de execução que dependem essencialmente apenas de n .)m+n+c+(n+c+1)m+4n+1O(m+n)O(m)n

Atualização : Como houve alguma confusão nos comentários, estou adicionando aqui um esboço da correção do argumento acima. Dado e ( G 2 , 2 ) , sejam G 1 e G 2 os gráficos construídos como acima; Seja v i , 1 denotar o vértice v i de cima em G 1 , e v i , 2 aquele em G (G1,1)(G2,2)G1G2vi,1viG1vi,2 e da mesma forma parawi,1ewi,2. Se existe um isomorfismoG1G2 , ele deve enviarwi,1awi,2para todoi, pois em cada gráficown+cé o vértice único que é o ponto final de qualquer caminho de comprimento pelo menosn+c+1. Em particular,w0,1G2wi,1wi,2G1G2wi,1wi,2iwn+cn+c+1w0,1mapeia para . Desde os vizinhos de w 0 que não são w 1 são exatamente o v i , o isomorfismo deve mapear o conjunto { v 1 , 1 , ... , v c , 1 } para o conjunto { v 1 , 2 , ... , v c , 2 } (e, em particular, 1 e 2 devem ter o mesmo número, cw0,2w0w1vi{v1,1,,vc,1}{v1,2,,vc,2}12c, de classes de equivalência). Observe que o isomorfismo não precisa enviar a v i , 2 para todos os i , mas é permitido permutar os índices dos v 's desde que as classes de equivalência correspondentes possam ser mapeadas uma para a outra. Por outro lado, com base nesta descrição de como os isomorfismos entre G 1 e G 2 podem parecer, é fácil ver que se ( G 1 , 1 ) ( G 2 , 2 )vi,1vi,2ivG1G2(G1,1)(G2,2)então isso dá um isomorfismo .G1G2

Joshua Grochow
fonte
Gf=ffu=fvf(u)=f(v)
(G,=1),(H,=2)G,Hc1,c2=1,=2(G,c)(H,d)(G,=c)(H,=d)
Em outras palavras, não vejo como seria possível uma mera transformação de gráfico reduzir o EQ-GI para o GI colorido, devido às restrições mais complexas. É claro, no entanto, que sua construção funcionaria para reduzir o IG colorido para o IG.
John D.
@ user17410 O EQ-GI é colorido GI. "Chame o problema que você descreve EQ-GI." Certamente é possível que uma transformação de gráfico reduza EQ-GI a GI: na verdade, isso pode ser feito para qualquer problema de isomorfismo em estruturas relacionais para GI. A redução de Josué parece correta para mim; Eu tinha pensado em um pouco mais simples que adiciona mais vértices.
David Richerby
11
Seu argumento de correção me convenceu. Tirei conclusões precipitadas antes de reservar um tempo para analisar sua redução, peço desculpas.
John D.
3

Li seu último comentário na resposta correta do Josué; se você precisar transformar EQ-GI em GI colorido (ou seja, você estiver com problemas com as cores atribuídas às classes de equivalência), poderá usar a seguinte redução:

G1=(V1,E1)G2=(V2,E2)q|V1|+1=|V2|+1K|V1|+1K|V2|+1q+1c1,...,cq,cq+1

KKqc1,...,cqcq+1G1cq+1KG2q+1K

Observe também que você pode soltar as cores e obter uma instância GI equivalente :-)

insira a descrição da imagem aqui
A redução corresponde ao exemplo no seu comentário

Marzio De Biasi
fonte
Isso parece promissor. Vou verificar a correção mais tarde.
John D.
@ user17410: ok, deixe-me saber se você precisar de mais esclarecimentos
Marzio De Biasi