Gráfico de complemento

Gráfico de Petersen (à esquerda) e seu gráfico de complemento (à direita).

Como gráfico de complemento , gráfico complementar ou complemento é referido na teoria dos grafos como um gráfico particular , obtido a partir de um dado gráfico.

O grafo complementar tem os mesmos nós do grafo original, mas difere em suas arestas : O grafo complementar tem exatamente aquelas arestas que o grafo original não tem.

definição

Deixe ser um gráfico não direcionado ou direcionado sem arestas múltiplas . O gráfico não direcionado ou direcionado sem arestas múltiplas é chamado de gráfico de complemento de se a interseção de e está vazia e a união de e${\ displaystyle G_ {1} = (V, E_ {1})}$ ${\ displaystyle G_ {2} = (V, E_ {2})}$${\ displaystyle G_ {1}}$${\ displaystyle E_ {1}}$${\ displaystyle E_ {2}}$${\ displaystyle E_ {1}}$${\ displaystyle E_ {2}}$

• no caso não direcionado, o conjunto de todos os subconjuntos de 2 elementos de V resp.
• no caso direcionado, o produto cartesiano ${\ displaystyle V \ times V}$

resultados.

O gráfico de complemento de um determinado gráfico é freqüentemente referido como. Como uma auto-complementaridade se refere a grafos complementares isomórficos aos seus grafos. ${\ displaystyle G}$${\ displaystyle {\ overline {G}}}$

características

• O complemento do complemento de G é o próprio G.