Grafi e retiGrafi planari

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.

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.

Formula di Eulero

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

Quando si confrontano questi numeri, noterai che il numero di spigoli è sempre uno in menopiù grandeuguale 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...

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.

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 + .