Complemento de um grafo §

---

O complemento de um grafo , representado por , é um grafo de possui o mesmo conjunto de vértices do grafo original, mas com as conexões de arestas invertidas.

De forma mais simples, para criar o complemento de um grafo:

• Vértices: Você mantém exatamente os mesmos vértices do grafo original.
• Arestas: Você inverte todas as conexões. Se dois vértices estavam conectados por uma aresta no grafo original (), eles não estarão conectados no complemento (). E se dois vértices não estavam conectados em , eles estarão conectados em .

Exemplo:

Note

O grafo a esquerda e seu complemento à direta.

Referências §

---

Teoria dos grafos - Conceitos iniciais