Grafo complemento

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search
Il grafo di Petersen (sulla sinistra) e il suo grafo complemento (sulla destra).

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.

Costruzione formale[modifica | modifica wikitesto]

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

Applicazioni ed esempi[modifica | modifica wikitesto]

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

Bibliografia[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]