Abrir menu principal
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 FormalEditar

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 exemplosEditar

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

Referências