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).
• O complemento de um grafo desconexo é um grafo conexo.

Referências

• BONDY, John Adrian; MURTY, U. S. R. (1976). Graph Theory with Applications. [S.l.]: North-Holland. p. 6 e 29. ISBN 0-444-19451-7  !CS1 manut: Nomes múltiplos: lista de autores (link).
• DIESTEL, Reinhard (2005). Electronic edition Graph Theory 3ª ed. Nova York, Berlin: Springer. p. 4. ISBN 3-540-26182-6 .