Grafo perfetto

Nella teoria dei grafi, un grafo perfetto è un grafo nel quale il numero cromatico di ogni sottografo indotto è uguale alla dimensione della cricca più grande di quel sottografo. Grazie al teorema del grafo perfetto forte, sappiamo dal 2002 che i grafi perfetti sono la stessa cosa dei grafi di Berge. Un grafo G è un grafo di Berge se né G né il suo complemento hanno un ciclo indotto di lunghezza dispari uguale a 5 o superiore.

Il grafo di Paley di ordine 9, colorato con tre colori e che mostra una cricca di tre vertici. In questo grafo e in ciascuno dei suoi sottografi indotti il numero cromatico è uguale al numero di cricca, pertanto è un grafo perfetto.

I grafi perfetti comprendono molte importanti famiglie di grafi, e servono a unificare risultati che collegano le colorazioni e le cricche in quelle famiglie. Per esempio, in tutti i grafi perfetti, il problema della colorazione dei grafi, il problema della cricca massima e il problema del massimo insieme indipendente possono essere tutti risolti in tempo polinomiale. In aggiunta, parecchi importanti teoremi di minimo e massimo in combinatoria, come il teorema di Dilworth, possono essere espressi in termini della perfezione di certi grafi associati.

La teoria dei grafi perfetti si sviluppò da un risultato del 1958 di Tibor Gallai che in linguaggio moderno può essere interpretato affermando che il complemento di un grafo bipartito è perfetto; questo risultato può anche essere visto come un semplice equivalente del teorema di König, un risultato molto anteriore che collega gli accoppiamenti e le coperture dei vertici nei grafi bipartiti. Il primo uso della locuzione "grafo perfetto" pare che sia in un saggio del 1963 di Claude Berge, dal quale prendono nome i grafi di Berge. In questo saggio egli unificò il risultato di Gallai con vari risultati simili definendo i grafi perfetti, e congetturò l'equivalenza delle definizioni di grafo perfetto e di grafo di Berge; la congettura di Berge fu dimostrata nel 2002 come il teorema del grafo perfetto forte.

Famiglie di grafi che sono perfetti

Alcuni dei grafi perfetti più conosciuti sono:

• I grafi bipartiti, i grafi che possono essere colorati con due colori, comprese le foreste, grafi senza cicli.
• I grafi di linea dei grafi bipartiti (vedi il teorema di König). I grafi della torre (grafi di linea di grafi bipartiti completi) sono un caso speciale.
• I grafi cordali, i grafi nei quali ogni ciclo di quattro o più vertici ha una corda, uno spigolo tra due vertici che non sono consecutivi nel ciclo. Questi includono le foreste, i k-alberi (grafi massimali con una data ampiezza d'albero), i grafi divisi (grafi che possono essere ripartiti in una cricca e in un insieme indipendente), i grafi a blocchi (grafi nei quali ogni componente biconnessa è una cricca), i grafi d'intervallo (grafi nei quali ogni vertice rappresenta l'intervallo di una linea e ciascuno spigolo rappresenta un'intersezione non vuota tra due intervalli), i grafi banalmente perfetti (grafi d'intervallo per intervalli nidificati), i grafi soglia (grafi nei quali due vertici sono adiacenti quando il loro peso totale supera una soglia numerica), i grafi a mulino a vento (formati unendo cricche uguali in un vertice comune) e i grafi fortemente cordali (grafi cordali nei quali ogni ciclo pari di lunghezza sei o più ha una corda dispari).
• I grafi di comparabilità formati da insiemi parzialmente ordinati connettendo coppie di elementi mediante uno spigolo ogni volta che siano collegati nell'ordine parziale. Questi includono i grafi bipartiti, i complementi dei grafi d'intervallo, i grafi banalmente perfetti, i grafi soglia, i grafi a mulino a vento, i grafi di permutazione (grafi nei quali gli spigoli rappresentano coppie di elementi che sono invertiti da una permutazione) e i cografi (grafi formati da operazioni ricorsive di unione disgiunta e di completamento).
• I grafi perfettamente ordinabili, i grafi che possono essere ordinati in modo tale che un algoritmo di colorazione golosa sia ottimale su ogni sottografo indotto. Questi includono i grafi bipartiti, i grafi cordali, i gradi di comparabilità, i grafi a distanze ereditarie (nei quali le distanze dei cammini più brevi nei grafi indotti connessi sono uguali a quelle dell'intero grafo) e i grafi ruota che hanno un numero dispari di vertici.
• I grafi trapezoidi, i grafi d'intersezione di trapezoidi le cui coppie parallele giacciono su due rette parallele. Questi includono i grafi d'intervallo, i grafi banalmente perfetti, i grafi a mulino a vento e i grafi di permutazione; i loro complementi sono un sottoinsieme dei grafi di comparabilità.

Relazione con i teoremi di minimo e massimo

In tutti i grafi, il numero di cricca fornisce un limite inferiore per il numero cromatico, in quanto a tutti i vertici di una cricca devono essere assegnati colori distinti in qualsiasi colorazione propria. I grafi perfetti sono quelli per i quali questo limite inferiore è rigido, non solo nel grafo stesso ma in tutti i suoi sottografi indotti. Per i grafi che non sono perfetti, il numero cromatico e il numero di cricca possono differire; per esempio, un ciclo di lunghezza cinque richiede tre colori in qualsiasi colorazione propria, ma la sua cricca più grande ha dimensione due.

Una dimostrazione che una classe di grafi è perfetta può essere vista come un teorema di minimo e massimo: il numero minimo di colori richiesti per questi grafi uguaglia la dimensione massima di una cricca. Molti importanti teoremi di minimo e massimo in combinatoria possono essere espressi in questi termini. Per esempio, il teorema di Dilworth afferma che il numero minimo di catene in una partizione in catene di un insieme parzialmente ordinato è uguale alla dimensione massima di un'anticatena, e può essere riformulato affermando che i complementi dei grafi di comparabilità sono perfetti. Il teorema di Mirsky afferma che il numero minimo di anticatene in una partizione in anticatene è uguale alla dimensione massima di una catena, e corrisponde nello stesso modo alla perfezione dei grafi di comparabilità.

La perfezione dei grafi di permutazione è equivalente all'affermazione che, in ogni sequenza di elementi ordinati, la lunghezza della più lunga sottosequenza decrescente uguaglia un numero minimo di sequenze in una partizione in sottosequenze decrescenti. Il teorema di Erdős-Szekeres è una facile conseguenza di questa affermazione.

Il teorema di König in teoria dei grafi afferma che una copertura minima dei vertici in un grafo bipartito corrisponde a un accoppiamento massimo, e viceversa; ciò può essere interpretato come la perfezione dei complementi dei grafi bipartiti. Un altro teorema sui grafi bipartiti, che il loro indice cromatico è uguale al loro grado massimo, è equivalente alla perfezione dei grafi di linea dei grafi bipartiti.

Le caratterizzazioni e i teoremi dei grafi perfetti

Nel suo lavoro iniziale sui grafi perfetti, Berge fece due importanti congetture sulla loro struttura che furono provate solo in seguito.

Il primo di questi due teoremi era il teorema del grafo perfetto di Lovász (1972), che afferma che un grafo è perfetto se e solo se il suo complemento è perfetto. Così, la perfezione (definita come l'uguaglianza della dimensione della cricca massima e del numero cromatico in ogni sottografo indotto) è equivalente all'uguaglianza della dimensione del massimo insieme indipendente e del numero di copertura delle cricche.

Un ciclo a sette vertici e il suo complemento, che mostra in ciascun caso una colorazione ottimale e una cricca massima (mostrata con gli spigoli marcati). Dal momento che nessuno dei due grafi usa un numero di colori uguale alla dimensione della sua cricca, nessuno dei due è perfetto.

Il secondo teorema, congetturato da Berge, forniva una caratterizzazione dei grafi proibiti dei grafi perfetti. Un ciclo indotto di lunghezza dispari almeno 5 è chiamato buco dispari. Un sottografo indotto che sia il complemento di un buco dispari è chiamato antibuco dispari. Un ciclo dispari di lunghezza maggiore di 3 non può essere perfetto, perché il suo numero cromatico e il suo numero di cricca è due. Similmente, il complemento di un ciclo dispari di lunghezza 2k + 1 non può essere perfetto, perché il suo numero cromatico è k + 1 e il suo numero di cricca è k. (Alternativamente, l'imperfezione di questo grafo consegue dal teorema del grafo perfetto e dall'imperfezione del ciclo dispari complementare). Poiché questi grafi non sono perfetti, ogni grafo perfetto deve essere un grafo di Berge, un grafo senza buchi dispari e senza antibuchi dispari. Berge congetturò l'inverso, che ogni grafo di Berge è perfetto. Questo fu infine dimostrato come il teorema del grafo perfetto forte di Chudnovsky, Robertson, Seymour e Thomas (2006).

Il teorema del grafo perfetto ha una dimostrazione breve, invece la dimostrazione del teorema del grafo perfetto forte è lunga e tecnica, basata su una scomposizione strutturale profonda dei grafi di Berge. Anche le relative tecniche di scomposizione hanno dato frutto nello studio di altre classi di grafi, e in particolare per i grafi senza stelle.

Algoritmi sui grafi perfetti

In tutti i grafi perfetti, il problema della colorazione dei grafi, il problema della cricca massima e il problema del massimo insieme indipendente possono essere tutti risolti in tempo polinomiale (Grötschel, Lovász & Schrijver (1988)). L'algoritmo per il caso generale implica l'uso del metodo dell'ellissoide per la programmazione lineare, ma si conoscono algoritmi combinatori più efficienti per molti casi speciali.

Per molti anni la complessità di riconoscere i grafi di Berge e i grafi perfetti è rimasta aperta. Dalla definizione dei grafi di Berge, segue immediatamente che il loro riconoscimento è in co-NP (Lovász 1983). Finalmente, successivamente alla dimostrazione del teorema del grafo perfetto forte, fu scoperto un algoritmo in tempo polinomiale da Chudnovsky, Cornuéjols, Liu, Seymour e Vušković.

Bibliografia

• Berge, Claude, Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind, in Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, vol. 10, 1961, p. 114.
• Berge, Claude, Six Papers on Graph Theory, Perfect graphs, Calcutta, Indian Statistical Institute, 1963, pp. 1–21.
• Chudnovsky, Maria; Cornuéjols, Gérard; Liu, Xinming; Seymour, Paul; Vušković, Kristina, Recognizing Berge graphs, in Combinatorica, vol. 25, n. 2, 2005, pp. 143–186, DOI:10.1007/s00493-005-0012-8.
• Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin, The strong perfect graph theorem, in Annals of Mathematics, vol. 164, n. 1, 2006, pp. 51–229, DOI:10.4007/annals.2006.164.51.
• Gallai, Tibor, Maximum-minimum Sätze über Graphen, in Acta Math. Acad. Sci. Hungar., vol. 9, n. 3-4, 1958, pp. 395–434, DOI:10.1007/BF02020271.
• Golumbic, Martin Charles, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980, ISBN 0-444-51530-5. URL consultato il 29 marzo 2014 (archiviato dall'url originale il 22 maggio 2010). Seconda edizione, Annals of Discrete Mathematics, 57, Elsevier, 2004.
• Grötschel, Martin, László, Lovász e Alexander, Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, 1988. Vedi specialmente il capitolo 9, "Stable Sets in Graphs", pp. 273–303.
• Lovász, László, Normal hypergraphs and the perfect graph conjecture, in Discrete Mathematics, vol. 2, n. 3, 1972, pp. 253–267, DOI:10.1016/0012-365X(72)90006-4.
• Lovász, László, A characterization of perfect graphs, in Rivista of Combinatorial Theory, Series B, vol. 13, n. 2, 1972, pp. 95–98, DOI:10.1016/0095-8956(72)90045-7.
• Lovász, László, Selected Topics in Graph Theory, Vol. 2, a cura di Beineke, Lowell W.; Wilson, Robin J., Perfect graphs, Academic Press, 1983, pp. 55–87, ISBN 0-12-086202-6.

Collegamenti esterni

• The Strong Perfect Graph Theorem di Václav Chvátal.
• Open problems on perfect graphs, curato dall'American Institute of Mathematics.
• Perfect Problems, curato da Václav Chvátal.
• Information System on Graph Class Inclusions: perfect graph