Utente:SilsisScalaZarli/Grafo Planare

{{T|lingua=inglese|argomento=|data=}}

In teoria dei grafi si definisce grafo planare un grafo che può essere raffigurato in un piano in modo che non si abbiano spigoli che si intersecano. Ad esempio sono planari i seguenti grafi:

Il secondo può essere raffigurato senza spigoli che si intersecano spostando uno degli spigoli dati da una diagonale al di fuori del perimetro del quadrato.

Vi sono invece grafi che posseggono solo raffigurazioni piane nelle quali si hanno coppie di spigoli che si intersecano. Le due seguenti figure forniscono raffigurazioni di due grafi non planari:

K₅

K_3,3

Si tratta del grafo completo con 5 nodi $\,K_{5}\,$ e del grafo bipartito completo con 3+3 nodi $\,K_{3,3}\,$; questi due grafi sono chiamati anche grafi di Kuratowski, in onore del matematico polacco Kazimierz Kuratowski. Si constata infatti che non è possibile ridisegnare queste raffigurazioni evitando che gli spigoli si intersechino. In effetti Kuratowski nel 1929 ha dimostrato che questi sono i due grafi non planari più ridotti: v. teorema di Kuratowski.

Nella pratica, se occorre decidere rapidamente se un dato grafo è planare, non è facile servirsi del criterio che si individua nel teorema di Kuratowski. Esistono invece degli algoritmi che consentono di decidere rapidamente la planarità di molti grafi.: per certi grafi con n nodi è possibile stabilire se sono planari o meno in un tempo O(n).

Per un grafo semplice, connesso e planare con n nodi ed e spigoli si dimostra:

Teorema 1. Se n ≥ 3, allora e ≤ 3n - 6

Teorema 2. Se n > 3 e non vi sono cicli di lunghezza 3, allora e ≤ 2n - 4

Si noti che questi enunciati riguardano condizioni sufficienti, non condizioni necessarie e sufficienti: quindi possono essere invocati per dimostrare che un grafo non è planare, ma non per dimostrare che sia planare. Vi sono casi nei quali i Teoremi 1 e 2 non si possono applicare: in tali circostanze si deve ricorrere al Teorema P.

Il grafo K_3,3 ha 6 nodi, 9 spigoli e nessun ciclo di lunghezza 3. Quindi per il Teorema 2 è non planare.

I grafi planari sono grafi relativamente agevoli da trattare: in effetti dati due grafi planari di n nodi, è possibile stabilire se sono isomorfi o meno in tempi O(n).

Il criterio di planarità di MacLane fornisce una caratterizzazione algebrica dei grafi planari mediante i corrispondenti spazi dei cicli.

Si dice faccia limitata di una raffigurazione piana di un grafo planare una regione delimitata da un ciclo del grafo che non contiene altri nodi. Si dice faccia illimitata della raffigurazione la regione esterna al ciclo che contiene ogni altro nodo.

La formula di Eulero afferma che se un grafo connesso planare è disegnato nel piano senza intersezioni degli spigoli, e v è il numero di vertici, e, il numero degli spigoli ed f è il numero di facce (considerando le limitate e la illimitata), allora:

v − e + f = 2 .

In altre parole, la caratteristica di Eulero è 2. Come nell’illustrazione, nel primo grafo planare mostrato su, abbiamo v=6, e=7 e f=3. Se il secondo grafo è ridisegnato senza spigoli che si intersecano, abbiamo ‘’v’’=4, ‘’e’’=6 e f= 4. La formula di Eulero può essere dimostrata come segue: se il grafo non è un albero, allora togliamo uno spigolo che completa un ciclo. Questo abbassa sia e che f di una unità, lasciando invariato v − e + f. Si può ripetere la manovra fino ad ottenere un albero. Gli alberi hanno v=e +1 e f=1, dimostrando che v - e + f = 2.

In un grafo planare finito semplicemente connesso, qualsiasi faccia (eccetto quella illimitata) è limitata da almeno tre spigoli e ogni spigolo è incidente di al più due facce; usando la formula di Eulero, si può dimostrare che questi grafi sono sparsi nel senso che e ≤ 3v - 6 if v ≥ 3.

Un grafo semplice è chiamato planare massimale se è planare, e se con l’aggiunta di un qualunque nuovo spigolo tra due vertici presenti fa cadere la planarità. Tutte le facce (eccetto al più una) sono allora limitate da tre spigoli; questo giustifica il termine alternativo di grafo triangolare che si usa per questi grafi. Se un grafo triangolare ha v vertici con v>2, allora ha precisamente 3v-6 spigoli e 2v-4 facce.

Notiamo che la formula di Eulero è anche valida per i poliedri semplici. Questa non è una coincidenza: ogni poliedro semplice può essere trasformato in un grafo semplice connesso usando i vertici del poliedro come vertici del grafo e gli spigoli del poliedro come spigoli del grafo. Le facce del grafo planare risultante corrispondono alle facce del poliedro. Per esempio il secondo grafo planare mostrato all'inizio corrisponde al tetraedro. Non tutti i grafi planari connessi semplici possono essere associati a poliedri semplici; ad esempio gli alberi non possono essere riguardati come poliedri. Un teorema di Ernst Steinitz dice che i grafi planari associati ai poliedri convessi (o equivalentemente quelli associati a a poliedri semplici) sono precisamente i grafi planari semplici 3-connessi.

Ogni grafo planare senza cappi è tetrapartito, o 4-colorabile; questa è la formulazione in termini della teoria dei grafi del teorema dei quattro colori.

Un grafo è chiamato planare esterno se è immerso in un piano in modo che i vertici giacciono su una circonferenza e gli spigoli si trovano all’interno del corrispondente cerchio e non si intersecano. In maniera equivalente, c’è una faccia che in una opportuna raffigurazione include ogni vertice. Ovviamente, ogni grafo planare esterno è un grafo planare, ma il viceversa non è vero: il secondo esempio mostra che (K₄) è un grafo planare, ma non un grafo planare esterno. Esso è il più piccolo grafo planare non esterno: si ha un teorema simile a quello di Kuratowski afferma che un grafo finito è planare esterno se e solo se non contiene un sottografo che è un’espansione di K₄ (il grafo completo su quattro vertici) o del grafo bipartito completo K_2,3 (5 vertici, 2 dei quali connessi ad ognuno dei tre per un totale di sei spigoli).

Tutti gli alberi (finiti) e gli alberi numerabili sono planari esterni e quindi planari.

Si dimostra che ogni grafo semplice planare ammette un'immersione nel piano tale che tutti gli spigoli sono segmenti rettilinei che non si intersecano. Si dimostra anche che ogni grafo semplice planare esterno ammette un'immersione nel piano tale che tutti i vertici giacciono su una circonferenza e tutti gli spigoli sono segmenti rettilinei che giacciono all'interno del corrispondente cerchio e non si intersecano.

Voci correlate

• Poliedro
• Grafo poliedrale

[[Categoria:Teoria dei grafi]]