Glossario

Seleziona una delle parole chiave a sinistra ...

Grafi e retiGrafi planari

Momento della lettura: ~25 min

Ecco un altro enigma relativo alla teoria dei grafi. In un piccolo villaggio ci sono tre case e tre impianti di servizio che producono acqua, elettricità e gas. Dobbiamo collegare ciascuna casa a ciascuno degli impianti di servizio, ma a causa della disposizione del villaggio, i tubi e cavi non si possono incrociare.

Prova a collegare ciascuna delle case a ciascuna delle società di servizi sottostanti, senza che nessuna delle tue linee si intersechi.

Proprio come i ponti di Königsberg prima, scopri rapidamente che anche questo problema è impossibile. Alcuni grafi possano essere disegnati senza spigoli sovrapposti - questi sono chiamati grafi planari - ma altri no.

K3 è planare.

K4 .

K5 .

Il grafo completo K5 è il grafo non planare più piccolo. Qualsiasi altro grafo che contiene K5 come sottografo, non è planare. Ciò include K6, K7 e tutti i grafi completi più grandi. Il grafo nell'enigma dei tre impianti di servizio è il grafo bipartito K3,3. Si scopre che qualsiasi grafo non planare deve contenere un K5 o un K3,3 (o una suddivisione di questi due grafici) come sottografo. Questo si chiama teorema di Kuratowski.

Planarity

Questo è un grafo planare, ma i ${n} vertici sono stati messi in disordine. Riorganizza i vertici in modo che nessuno degli spigoli si sovrapponga.

Formula di Eulero

Tutti i grafi planari dividono il piano su cui sono disegnati in un numero di aree, chiamate facce.

Vertici
Facce
Spigoli
11 vertici + facce

Vertici
Facce
Spigoli
15 vertici + facce

Vertici
Facce
Bordi
25 vertici + facce

Quando si confrontano questi numeri, noterai che il numero di spigoli è sempre rispetto alla somma del numero di facce e del numero di vertici. In altre parole, F + V = E + 1. Questo risultato si chiama equazione di Eulero e prende il nome dallo stesso matematico che ha risolto il problema dei ponti di Königsberg. Sfortunatamente, esistono infiniti grafi e non possiamo controllarli tutti per vedere se l'equazione di Eulero funziona. Invece possiamo provare a trovare una semplice prova che funzioni per qualsiasi grafo...

FVE
010

0 + 1  =  0 + 1

Il grafico più semplice è costituito da un singolo vertice. Possiamo facilmente verificare che l'equazione di Eulero funziona.
Aggiungiamo un nuovo vertice al nostro grafico. Dobbiamo anche aggiungere uno spigolo e l'equazione di Eulero funziona ancora.
Se vogliamo aggiungere un terzo vertice al grafico, abbiamo due possibilità. Potremmo creare un piccolo triangolo: questo aggiunge un vertice, una faccia e due spigoli, quindi l'equazione di Eulero funziona ancora.
Oppure potremmo semplicemente estendere la linea: questo aggiunge un vertice e un bordo e l'equazione di Eulero funziona.
Continuando così: se ora creiamo un quadrilatero, aggiungeremo un vertice, due spigoli e una faccia. L'equazione di Eulero funziona ancora.

Qualsiasi grafo (finito) può essere costruito iniziando da un vertice e aggiungendo più vertici, uno alla volta. Abbiamo dimostrato che, in qualunque modo aggiungiamo nuovi vertici, l'equazione di Eulero è valida. Pertanto è valida per tutti i grafi. Il processo che abbiamo usato si chiama induzione matematica. È una tecnica molto utile per dimostrare i risultati in tantissimi casi, semplicemente partendo dal caso più semplice e dimostrando che il risultato vale in ogni fase della costruzione di casi più complessi.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Molti grafi planari sembrano molto simili alle reti di poliedri, forme tridimensionali con facce poligonali. Se pensiamo che i poliedri siano fatti di elastici, possiamo immaginare di allungarli fino a quando non diventano piatti, come grafi planari:

Ciò significa che si può usare la formula di Eulero non solo per i grafi planari ma anche per tutti i poliedri - con una piccola differenza. Quando i poliedri si trasformano in grafi, una delle facce scompare: la faccia più in alto dei poliedri diventa "la parte più esterna" dei grafi. In altre parole, se conti il numero di spigoli, facce e vertici di qualsiasi poliedro, scoprirai che F + V = E + .

Icosaedro 20 Facce 12 Vertici 30 Bordi

Rhombicosidodecahedron 62 Facce 60 Vertici 120 Bordi

Icosaedro troncato 32 Facce (12 neri, 20 bianchi) 60 Vertici 90 Bordi

Archie