Grafo cordale

Un ciclo (nero) con due corde (verdi). Quanto a questa parte, il grafo è cordale. Tuttavia, rimuovere uno spigolo verde darebbe come risultato un grafo non cordale. In effetti, l'altro spigolo verde con tre spigoli neri formerebbe un ciclo di lunghezza quattro senza corde.

Nel campo matematico della teoria dei grafi, un grafo è cordale se ciascuno dei suoi cicli di quattro o più vertici ha una corda, che è uno spigolo che non fa parte del ciclo ma connette due vertici di quest'ultimo. In modo equivalente, ogni ciclo indotto nel grafo dovrebbe avere al più tre nodi. I grafi cordali possono anche essere caratterizzati come i grafi che hanno ordinamenti di eliminazione perfetta, come i grafi nei quali ciascun separatore minimale è una cricca, e come i grafi d'intersezione dei sottoalberi di un albero. Essi sono chiamati talvolta grafi a circuito rigido^[1] o grafi triangolati.^[2]

I grafi cordali sono un sottoinsieme dei grafi perfetti. Possono essere riconosciuti in tempo polinomiale, e parecchi problemi che sono difficili su altre classi di grafi come la colorazione dei grafi possono essere risolti in tempo polinomiale quando l'entrata è cordale. L'ampiezza d'albero di un grafo arbitrario può essere caratterizzata dalla dimensione delle cricche nei grafi cordali che la contengono.

Eliminazione perfetta e riconoscimento efficiente

[modifica | modifica wikitesto]

Un ordinamento di eliminazione perfetta in un grafo è un ordinamento dei vertici del grafo tale che, per ciascun vertice v, v e i vicini di v che si presentano dopo v nell'ordine, formano una cricca. Un grafo è cordale se e solo se ha un ordinamento di eliminazione perfetta.^[3]

Rose, Lueker & Tarjan (1976) (vedi anche Habit et al. (2000)) mostrano che un ordinamento di eliminazione perfetta di un grafo cordale si può trovare in maniera efficiente usando un algoritmo noto come ricerca lessicografica in ampiezza. Questo algoritmo mantiene una partizione dei vertici del grafo in una sequenza di insiemi; inizialmente questa sequenza consiste di un singolo insieme con tutti i vertici. L'algoritmo sceglie ripetutamente un vertice v dall'insieme più iniziale nella sequenza che contiene i vertici non scelti precedentemente, e scinde ciascun insieme S della sequenza in due sottoinsiemi più piccoli, il primo che consiste dei vicini di v in S e il secondo che consiste dei non vicini. Quando questo processo di scissione è stato eseguito per tutti i vertici, la sequenza di insiemi ha un solo vertice per ogni insieme, all'inverso di un ordinamento di eliminazione perfetta.

Dal momento che sia questo processo di ricerca lessicografica in ampiezza sia il processo di verificare se un ordinamento è di eliminazione perfetta possono essere eseguiti in tempo lineare, è possibile riconoscere i grafi cordali in tempo lineare. Il problema del tramezzino dei grafi sui grafi cordali è NP-completo,^[4] mentre il problema del grafo sonda sui grafi cordali ha complessità in tempo polinomiale.^[5]

L'insieme di tutti gli ordinamenti di eliminazione perfetta di un grafo cordale può essere modellato come le parole di base di un antimatroide; Chandra et al. (2003) usano questa connessione con gli antimatroidi come parte di un algoritmo per elencare in modo efficiente tutti gli ordinamenti di eliminazione perfetta di un dato grafo cordale.

Cricche massimali e colorazione dei grafi

[modifica | modifica wikitesto]

Un'altra applicazione degli ordinamenti di eliminazione perfetta è trovare una cricca di un grafo cordale in tempo polinomiale, mentre lo stesso problema per i grafi generali è NP-completo. Più in generale, un grafo cordale può avere solo un numero lineare di cricche massimali, mentre i grafi non cordali possono averne un numero esponenziale. Per elencare tutte le cricche massimali di un grafo cordale, si trova semplicemente un ordinamento di eliminazione perfetta, si forma una cricca per ciascun vertice v insieme ai vicini di v che sono successivi a v nell'ordinamento di eliminazione perfetta, e si verifica se ciascuna delle cricche risultanti è massimale.

La cricca massimale più grande è una cricca massima e, poiché i grafi cordali sono perfetti, la dimensione della cricca è uguale al numero cromatico del grafo cordale. I grafi cordali sono perfettamente ordinabili: una colorazione ottimale può essere ottenuta applicando un algoritmo di colorazione golosa ai vertici nell'inverso di un ordinamento di eliminazione perfetta.^[6]

Separatori minimali

[modifica | modifica wikitesto]

In qualsiasi grafo, un separatore di vertici è un insieme di vertici la cui rimozione lascia il grafo rimanente disconnesso; un separatore è minimale se non ha alcun sottoinsieme proprio che è anch'esso un separatore. Secondo un teorema di Dirac (1961), i grafi cordali sono grafi in cui ciascun separatore minimale è una cricca; Dirac usò questa caratterizzazione per provare che i grafi cordali sono perfetti.

La famiglia dei grafi cordali può essere definita induttivamente come i grafi i cui vertici possono essere divisi in tre sottoinsiemi non vuoti A, S e B, tali che A ∪ S ed S ∪ B formino entrambi sottografi indotti cordali, S sia una cricca e non ci siano spigoli da A a B. Cioè, essi sono i grafi che hanno suna scomposizione ricorsiva in sottografi più piccoli mediante separatori di cricche. Per questa ragione, i grafi cordali a volte sono stati chiamati anche grafi scomponibili.^[7]

Grafi d'intersezione di sottoalberi

[modifica | modifica wikitesto]

Una caratterizzazione alternativa dei grafi cordali, dovuta a Gavril (1974), coinvolge gli alberi e i loro sottoalberi.

Da una collezione di sottolaberi di un albero, si può definire un grafo sottoalbero, che è un grafo d'intersezione che ha un solo vertice per ogni sottoalbero e uno spigolo che connette due qualsiasi sottoalberi che si sovrappongono in uno o più nodi del sottoalbero. Gavril mostro che i grafi sottoalberi sono esattamente i grafi cordali.

Una rappresentazione di un grafo cordale come intersezione di sottoalberi forma una scomposizione ad albero del grafo, con l'ampiezza d'albero uguale a uno meno la dimensione della cricca più grande del grafo; la scomposizione ad albero di qualsiasi grafo G può essere vista in questo modo come una rappresentazione di G come sottografo di un grafo cordale. La scomposizione ad albero di un grafo è anche l'albero di giunzione dell'algoritmo omonimo.

Relazione con altre classi di grafi

[modifica | modifica wikitesto]

Sottoclassi

[modifica | modifica wikitesto]

I grafi d'intervallo sono i grafi d'intersezione di sottoalberi dei grafi cammino, un caso speciale di alberi. Perciò, essi sono una sottofamiglia dei grafi cordali.

I grafi divisi sono grafi che sono sia cordali sia complementi di grafi cordali. Bender, Richmond & Wormald (1985) mostrarono che, nel limite quando n va a infinito, la frazione di grafi cordali con n vertici che sono divisi si avvicina a uno.

I grafi tolemaici sono grafi che sono sia cordali sia a distanze ereditarie.

I grafi quasi soglia sono una sottoclasse di grafi tolemaici che sono sia cordali sia cografi. I grafi a blocchi sono un'altra sottoclasse di grafi tolemaici nei quali ogni due cricche massimali hanno al massimo un vertice in comune. Un tipo speciale sono i grafi a mulino a vento, dove il vertice comune è lo stesso per ogni coppia di cricche.

I grafi fortemente cordali sono grafi che sono cordali e non contengono nessun SUn (n≥3) come sottografo indotto.

I K-alberi sono grafi cordali nei quali tutte le critiche massimali e tutti i separatori delle cricche massimali hanno la stessa dimensione.^[8] Le reti apollinee sono grafi planari, o in modo equivalente 3-alberi planari.^[8] I grafi esternoplanari massimali sono una sottoclasse di 2-alberi, e perciò sono anche cordali.

Superclassi

[modifica | modifica wikitesto]

I grafi cordali sono una sottoclasse dei ben noti grafi perfetti. Altre superclassi di grafi cordali comprendono i grafi debolmente cordali, i grafi senza buchi dispari e i grafi senza buchi pari. Infatti, i grafi cordali sono precisamente i grafi che sono al tempo stesso senza buchi dispari e senza buchi pari (vedi i buchi nella teoria dei grafi).

Ogni grafo cordale è un grafo strozzato, un grafo nel quale ogni ciclo periferico è un triangolo, perché i cicli periferici sono un caso speciale dei cicli indotti. I grafi strozzati sono grafi che possono essere formati dalle somme delle cricche di grafi cordali e di grafi planari massimali. Perciò i grafi strozzati includono i grafi planari massimali.^[9]

Completamenti cordali e ampiezza d'albero

[modifica | modifica wikitesto]

Se G è un grafo arbitrario, un completamento cordale di G è un grafo cordale che contiene G come sottografo. L'ampiezza d'albero di G è uno meno del numero dei vertici in una cricca massima di un completamento cordale scelto per minimizzare questa dimensione della cricca. I k-alberi sono grafi ai quali non si possono aggiungere spigoli addizionali senza aumentare la loro ampiezza d'albero a un numero più grande di k. Perciò, i k-alberi sono i propri completamenti cordali, e formano una sottoclasse del grafi cordali. I completamenti cordali si possono usare anche per caratterizzare parecchie altre classi collegate di grafi.^[10]