Verificatore di Grafo Planare

Verificatore di Grafo Planare

Il Verificatore di Grafo Planare determina se un grafo semplice non orientato è planare — ovvero disegnabile nel piano senza che due spigoli si incrocino — e, quando il grafo non supera il test, trova e visualizza il testimone di Kuratowski: una suddivisione di K₅ (il grafo completo su 5 vertici) o di K₃,₃ (il grafo bipartito completo su 3 + 3 vertici). Lo strumento è pensato per la didattica, il riscaldamento per la programmazione competitiva e per il rapido controllo di piccole costruzioni di grafi.

Cosa significa "Planare"?

Un grafo G = (V, E) è planare se può essere immerso nel piano in modo che gli spigoli si incontrino solo nei loro punti terminali condivisi — senza incroci. Equivalentemente, G può essere disegnato sulla superficie di una sfera senza incroci. La planarità è una proprietà puramente topologica: non dipende da come si disegna il grafo, ma solo dal fatto che esista un qualche disegno privo di incroci.

I grafi planari compaiono ovunque: reti stradali e di utenze, sbroglio di circuiti stampati, grafi degli spigoli dei solidi platonici e struttura delle facce dei poliedri. Tuttavia, molti grafi "naturali" sono ostinatamente non planari: ogni volta che provi a connettere 3 case a 3 utenze senza incroci, ti scontri con la barriera di K₃,₃.

Il Teorema di Kuratowski — Il cuore del verificatore

Kazimierz Kuratowski dimostrò nel 1930 che la planarità ha una caratterizzazione puramente combinatoria:

Una suddivisione di un grafo H si ottiene sostituendo alcuni spigoli di H con percorsi più lunghi i cui vertici interni sono tutti nuovi vertici di grado 2. Il teorema di Kuratowski afferma quindi che K₅ e K₃,₃ sono le uniche ostruzioni alla planarità — ogni grafo non planare ne contiene uno in una forma "allungata".

I grafi proibiti

Formula di Eulero e condizioni necessarie rapide

Prima di eseguire la ricerca della suddivisione (relativamente costosa), il verificatore applica due condizioni necessarie rapide derivate dalla formula di Eulero: per ogni grafo planare connesso disegnato nel piano con V vertici, E spigoli e F facce (contando la faccia esterna), abbiamo

Combinato con l'osservazione che ogni faccia di un grafo planare semplice ha almeno 3 spigoli sul suo contorno, otteniamo il limite superiore degli spigoli:

Qualsiasi grafo che violi queste disuguaglianze è immediatamente non planare, senza necessità di cercare suddivisioni. K₅ ha m = 10, n = 5 ⇒ 3n − 6 = 9, quindi 10 > 9 — viola il limite. K₃,₃ ha m = 9, n = 6 ⇒ 2n − 4 = 8, quindi 9 > 8 — viola il limite bipartito.

Come funziona la ricerca della suddivisione

Dopo i rapidi controlli di Eulero, il verificatore cerca direttamente una suddivisione:

1. Vittoria rapida — rileva K₅ o K₃,₃ come sottografo letterale. Se 5 vertici sono a coppie adiacenti, è palesemente un K₅. Se 6 vertici si dividono 3 + 3 con tutti i 9 spigoli incrociati presenti, è un K₃,₃.
2. Ricerca suddivisione K₅. Per ogni insieme candidato di 5 vertici di "diramazione" (ciascuno con grado ≥ 4 in G), prova a trovare 10 percorsi — uno per coppia di rami — che siano internally vertex-disjoint (nessun vertice non di diramazione appare in più di un percorso) ed eviti di usare gli altri rami come vertici interni. Un riscontro positivo prova la non planarità.
3. Ricerca suddivisione K₃,₃. Sceglie 6 rami (ciascuno con grado ≥ 3) e una bipartizione 3 + 3. Cerca 9 percorsi tra coppie incrociate con lo stesso requisito di disgiunzione interna.
4. Nessun testimone ⇒ planare. Se non viene trovata alcuna suddivisione entro i limiti di dimensione, il teorema di Kuratowski garantisce che il grafo sia planare.

Trovare percorsi disgiunti dai vertici è in generale un problema NP-hard, quindi il verificatore utilizza una ricerca greedy randomizzata limitata: ogni iterazione ordina le coppie richieste per difficoltà, sceglie prima un percorso per la coppia più difficile utilizzando una BFS randomizzata, rimuove quei vertici interni e continua. Se quell'ordine specifico fallisce, riprova con un ordine rimescolato — fino a 40 tentativi per configurazione di rami. Su ogni piccolo grafo testato (fino a 16 vertici), questo è sufficiente per individuare un testimone laddove esista.

Come usare questo calcolatore

1. Scegli un formato di input usando le schede in alto: lista di spigoli o lista di adiacenza. Entrambi codificano lo stesso grafo.
2. Inserisci il tuo grafo. Il grafo è trattato come non orientato, quindi A-B e B-A sono lo stesso spigolo.
3. Clicca su Verifica Planarità. Lo strumento riporta un verdetto, mostra il ragionamento passo-passo (Eulero, bipartito, Kuratowski) e renderizza il grafo.
4. Per un grafo non planare la visualizzazione colora la suddivisione di K₅ o K₃,₃ ed elenca i 10 (o 9) percorsi disgiunti dai vertici. Clicca su una riga di percorso per isolarlo.
5. Per un grafo planare il conteggio delle facce F = m − n + 1 + c viene riportato insieme alla struttura del grafo.

Esempio pratico 1 — K₄ è planare

K₄ ha n = 4, m = 6. Ogni grafo con ≤ 4 vertici è planare e infatti K₄ si immerge come un triangolo con un singolo vertice all'interno connesso a tutti e tre gli angoli. Eulero dice F = 6 − 4 + 2 = 4 facce: tre facce triangolari interne più la faccia esterna.

Esempio pratico 2 — K₃,₃ è non planare

K₃,₃ ha n = 6, m = 9. È bipartito, quindi si applica il limite bipartito: m = 9 > 2n − 4 = 8. Questo da solo prova la non planarità. Il testimone è banale — K₃,₃ è esso stesso il sottografo proibito. Lo strumento evidenzia quindi la partizione 3 + 3 e i 9 spigoli diretti.

Esempio pratico 3 — Il grafo di Petersen

Il grafo di Petersen ha n = 10, m = 15, quindi m ≤ 3n − 6 = 24 e i controlli rapidi di Eulero vengono superati. Eppure è notoriamente non planare. Il verificatore individua una suddivisione di K₃,₃: scegliendo sei vertici dal pentagono esterno e dal pentagramma interno in modo che ogni coppia incrociata possa essere instradata attraverso i restanti quattro vertici tramite percorsi disgiunti dai vertici. Lo strumento disegna il testimone, rendendo tangibile la geometria degli anni '30.

Applicazioni della planarità

• Routing VLSI e PCB. Un circuito a strato singolo è realizzabile solo se il grafo di connessione è planare; le reti non planari costringono all'uso di fori di via o strati extra.
• Disegno e visualizzazione di grafi. I grafi planari ammettono layout chiari e privi di incroci — utili per mappe della metropolitana, grafi di chiamata e diagrammi schematici.
• Progettazione di algoritmi. Molti problemi NP-hard (taglio massimo, copertura dei vertici, isomorfismo di grafi) diventano risolvibili in tempo polinomiale se limitati ai grafi planari.
• Colorazione di grafi. Il teorema dei quattro colori garantisce che ogni grafo planare sia colorabile con 4 colori — un risultato classico la cui formulazione dipende dalla planarità.
• Ottimizzazione combinatoria. Il percorso minimo planare, il flusso massimo e il taglio minimo ammettono tutti algoritmi veloci specializzati.
• Chimica molecolare. I grafi degli idrocarburi aromatici con anello benzenico sono planari; alcune molecole a gabbia non lo sono.

Domande frequenti

Cosa significa planare per un grafo?

Un grafo è planare se puoi disegnarlo sul piano senza che due spigoli si incrocino se non nei vertici condivisi. Equivalentemente, un grafo è planare se e solo se può essere disegnato sulla superficie di una sfera senza incroci. Alberi, cicli, il grafo del cubo e i solidi platonici sono tutti planari, mentre K₅ e K₃,₃ sono i classici esempi non planari.

Cos'è il teorema di Kuratowski?

Il teorema di Kuratowski afferma che un grafo finito è planare se e solo se non contiene sottografi che siano suddivisioni di K₅ o K₃,₃. Una suddivisione si ottiene sostituendo alcuni spigoli con percorsi più lunghi, ciascuno attraverso nuovi vertici di grado 2. Questo fornisce un certificato combinatorio concreto di non planarità.

Qual è la differenza tra K₅ e K₃,₃?

K₅ ha 5 vertici, ogni coppia dei quali è unita da uno spigolo, per 10 spigoli totali. K₃,₃ ha 6 vertici partizionati in due gruppi di 3, con ogni vertice di un gruppo connesso a ogni vertice dell'altro, per 9 spigoli. Entrambi sono i più piccoli grafi non planari del loro genere e insieme formano i minori proibiti per la planarità.

Come aiuta la disuguaglianza di Eulero?

La formula di Eulero V − E + F = 2 per grafi planari connessi combinata con il fatto che ogni faccia di un grafo planare semplice ha almeno 3 spigoli produce m ≤ 3n − 6. Qualsiasi grafo semplice che violi questo limite è immediatamente non planare. Per i grafi planari bipartiti ogni faccia ha almeno 4 spigoli, fornendo il limite più stretto m ≤ 2n − 4. Il verificatore applica entrambi come regole di scarto rapido.

Qual è il limite di dimensioni?

Il verificatore gestisce fino a 16 vertici e 60 spigoli. Questo copre i tipici grafi didattici e da competizione inclusi il grafo di Petersen, il grafo di Möbius-Kantor, piccoli ipercubi e il grafo completo K₇. Grafi più grandi richiedono test di planarità specializzati in tempo lineare come Hopcroft-Tarjan o planarità left-right.

Come viene disegnata la suddivisione testimone?

Quando il grafo è non planare, i 5 vertici di diramazione del K₅ trovato — o i 6 vertici di K₃,₃ divisi nelle due terne A e B — vengono evidenziati su un anello interno. I 10 (o 9) percorsi internamente disgiunti dai vertici sono disegnati ciascuno con un colore distinto per permetterti di tracciare visivamente la topologia di K₅ o K₃,₃. I vertici e gli spigoli che non fanno parte della suddivisione sono oscurati.

Ulteriori letture

• Planar graph — Wikipedia
• Kuratowski's theorem — Wikipedia
• Euler characteristic — Wikipedia
• Petersen graph — Wikipedia
• Wagner's theorem (minor version) — Wikipedia