Primi elementi della teoria dei grafi

Grafi planari

Un grafo che si può tracciare nel piano in modo che i suoi spigoli si incontrino solo nei vertici è detto planare.

Possiamo immaginare un grafo planare come un circuito elettronico stampato dove i fili conduttori di rame non possono incontrarsi in punti diversi dai punti di collegamento altrimenti si produrrebbe un corto-circuito.

Consideriamo il grafo completo a quattro vertici in figura

Due spigoli si intersecano in un punto che non ò un vertice del grafo. Tuttavia questa intersezione può essere facilmente eliminata spostando la posizione di un vertice o incurvando uno spigolo. In questo modo si ottengono due grafi planare equivalente tra loro e equivalenti a quello inziale.

E' sempre possibile trasformare un grafo in uno equivalente che sia planare? No! Ad esempio, il grafo completo a cinque vertici non può essere trasformato in un grafo planare anche se spostiamo alcuni vertici o deformiamo alcuni spigoli. Se deformiamo gli spigoli AD e BD eliminiamo quattro intersezioni ma resta ancora l'intersezione tra gli spigoli AC e BE.

Gli spigoli BD, DE, EB formano una curva piana chiusa che divide il piano in due regioni, una interna alla curva (quella colorata) e l'altra esterna.

Come si può vedere il vertice C è all'interno della regione colorata mentre il vertice A è esterno a questa regione; ora, se vogliamo unire con uno spigolo il vertice A con il vertice C dobbiamo necessariamente intersecare la curva che delimita la regione colorata e quindi non è possibile deformare lo spigolo AC senza intersecare lo spigolo EB o lo spigolo BD o lo spigolo DE.

Con lo stesso ragionamento si può verificare che tutti i grafi completi con più di quattro vertici non sono planari.

Anche il grafo bipartito k_3,3 non è planare come si può vedere dalla figura il vertice F è all'interno della regione colorata mentre il vertice C è esterno a questa regione; ora, se vogliamo unire con uno spigolo il vertice C con il vertice F dobbiamo necessariamente intersecare la curva che delimita la regione colorata e quindi non è possibile deformare lo spigolo CF senza intersecare lo spigolo BE o lo spigolo ED o lo spigolo AD.

I grafi k₅ e k_3,3 sono i più semplici grafi non planari. Questi due grafi hanno un ruolo importante per stabilire se un grafo sia planare oppure no perchè è stato accertato da Kuratowski che un grafo è sempre planare tranne quando contiene una copia di k₅ o di k_3,3.