Primi elementi della teoria dei grafi

Grafo duale di un grafo planare

Per ogni grafo planare G si può costruire un nuovo grafo planare G' detto grafo duale di G in questo modo: all'interno di ciascuna faccia di G (compresa anche quella esterna) si sceglie un punto e se due facce hanno uno spigolo in comune i punti corrispondenti a queste due facce si uniscono con una linea in modo che attraversi lo spigolo comune esattamente una volta e non attraversi altri spigoli di G. Se vi sono più spigoli comuni a due facce bisogna tracciare una nuova linea per ciascuno di essi. I punti e le linee tracciate costituiscono rispettivamente i vertici e gli spigoli di G'. Ad esempio, consideriamo il grafo planare in figura che ha quattro facce; tre interne e una esterna.

inseriamo un punto all'interno di ciascuna faccia del grafo, quindi inseriamo quattro punti rossi

e uniamo due punti rossi con una linea tratteggiata blu se i due punti appartengono a due facce con uno spigolo in comune in modo che la linea blu attraversi solo quello spigolo. Se vi sono più spigoli comuni a due facce tracciamo una nuova linea blu per ciascuno di essi.

Il nuovo grafo G' con i vertici rossi e gli spigoli blu è duale di G. Se confrontiamo i due grafi possiamo scoprire che alle 4 facce di G corrispondono 4 vertici di G', ai 7 vertici di G corrispondono 7 facce di G' e ai 9 spigoli di G corrispondono 9 spigoli di G'. In altre parole, tra i due grafi c'è uno scambio tra il numero delle facce e il numero dei vertici e viceversa, mentre il numero degli spigoli resta immutato.

Consideriamo il grafo planare del cubo e tracciamo il suo duale.

Il duale del cubo ha 6 vertici 8 facce e 12 vertici e ha gli stessi numeri di vertici, di facce, e di spigoli del grafo planare dell'ottaedro regolare. Se confrontiamo questi due grafi possiamo facilmente scoprire che sono uguali sono cioè isomorfi.

Questo significa che i due poliedri, cubo e ottaedro, sono strettamente correlati. Infatti, i 6 centri delle facce del cubo sono vertici di un ottaedro regolare

e viceversa gli 8 centri delle facce di un ottaedro regolare sono i vertici di un cubo. Questi due poliedri sono uno duale dell'altro.

Da ciò si intuisce che il grafo duale del grafo planare dell'ottaedro è isomorfo al grafo planare del cubo. In generale, il duale del duale di un grafo G è isomorfo a G.

Con gli stessi ragionamenti si può verificare che anche icosaedro e dodecaedro regolari sono uno duale dell'altro

e il tetraedro regolare è duale di se stesso cioè, i centri della 4 facce di un tetraedro regolare sono vertici di un altro tetraedro regolare.