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)\leq 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 (2004). Graphs and Homomorphisms (Oxford Lecture Series in Mathematics and Its Applications). [S.l.]: Oxford University Press. 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