Grafo complementar

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

Seja G = (V, E) 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

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

• O complementar de um grafo sem arestas é um grafo completo e vice versa.
• Um conjunto independente em um grafo é um clique no grafo complementar e vice versa.
• O complementar de um grafo livre de triângulos é um grafo sem garra.
• Um grafo auto-complementar é um grafo que é isomórfico ao seu próprio complemento.
• Cografos são definidos como os grafos que podem ser construídas a partir de uniões disjuntas e operações de complementação, e formam uma família de grafos auto-complementares: o complemento de qualquer cografo é outro (possivelmente diferente) cografo (Complement Reducible Graphs).

Referências

• BONDY, John Adrian; MURTY, U. S. R.. Graph Theory with Applications. [S.l.]: North-Holland, 1976. ISBN 0-444-19451-7.
• DIESTEL, Reinhard. Electronic edition Graph Theory. 3ª ed. Nova York, Berlin: Springer, 2005. ISBN 3-540-26182-6.