ll complemento di un grafo

Il complemento di un grafo consiste in un grafo che conserva gli stessi vertici di quello originale, ma la presenza dei lati  è invertita: nel grafo complemento due vertici sono uniti da un arco se e solo se non lo erano nel grafo originale.

Formalmente il complemento \( \bar{G} \) di un grafo \( G \) è un altro grafo composto dagli stessi vertici $ V(G) $ e dai lati $ uv \in \bar{E}(G) $ che non sono presenti nel grafo d'origine $ uv \notin E(G) $.

In altre parole, il complemento di un grafo ha le connessioni opposte rispetto al grafo originale.

Se due vertici non sono connessi da un lato nel grafo $ G $, allora sono connessi nel complemento \(  \bar{G} \) e viceversa.

Il complemento di un grafo è una specie di immagine speculare rispetto alle connessioni tra i vertici del grafo iniziale. Una sorta di grafo "allo specchio".

Esempio

Immaginiamo una festa con alcuni ospiti e un grafo che rappresenta chi conosce chi. Ogni persona è un punto (vertice) e disegniamo una linea (spigolo) tra due persone se si conoscono.

Se ora vogliamo creare un "anti-grafo" della festa, che mostra invece chi NON conosce chi, prendiamo gli stessi punti (vertici), ma questa volta disegniamo una linea tra due persone solo se queste non si sono mai incontrate.

Quindi, ogni coppia di persone che non aveva una linea tra loro nel primo grafo, adesso ne avrebbe una nel secondo, e viceversa.

Questo "anti-grafo" è quello che chiamiamo il complemento del grafo originale. In pratica, il complemento di un grafo ci mostra tutte le connessioni mancanti del grafo originale.

Merita d'essere sottolineato che l'unione di un grafo \(G\) con il suo complemento \( \bar{G} \) dà come risultato un grafo completo. Questo perché, per definizione, in \(G\) ci sono alcuni archi che collegano certi vertici, mentre nel suo complemento \( \bar{G} \), ci sono archi che collegano tutti i vertici che non sono collegati in \(G\). Unendo \(G\) e \( \bar{G} \), finiamo per avere un arco tra ogni coppia di vertici, che è proprio la definizione di un grafo completo. In un grafo completo, ogni vertice è collegato direttamente a ogni altro vertice, senza eccezioni.

Il complemento di un grafo permette di studiare le proprietà di un grafo esaminando il suo complemento.

A volte, è più facile analizzare certe caratteristiche del complemento di un grafo piuttosto che del grafo stesso.

Inoltre, in alcuni problemi di ottimizzazione, come il problema del massimo clique o del massimo insieme indipendente, lavorare con il complemento di un grafo può semplificare l'approccio o rendere più efficienti gli algoritmi.

Ad esempio, la ricerca di un insieme indipendente massimale in un grafo è equivalente alla ricerca di un clique massimale nel suo complemento.