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. Alcuni problemi NP-hard diventano più facili sui grafi planari: il taglio massimo diventa risolvibile in tempo polinomiale, mentre la copertura dei vertici e l'insieme indipendente restano NP-hard ma ammettono schemi di approssimazione veloci. Anche l'isomorfismo di grafi (di cui non si sa se sia NP-hard) è polinomiale sui 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; lo sono anche i grafi delle molecole a gabbia, come fullereni, cubano e dodecaedrano.

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
• Wagner's theorem (minor version) — Wikipedia

Operazioni matematiche avanzate:

• Calcolatore di Matrice di Adiacenza Nuovo
• Calcolatore di Antilogaritmo
• Calcolatore di funzione Beta
• Calcolatore del Coefficiente Binomiale
• Calcolatrice di distribuzione binomiale
• Calcolatore Bitwise
• Semplificatore di Algebra Booleana Nuovo
• Calcolatore del Teorema Centrale del Limite
• Calcolatore del Teorema Cinese del Resto
• Calcolatore di combinazione
• Calcolatore di Funzione di Errore Complementare
• Calcolatrice di Numeri Complessi
• Calcolatore di Frazioni Continue
• Calcolatore di Derangement (Sottofattoriale)
• Calcolatore del Percorso più Breve di Dijkstra
• Calcolatore di Entropia
• Calcolatore della funzione di errore
• Calcolatore della Funzione Toziente di Eulero
• Calcolatore di decadimento esponenziale
• Calcolatore della crescita esponenziale
• Calcolatore dell'Integrale Esponenziale
• Calcolatore di Esponenti (Alta Precisione) Popolare
• Calcolatore dell'Algoritmo Euclideo Esteso
• Calcolatrice del Fattoriale Popolare
• Calcolatore della Funzione Gamma
• Calcolatore del Rapporto Aureo
• Calcolatore di Colorazione di Grafi Nuovo
• Validatore di Sequenza di Gradi di Grafo
• Calcolatore Ordine Teoria dei Gruppi Nuovo
• Calcolatore del tempo di dimezzamento
• Verificatore di Cammino Hamiltoniano Nuovo
• Calcolatore Inclusione-Esclusione Nuovo
• Risolutore di Mappa di Karnaugh (K-Map) Nuovo
• Risolutore di Programmazione Lineare Nuovo
• Calcolatore Distribuzione Stazionaria Catena di Markov
• Calcolatore dell'Albero Ricoprente Minimo
• Calcolatore Esponenziazione Modulare Nuovo
• Calcolatore dell'Inverso Moltiplicativo Modulare
• Calcolatore Distribuzione Binomiale Negativa Nuovo
• Calcolatore di Flusso in Rete (Flusso Massimo) Nuovo
• Calcolatore del Tasso di Crescita Percentuale
• Calcolatore di Permutazione
• Calcolatore Permutazioni con Ripetizione Nuovo
• Calcolatore del Principio dei Cassetti
• Verificatore di Grafo Planare Nuovo
• Calcolatrice della Distribuzione di Poisson
• Calcolatrice delle Radici dei Polinomi con Passaggi Dettagliati
• Calcolatore Radice Primitiva
• Calcolatrice delle probabilità
• Calcolatrice di Distribuzione di Probabilità
• Calcolatore di Proporzioni
• Calcolatore di formula quadratica
• Calcolatore di Anelli e Campi Nuovo
• Calcolatore di Arrotondamento Popolare
• Calcolatrice Scientifica
• Calcolatore di notazioni scientifiche Popolare
• Calcolatore di Teoria degli Insiemi
• Calcolatore di Cifre Significative Popolare
• Risolutore del Problema del Matrimonio Stabile Nuovo
• Calcolatore di Numeri di Stirling
• Calcolatore di Somme di Cubi
• Calcolatore di somme di numeri interi positivi
• Calcolatore di Somme di Quadrati
• Calcolatore di Ordinamento Topologico Nuovo
• Risolutore del Commesso Viaggiatore (TSP) Nuovo
• Generatore di Tabella di Verità Popolare
• Generatore di Diagramma di Venn (3 Insiemi)