Homomorfismo de grafos

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

No campo da matemática da teoria dos grafos um homomorfismo de grafos é um mapeamento entre dois grafos que respeita suas estruturas. De forma mais concreta ele mapeia vértices adjacentes a vértices adjacentes.

Definição[editar | editar código-fonte]

Um homomorfismo de grafos f de um grafo \,G=(V,E) para um grafo \,G'=(V',E'), denotado por f:G \longrightarrow G', é um mapeamento f:V \longrightarrow V' do conjunto de vértices de \,G para o conjunto de vértices de \,G' tal que \{f(u),f(v)\}\in E' sempre que \{u,v\}\in E.

A definição acima é estendida para dígrafos (grafos com arestas dirigidas). Então, para um homomorfismo f:G \longrightarrow G', \,(f(u),f(v)) é um arco (aresta dirigida) de \,G' se \,(u,v) é um arco de \,G.

Se há um homomorfismo f:G\longrightarrow H nós escreveremos G\longrightarrow H, e G\not\longrightarrow H caso contrário. Se G\longrightarrow H, G é dito ser homomórfico a H ou H-colorável.

A composição de homomorfismos é também um homomorfismo. Se o homomorfismo f:G\longrightarrow G' é uma bijeção cuja função inversa é também um homomorfismo de grafos, então \,f é um isomorfismo de grafo. Determinar se há ou não um isomorfismo entre dois grafos é um importante problema em complexidade computacional; veja o problema do isomorfismo de subgrafos.

Dois grafos \,G e \,G' são homomorficamente equivalentes se G\longrightarrow G' e G'\longrightarrow G.

O resultado da retração de um grafo \,G é um subgrafo \,H de \,G tal que existe um homomorfismo r:G\longrightarrow H, chamado retração com \,r(x)=x para todo vértice \,x de \,H. Um núcleo é um grafo que não se retrai a um subgrafo próprio. Qualquer grafo é homomorficamente equivalente a um único núcleo.

Generalização[editar | editar código-fonte]

Tome a seguinte definição de grafo:

Um grafo \,G é uma estrutura

\langle\, N, args, rotulo, raiz\,\rangle

em que \,N é o conjunto de nós do grafo, args : N \longrightarrow N^* , \,rotulo : N \longrightarrow \Sigma (uma função parcial) e tais que:

\,comprimento(args(n)) = aridade(rotulo(n)) se rotulo(n)\downarrow; ou \,0, caso contrário.


O conceito de homomorfismo de grafos pode ser generalizado (usando essa estrutura para grafos) de funções (entre nós dos grafos) para relações:

Sejam \,G, H grafos. Uma bissimulação entre \,G e \,H é uma relação R \subseteq N_G \times N_H tal que:

  • raiz_G\,\,R\,\, raiz_H
  • m\,R\,n \longrightarrow \,rotulo_G(m)\,=\,rotulo_H(n)
  • m\,R\,n \longrightarrow \,args_G(m)_i\,R\,args_H(n)_i

Se há tal relação, então \,G e \,H são chamados bissimilares (notação G \underline \longleftrightarrow H). Se \,R é de fato uma função (caso em que chamaremos \,R uma bissimulação funcional) temos um homomorfismo de grafo, tal que  \underline \longleftrightarrow inclui  \underline \longleftarrow , sendo uma ordenação de homomorfismos \underline \longleftarrow definida como:

 G\,\underline \longleftarrow \, H se \varphi : H \longrightarrow G , para algum homomorfismo \,\varphi

Os conceitos de bissimulação e ordenação de homomorfismos são bastante importantes na demonstração de resultados sobre a confluência de sistemas de reescrita de grafos.


Observações[editar | editar código-fonte]

  • Em termos de coloração de grafos, k-colorações de \,G são exatamente homomorfismos f:G\longrightarrow K_k, em que \,K_k é o grafo completo com \,k nós. Como conseqüência se G\longrightarrow H, o número cromático (menor número de cores necessário para colorir um grafo) de \,G é no máximo o de \,H : Nc(G) \le Nc(H) (onde \,Nc(X) representa o número cromático do grafo \,X).
  • O homomorfismo de grafos preserva a conectividade.
  • O produto tensorial de grafos é o produto categorial para a categoria dos grafos e dos homomorfismos de grafos.
  • O problema de decisão associado, isto é, decidir se existe ou não um homomorfismo de um grafo para outro, é NP-completo.

Referências[editar | editar código-fonte]

  • Hell, Pavol; Jaroslav Nešetřil. Graphs and Homomorphisms (Oxford Lecture Series in Mathematics and Its Applications). [S.l.]: Oxford University Press, 2004. ISBN 0-19-852817-5
  • Term Rewriting Systems, Terese, Cambridge Tracts in Theoretical Computer Science, 2003.

Veja também[editar | editar código-fonte]