Gráfico de complemento

Gráfico de Petersen (izquierda) y su gráfico de complemento (derecha).

Como gráfico de complemento , gráfico complementario o complemento se hace referencia en la teoría de grafos a un gráfico particular , obtenido a partir de un gráfico dado.

El gráfico complementario tiene los mismos nodos que el gráfico original, pero difiere en sus bordes : el gráfico complementario tiene exactamente esos bordes que el gráfico original no tiene.

definición

Sea un gráfico dirigido o no dirigido sin múltiples aristas . El gráfico no dirigido o dirigido sin múltiples aristas se denomina gráfico de complemento de si la intersección de y está vacía y la unión de y${\ 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}}$

• en el caso no dirigido, el conjunto de todos los subconjuntos de 2 elementos de V resp.
• en el caso dirigido, el producto cartesiano ${\ Displaystyle V \ times V}$

resultados.

El gráfico de complemento de un gráfico dado a menudo se denomina . Como autocomplementario se refiere a los gráficos isomorfos complementarios a sus gráficos. ${\ Displaystyle G}$${\ Displaystyle {\ overline {G}}}$

caracteristicas

• El complemento del complemento de G es el propio G.