Grafo complementar

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
O grafo de Petersen (à esquerda) e o seu grafo complementar (à direita).

Em teoria dos grafos, o complemento ou inverso de um grafo G é um grafo H nos mesmos vértices tais que dois vértices de H são adjacentes se e somente se eles não são adjacentes em G. Isso é para encontrar o complemento de um grafo, você preenche todas as arestas que faltavam para obter um grafo completo, e remove todas as arestas que já estavam lá. Não é o conjunto complementar do grafo; apenas as arestas são complementadas.

Construção Formal[editar | editar código-fonte]

Seja G = (VE) ser um grafo simples e seja K consistindo de todos subconjuntos de 2-elementos de V. Então H = ( V, K / E ) é o complemento de G.

Aplicações e exemplos[editar | editar código-fonte]

Vários conceitos em teoria dos grafos são relacionados uns aos outros através de grafos complementares:

Referências