Топ-100
Indietro

ⓘ Grafo perfetto. Nella teoria dei grafi, un grafo perfetto è un grafo nel quale il numero cromatico di ogni sottografo indotto è uguale alla dimensione della cri ..




Grafo perfetto
                                     

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

I grafi perfetti comprendono molte importanti famiglie di grafi, e servono a unificare risultati che collegano le colorazioni 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 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ò lequivalenza 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.

                                     

1. Famiglie di grafi che sono perfetti

Alcuni dei grafi perfetti più conosciuti sono:

  • I grafi di comparabilità formati da insiemi parzialmente ordinati connettendo coppie di elementi mediante uno spigolo ogni volta che siano collegati nellordine parziale. Questi includono i grafi bipartiti, i complementi dei grafi dintervallo, 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 trapezoidi, i grafi dintersezione di trapezoidi le cui coppie parallele giacciono su due rette parallele. Questi includono i grafi dintervallo, 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à.
  • 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 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 dellintero grafo e i grafi ruota che hanno un numero dispari di vertici.
  • 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 dalbero, 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 dintervallo grafi nei quali ogni vertice rappresenta lintervallo di una linea e ciascuno spigolo rappresenta unintersezione non vuota tra due intervalli, i grafi banalmente perfetti grafi dintervallo 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.
                                     

2. 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 unanticatena, 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 allaffermazione 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.

                                     

3. 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 luguaglianza della dimensione della cricca massima e del numero cromatico in ogni sottografo indotto è equivalente alluguaglianza della dimensione del massimo insieme indipendente e del numero di copertura delle cricche.

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 2 k + 1 non può essere perfetto, perché il suo numero cromatico è k + 1 e il suo numero di cricca è k. Alternativamente, limperfezione di questo grafo consegue dal teorema del grafo perfetto e dallimperfezione 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ò linverso, 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.



                                     

4. 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). Lalgoritmo per il caso generale implica luso del metodo dellellissoide 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ć.

                                     
  • accoppiamento perfetto da un grafo completo K2n. Come mostrò Roberts 1969 questo grafo ha bossicità esattamente n esso è noto a volte come grafo di Roberts
  • compresi il grafo dei servizi, il grafo di Petersen, il grafo di Heawood, il grafo di Möbius - Kantor, il grafo di Pappus, il grafo di Desargues, il grafo di Nauru
  • grafo dovrebbe avere al più tre nodi. I grafi cordali possono anche essere caratterizzati come i grafi che hanno ordinamenti di eliminazione perfetta
  • teoria dei grafi, il grafo di Heawood è un grafo non orientato con 14 vertici e 21 spigoli, che prende nome da Percy John Heawood. Il grafo di Heawood è cubico
  • accoppiamento quasi perfetto Se, per ogni vertice in un grafo c è un accoppiamento quasi perfetto che omette soltanto quel vertice, il grafo è chiamato anche
  • Nella teoria dei grafi, un grafo bipartito è un grafo tale che l insieme dei suoi vertici si può partizionare in due sottoinsiemi tali che ogni vertice
  • matematico della teoria dei grafi, il grafo di Petersen è un grafo non orientato con 10 vertici e 15 spigoli. È un piccolo grafo che serve come utile esempio e
  • Nella teoria dei grafi, un grafo d intervallo è il grafo d intersezione di un multiinsieme di intervalli sulla linea reale. Ha un solo vertice per ciascun
  • Un grafo perfetto è un grafo nel quale il numero di cricca equivale al numero cromatico in ogni sottografo indotto. Un grafo diviso è un grafo nel quale