Cograph

Un cograph è, in teoria dei grafi , un grafico che può essere generato da complementazione e unione disgiunta dal grafico in un nodo.

La maggior parte dei problemi algoritmici possono essere risolti su questa classe in tempo polinomiale, e anche lineare, grazie alle sue proprietà strutturali.

Definizioni e caratterizzazioni

Questa famiglia di grafici è stata introdotta da diversi autori in modo indipendente negli anni '70 con vari nomi, inclusi grafici D *, grafici Dacey ereditari e grafici a 2 parità .

Definizione

Un grafico è un semplice grafico che può essere costruito ricorsivamente secondo le seguenti regole:

il grafico a un vertice è un cografo,
il complemento di una cografia è una cografia,
l'unione di due cografi è una cografia.

Definizione utilizzando l'operazione di unione

Il "join" di due grafici disgiunti e , è l'operazione che consiste nel creare un nuovo grafo , dove e . Questa operazione è infatti il complemento dell'unione dei complementari. $G_ {1} = (V_ {1}, E_ {1})$ $G_ {2} = (V_ {2}, E_ {2})$ $G = (V, E)$ $V = V_ {1} \ cup V_ {2}$ $E = E_ {1} \ cup E_ {2} \ cup \ {(i, j) | i \ in V_ {1}, j \ in V_ {2} \}$

Un cografo è quindi un grafo che può essere formato dai grafici a un vertice, per "join" e per unione.

Caratterizzazioni

Esistono molte caratterizzazioni di cografi, tra cui:

i grafici sono i grafi liberi , cioè quelli che non hanno il cammino su quattro vertici come sottografo indotto; $P_ {4}$
i grafici sono grafi per i quali tutti i sottografi indotti non banali hanno due vertici aventi lo stesso intorno .
i grafici sono i grafici delle inversioni di permutazioni separabili .

Coarbre

Un coarbre descrive un cografo, grazie alle operazioni che sono necessarie per costruirli.

Le foglie rappresentano i nodi del cografo, mentre i nodi interni rappresentano le operazioni. I nodi etichettati con uno 0 rappresentano l'unione dei cografi rappresentati dai sottoalberi e quelli etichettati con un 1 rappresentano il "join" di questi grafici. C'è un bordo tra due nodi dell'albero se e solo se il più piccolo antenato comune di questi nodi è etichettato con 1.

Questa rappresentazione è unica. È un modo compatto per rappresentare i cografi.

Inoltre, scambiando gli 1 e gli 0, si ottiene il co-albero del grafo complementare .

Proprietà matematiche e inclusioni

La famiglia dei cografi è stabile dai sottografi indotti;
I grafici sono grafici perfetti .
I grafici Turán sono cografi.
i grafici sono grafici di permutazione e grafici di comparabilità .

Proprietà algoritmiche

I cografi possono essere riconosciuti in tempo lineare. La maggior parte dei problemi classici possono essere risolti in tempo lineare su questa classe, ad esempio i problemi relativi alle cricche e ai cicli hamiltoniani . Il problema di taglio massimo è il polinomio su questa classe.

In un contesto di computazione distribuita sincrona, la caratterizzazione a 4 cammini esclusi permette di riconoscere i cografi in un numero di giri costante.

Note e riferimenti

vedi in particolare ( Jung 1978 ), ( Sumner 1974 ) e ( Burlet e Uhry 1984 )
Vedi ( Corneil, Lerchs e Burlingham 1981 ) e ( Seinsche 1974 ).
Questo segue direttamente dalla caratterizzazione P4-free.
( Corneil, Perl e Stewart 1985 )
Vedere la pagina correlata sul sistema informativo sulle classi di grafici e le loro inclusioni
Vedi ( Bodlaender e Jansen 2000 )
( Fraigniaud, Halldorsson e Korman 2012 )

Bibliografia

HA Jung , " Su una classe di poset e i corrispondenti grafici di comparabilità ", Journal of Combinatorial Theory, serie B , vol. 24, n o 21978, p. 125-133 ( DOI 10.1016 / 0095-8956 (78) 90013-8 ).

DP Sumner , " Grafici di Dacey ", J. Austral. Matematica. Soc. , vol. 18, n o 4,1974, p. 492–502 ( DOI 10.1017 / S1446788700029232 ).

M. Burlet e JP Uhry , " Topics on Perfect Graphs (Parity Graphs) ", Annals of Discrete Mathematics , vol. 21,1984, p. 253–277.

DG Corneil , H. Lerchs e L. Stewart Burlingham , " Grafici riducibili del complemento ", Matematica applicata discreta , vol. 3, n o 3,diciannove ottantuno, p. 163–174 ( DOI 10.1016 / 0166-218X (81) 90013-5 ).

DG Corneil , Y. Perl e LK Stewart , " Un algoritmo di riconoscimento lineare per i grafici ", SIAM Journal on Computing , vol. 14, n o 4,1985, p. 926-934 ( DOI 10.1137 / 0214065 , Recensioni matematiche 0807891 ).

Hans L. Bodlaender e Klaus Jansen , " Sulla complessità del problema del taglio massimo ", Nord. J. Comput. , vol. 7, n o 1,2000, p. 14-31.

D. Seinsche , " Su una proprietà della classe dei grafici n- colorabili ", Journal of Combinatorial Theory, serie B , vol. 16, n o 21974, p. 191-193 ( DOI 10.1016 / 0095-8956 (74) 90063-X , Recensioni matematiche 0337679 ).

Pierre Fraigniaud , Magnus M. Halldorsson e Amos Korman , "On the impact of identifiers on local decision" , in Principles of Distributed Systems ,2012, p. 224-238