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 ${\displaystyle f}$ de um grafo ${\displaystyle \,G=(V,E)}$ para um grafo ${\displaystyle \,G'=(V',E')}$, denotado por ${\displaystyle f:G\longrightarrow G'}$, é um mapeamento ${\displaystyle f:V\longrightarrow V'}$ do conjunto de vértices de ${\displaystyle \,G}$ para o conjunto de vértices de ${\displaystyle \,G'}$ tal que ${\displaystyle \{f(u),f(v)\}\in E'}$ sempre que ${\displaystyle \{u,v\}\in E}$.

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

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

A composição de homomorfismos é também um homomorfismo. Se o homomorfismo ${\displaystyle f:G\longrightarrow G'}$ é uma bijeção cuja função inversa é também um homomorfismo de grafos, então ${\displaystyle \,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 ${\displaystyle \,G}$ e ${\displaystyle \,G'}$ são homomorficamente equivalentes se ${\displaystyle G\longrightarrow G'}$ e ${\displaystyle G'\longrightarrow G}$.

O resultado da retração de um grafo ${\displaystyle \,G}$ é um subgrafo ${\displaystyle \,H}$ de ${\displaystyle \,G}$ tal que existe um homomorfismo ${\displaystyle r:G\longrightarrow H}$, chamado retração com ${\displaystyle \,r(x)=x}$ para todo vértice ${\displaystyle \,x}$ de ${\displaystyle \,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 ${\displaystyle \,G}$ é uma estrutura

${\displaystyle \langle \,N,args,rotulo,raiz\,\rangle }$

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

${\displaystyle \,comprimento(args(n))=aridade(rotulo(n))}$ se ${\displaystyle rotulo(n)\downarrow }$; ou ${\displaystyle \,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 ${\displaystyle \,G,H}$ grafos. Uma bissimulação entre ${\displaystyle \,G}$ e ${\displaystyle \,H}$ é uma relação ${\displaystyle R\subseteq N_{G}\times N_{H}}$ tal que:

• ${\displaystyle raiz_{G}\,\,R\,\,raiz_{H}}$
• ${\displaystyle m\,R\,n\longrightarrow \,rotulo_{G}(m)\,=\,rotulo_{H}(n)}$
• ${\displaystyle m\,R\,n\longrightarrow \,args_{G}(m)_{i}\,R\,args_{H}(n)_{i}}$

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

${\displaystyle G\,{\underline {\longleftarrow }}\,H}$ se ${\displaystyle \varphi :H\longrightarrow G}$, para algum homomorfismo ${\displaystyle \,\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 ${\displaystyle \,G}$ são exatamente homomorfismos ${\displaystyle f:G\longrightarrow K_{k}}$, em que ${\displaystyle \,K_{k}}$ é o grafo completo com ${\displaystyle \,k}$ nós. Como conseqüência se ${\displaystyle G\longrightarrow H}$, o número cromático (menor número de cores necessário para colorir um grafo) de ${\displaystyle \,G}$ é no máximo o de ${\displaystyle \,H}$ : ${\displaystyle Nc(G)\leq Nc(H)}$ (onde ${\displaystyle \,Nc(X)}$ representa o número cromático do grafo ${\displaystyle \,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  A referência emprega parâmetros obsoletos |coautor= (ajuda)
• Term Rewriting Systems, Terese, Cambridge Tracts in Theoretical Computer Science, 2003.

Veja também

• Reescrita de Grafos
• Teoria das categorias