Homomorfismo de grafos

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

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

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

• 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

• 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

• Reescrita de Grafos
• Teoria das categorias