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 de um grafo para um grafo , denotado por , é um mapeamento do conjunto de vértices de para o conjunto de vértices de tal que sempre que .

A definição acima é estendida para dígrafos (grafos com arestas dirigidas). Então, para um homomorfismo , é um arco (aresta dirigida) de se é um arco de .

Se há um homomorfismo nós escreveremos , e caso contrário. Se , é dito ser homomórfico a ou -colorável.

A composição de homomorfismos é também um homomorfismo. Se o homomorfismo é uma bijeção cuja função inversa é também um homomorfismo de grafos, então é 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 e são homomorficamente equivalentes se e .

O resultado da retração de um grafo é um subgrafo de tal que existe um homomorfismo , chamado retração com para todo vértice de . 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 é uma estrutura

em que é o conjunto de nós do grafo, , (uma função parcial) e tais que:

se ; ou , 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 grafos. Uma bissimulação entre e é uma relação tal que:

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

se , para algum homomorfismo

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 são exatamente homomorfismos , em que é o grafo completo com nós. Como conseqüência se , o número cromático (menor número de cores necessário para colorir um grafo) de é no máximo o de  : (onde representa o número cromático do grafo ).
  • 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 (2004). Graphs and Homomorphisms (Oxford Lecture Series in Mathematics and Its Applications) Oxford University Press [S.l.] ISBN 0-19-852817-5. 
  • Term Rewriting Systems, Terese, Cambridge Tracts in Theoretical Computer Science, 2003.

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