Grafo planare: differenze tra le versioni

Versione delle 19:50, 7 mar 2006

Versione attuale delle 20:12, 12 mag 2023

(54 versioni intermedie di 43 utenti non mostrate)

Riga 1:

{{F|teoria dei grafi|giugno 2013}}

InNella [[teoria dei grafi]] si definisce '''grafo planare''' un grafo che può essere [[raffigurazione di un grafo|raffigurato]] in un [[piano (matematica)|piano]] in modo che non si abbiano [[spigoloArco (grafoteoria dei grafi)|spigoliarchi]] che si intersecano. Ad esempio sono planari i seguenti grafi:

[[ImmagineFile:6n-graf.pngsvg]] [[ImageFile:Complete graph K4.svg|200px]]

Il secondo può essere raffigurato senza spigoliarchi che si intersecano spostando uno degli spigoliarchi 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 spigoliarchi che si intersecano. Le due seguenti figure forniscono raffigurazioni di due '''grafi non planari''':

[[ImmagineFile:Complete graph K5.svg|thumb|left|250px|''K''₅]] [[ImageFile:Complete bipartite graph K3,3.svg|thumb|left|250px|''K''_3,3]]

<br style="{{clear:|left" />}}

Si tratta del [[grafo completo]] con 5 nodi <math>\,K_5\,</math> e del [[grafo bipartito completo]] con 3+3 nodi <math>\,K_{3,3}\,</math>; 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 spigoliarchi si intersechino. In effetti Kuratowski nel [[1929]] ha dimostrato che questi sono i due grafi non planari più ridotti, con il seguente enunciato.

==Teorema di Kuratowski==

'''Teorema di Kuratowski''':

:Un grafo è planare [[se e solo se]] non contiene alcun sottografo che sia un'espansione di <math>\,K_5\,</math> o un'espansione di <math>\,K_{3,3}\,</math>.

Ricordiamo che per '''espansione di un grafo''' G si intende un grafo che si ottiene da G attraverso manovre di '''inserimento di nodi negli spigoliarchi''', cioè modificando uno spigolo * --- * nella coppia di spigoliarchi adiacenti * --- * --- *; queste manovre potendopossono essere effettuate nessunnessuna, una o più volte.

Questo teorema è conosciuto anche come '''Teorema P''' e possiede diverse formulazioni equivalenti

:Un grafo è planare se e solo se non contiene alcun sottografo che sia [[omeomorfismo (teoria dei grafi)|omeomorfo]] a <math>\,K_5\,</math> o a <math>\,K_{3,3}\,</math>.

:Un grafo è planare se e solo se non contiene tra i suoi [[minore (teoria dei grafi)|minori]] nèné <math>\,K_5\,</math> nèné <math>\,K_{3,3}\,</math>.

Una generalizzazione di ampia portata del teorema di Kuratowski è costituita dal [[teorema di Robertson-Seymour]]; questo enunciato considera <math>\,K_5\,</math> e <math>\,K_{3,3}\,</math> come "minori proibiti" per i grafi planari.

==Algoritmi e criteri di planarità==

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 [[algoritmo|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 [[notazione O grande|O]](''n'').

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 [[algoritmo|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 [[notazione O grande|O]](''n'').

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

:Per Teoremaun 1.[[grafo Sesemplice]], connesso e planare con <var>n</var> &ge;nodi 3, alloraed <var>e</var> &le;archi 3<var>n</var>si - 6dimostra:

: Teorema 2. Se <var>n</var> &gt; 3 e non vi sono cicli di lunghezza 3, allora <var>e</var> &le; 2<var>n</var> - 4

: Teorema 1. Se <var>n</var> ≥ 3, allora <var>e</var> ≤ 3<var>n</var> - 6

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.

: Teorema 2. Se <var>n</var> &gt; 3 e non vi sono cicli di lunghezza 3, allora <var>e</var> &le;≤ 2<var>n</var> - 4

Si noti che questi enunciati riguardano condizioni sufficientinecessarie, 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 <var>K</var>_3,3 ha 6 nodi, 9 spigoli e nessun ciclo di lunghezza 3. Quindi per il Teorema 2 è non planare.

Il grafo <var>K</var>_3,3 ha 6 nodi, 9 spigoliarchi 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 [[isomorfismo tra grafi|isomorfi]] o meno in tempi O(''n'').

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

'''La formula di Eulero''' afferma che se un [[grafo connesso planare]] è disegnato nel piano senza intersezioni del bordo, e ''v'' è il numero di vertici, ''e'', il numero di bordi e ''f'' è il numero di facce (regioni limitate dal bordo, incluse in regioni esterne infinitamente grandi), allora:

==La formula di Eulero==

''v'' &minus; ''e'' + ''f'' = 2,

'''La formula di Eulero''' afferma che se un [[grafo connesso planare]] è disegnato nel piano senza intersezioni del bordo, e ''v'' è il numero di vertici, ''e'', è il numero di bordi eed ''f'' è il numero di facce (regioni limitate daldai bordobordi, incluseinclusa inla regioniregione esterneesterna infinitamente grandigrande), allora:

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 (teoria dei grafi|albero]], allora togliamo uno spigolo che completa un ciclo. Questo abbassa sia ''e'' che ''f'' di una unità, lasciando invariato ''v'' &minus; ''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.

''v'' &minus;− ''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'' &le; 3''v'' - 6 if ''v'' &ge; 3.

In altre parole, la [[caratteristica di Eulero]] è 2. Come nell’illustrazionenell'illustrazione, nel primo grafo planare mostrato su, abbiamo ''v''=6, ''e''=7 e ''f''=3. Se il secondo grafo è ridisegnato senza spigoliarchi che si intersecano, abbiamo ‘’v’’‘'v’'=4, ‘’e’’‘'e’'=6 e ''f''= 4. La formula di Eulero può essere dimostrata come segue: se il grafo non è un [[albero (teoria dei grafigrafo)|albero]], allora togliamo uno spigolo che completa un ciclo. Questo abbassa sia ''e'' che ''f'' di una unità, lasciando invariato ''v'' &minus;− ''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.

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 3''v''-6 spigoli e 2''v''-4 facce.

In un grafo planare finito, semplicementesemplice e connesso, qualsiasi faccia (eccetto quella illimitata) è limitata da almeno tre spigoliarchi 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'' &le;≤ 3''v'' - 6 if ''v'' &ge;≥ 3.

Notiamo che la formula di Eulero è valida anche 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 [[connessione nei grafi|3-connessi]].

Notiamo che la formula di Eulero è valida anche 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 spigoliarchi 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 [[connessione nei grafi|3-connessi]].

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

==Casi particolari==

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 <var>K</var>₄ (il grafo completo su quattro vertici) o del grafo bipartito completo <var>K</var>_2,3 (5 vertici, 2 dei quali connessi ad ognuno dei tre per un totale di sei spigoli).

===Grafi massimali===

Un grafo semplice è chiamato '''planare massimale''' se è planare, e se con l’aggiuntal'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 spigoliarchi; 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 3''v''-6 spigoliarchi e 2''v''-4 facce.

===Grafi planari esterni===

Un grafo è chiamato '''planare esterno''' se è immerso in un piano in modo che i vertici giacciono su una [[circonferenza]] e gli spigoliarchi si trovano all’internoall'interno del corrispondente cerchio e non si intersecano. In maniera equivalente, c’è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''₄ (il grafo completo su quattro vertici) è 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 che afferma che un grafo finito è planare esterno se e solo se non contiene un sottografo che è un’espansioneun'espansione di <var>K</var>₄ (il grafo completo su quattro vertici) o del grafo bipartito completo <var>K</var>_2,3 (5 vertici, 2 dei quali connessi ad ognuno dei tre per un totale di sei spigoliarchi).

==Ulteriori proprietà==

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

Tutti gli [[albero (grafo)|alberi]] finiti e gli [[albero numerabile|alberi numerabili]] sono planari esterni e quindi planari.

Si dimostra che ogni grafo semplice planare ammette un'immersione nel piano tale che tutti gli spigoliarchi 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 spigoliarchi sono segmenti rettilinei che giacciono all'interno del corrispondente cerchio e non si intersecano.

== Voci correlate ==

*[[Poliedro]]

*[[Multigrafo duale]]

*[[Tre case e tre centrali]]

*[[Congettura di Erdős-Gyárfás]]

<!---->

== Altri progetti ==

{{interprogetto|preposizione=sul}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

{{Portale|matematica}}

[[Categoria:Teoria dei grafi]]

[[Categoria:TeoriaFamiglie deidi grafi|Planare]]

[[cs:Rovinný graf]]

[[de:Planarer Graph]]

[[en:Planar graph]]

[[fr:Graphe planaire]]

[[he:גרף מישורי]]

[[ja:平面グラフ]]

[[lt:Plokščiasis grafas]]

[[pl:Graf planarny]]

[[pt:Grafo planar]]

[[th:กราฟเชิงระนาบ]]

[[vi:Đồ thị phẳng]]

[[zh:平面圖]]