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^{\prime }=(V^{\prime },E^{\prime })$, denotado por $f:G⟶G^{\prime }$, é um mapeamento $f:V⟶V^{\prime }$ do conjunto de vértices de $G$ para o conjunto de vértices de $G^{\prime }$ tal que $\{f(u),f(v)\}\in E^{\prime }$ 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⟶G^{\prime }$, $(f(u),f(v))$ é um arco (aresta dirigida) de $G^{\prime }$ se $(u,v)$ é um arco de $G$.

Se há um homomorfismo $f:G⟶H$ nós escreveremos $G⟶H$, e $G⟶̸H$ caso contrário. Se $G⟶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⟶G^{\prime }$ é 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^{\prime }$ são homomorficamente equivalentes se $G⟶G^{\prime }$ e $G^{\prime }⟶G$.

O resultado da retração de um grafo $G$ é um subgrafo $H$ de $G$ tal que existe um homomorfismo $r:G⟶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

$⟨N,args,rotulo,raiz⟩$

em que $N$ é o conjunto de nós do grafo, $args:N⟶N^{*}$ , $rotulo:N⟶\mathrm{\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:

• $rai{z}_{G}Rrai{z}_H$
• $mRn⟶rotul{o}_G(m)=rotul{o}_H(n)$
• $mRn⟶arg{s}_G(m{)}_{i}Rarg{s}_H(n{)}_i$

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

$G\underset{\_}{⟵}H$ se $\phi :H⟶G$, para algum homomorfismo $\phi$

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⟶K_k$, em que $K_k$ é o grafo completo com $k$ nós. Como conseqüência se $G⟶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

• Predefinição:Citar livro
• Term Rewriting Systems, Terese, Cambridge Tracts in Theoretical Computer Science, 2003.

Veja também

• Reescrita de Grafos
• Teoria das categorias