Grafo complemento

Nella teoria dei grafi, il complemento o inverso di un grafo G è un grafo H sugli stessi vertici tale che due distinti vertici di H sono adiacenti se e solo se non sono adiacenti in G. Ossia, per generare il complemento di un grafo, si riempiono tutti gli spigoli mancanti richiesti per formare un grafo completo, e si rimuovono tutti gli spigoli che vi erano in precedenza. Esso non è, tuttavia, l'insieme complemento del grafo; solo gli spigoli del grafo sono complementati.

Il grafo di Petersen (sulla sinistra) e il suo grafo complemento (sulla destra).

Costruzione formale

Sia G = (V, E) un grafo semplice e consista K di tutti i sottoinsiemi di 2 elementi di V. Allora H = (V, K \ E) è il complemento di G.

Applicazioni ed esempi

Parecchi concetti della teoria dei grafi sono legati tra loro attraverso i grafi complemento:

• Il complemento di un grafo senza spigoli è un grafo completo e viceversa.
• Un insieme indipendente in un grafo è una cricca nel grafo complemento e viceversa.
• Il complemento di qualsiasi grafo senza triangolo è un grafo senza stella.
• Un grafo autocomplementare è un grafo che è isomorfico al proprio complemento.
• I cografi sono definiti come i grafi che possono essere costituiti dall'unione disgiunta e da operazioni di complementazione, e formare una famiglia autocomplementare di grafi: il complemento di qualsiasi cografo è un altro cografo (eventualmente diverso).

Bibliografia

• John Adrian Bondy e U. S. R. Murty, Graph Theory with Applications (PDF), North-Holland, 1976, p. 6, ISBN 0-444-19451-7.
• Reinhard Diestel, Graph Theory, 3ª ed., Springer, 2005, ISBN 3-540-26182-6. Edizione elettronica, p. 4.

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su Grafo complemento

Portale Informatica

Portale Matematica