Cograph

Uma cografia é, na teoria dos grafos , um gráfico que pode ser gerado por complementação e união disjunta do gráfico em um nó.

A maioria dos problemas algorítmicos podem ser resolvidos nesta classe em tempo polinomial, e até linear, devido às suas propriedades estruturais.

Definições e caracterizações

Esta família de gráficos foi introduzida por vários autores independentemente na década de 1970 sob vários nomes, incluindo gráficos D *, gráficos Dacey hereditários e gráficos de 2 paridades .

Definição

Uma cografia é um gráfico simples que pode ser construído recursivamente de acordo com as seguintes regras:

o gráfico em um vértice é uma cografia,
o complemento de uma cografia é uma cografia,
a união de duas cografias é uma cografia.

Definição usando a operação de junção

A "junção" de dois gráficos disjuntos e , é a operação que consiste em criar um novo gráfico , onde e . Esta operação é na verdade o complemento da união das complementares. $G_ {1} = (V_ {1}, E_ {1})$ $G_ {2} = (V_ {2}, E_ {2})$ $G = (V, E)$ $V = V_ {1} \ xícara V_ {2}$ $E = E_ {1} \ xícara E_ {2} \ xícara \ {(i, j) | i \ em V_ {1}, j \ em V_ {2} \}$

Uma cografia é então um gráfico que pode ser formado a partir dos gráficos de um vértice, por "junção" e por união.

Caracterizações

Existem muitas caracterizações de cógrafos, incluindo:

as cografias são os gráficos livres , ou seja, aqueles que não têm o caminho dos quatro vértices como subgráfico induzido; $P_ {4}$
cografias são gráficos para os quais todos os subgráficos induzidos não triviais têm dois vértices com a mesma vizinhança .
cografias são os gráficos de inversões de permutações separáveis .

Coarbre

Um coarbre descreve uma cografia, graças às operações que são necessárias para construí-la.

As folhas representam os nós da cografia e os nós internos representam as operações. Os nós marcados com 0 representam a união das cografias representadas pelas subárvores e aqueles marcados com 1 representam a "junção" dessas cografias. Há uma aresta entre dois nós da árvore se e somente se o menor ancestral comum desses nós for rotulado por 1.

Esta representação é única. É uma forma compacta de representar cografias.

Além disso, trocando os 1s e os 0s, obtemos a co-árvore do grafo complementar .

Propriedades matemáticas e inclusões

A família do cógrafo é estável por subgráficos induzidos;
Cografias são gráficos perfeitos .
Os gráficos Turán são cografias.
cografias são gráficos de permutação e gráficos de comparabilidade .

Propriedades algorítmicas

Cografias podem ser reconhecidas em tempo linear. A maioria dos problemas clássicos podem ser resolvidos em tempo linear nesta classe, por exemplo, os problemas relacionados a cliques e ciclos hamiltonianos . O problema de corte máximo é polinomial nesta classe.

Em um contexto de computação distribuída síncrona, a caracterização por 4 caminhos excluídos torna possível reconhecer as cografias em um número constante de voltas.

Notas e referências

ver em particular ( Jung 1978 ), ( Sumner 1974 ) e ( Burlet e Uhry 1984 )
Ver ( Corneil, Lerchs e Burlingham 1981 ) e ( Seinsche 1974 ).
Isso decorre diretamente da caracterização livre de P4.
( Corneil, Perl e Stewart 1985 )
Ver página relacionada no Sistema de Informação sobre Classes de Grafos e suas Inclusões
Veja ( Bodlaender e Jansen 2000 )
( Fraigniaud, Halldorsson e Korman 2012 )

Bibliografia

HA Jung , " Em uma classe de posets e os gráficos de comparabilidade correspondentes ", Journal of Combinatorial Theory, Series B , vol. 24, n o 21978, p. 125–133 ( DOI 10.1016 / 0095-8956 (78) 90013-8 ).

DP Sumner , " Dacey graphs ", J. Austral. Matemática. 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 , “ Complement reducible graphs ”, Discrete Applied Mathematics , vol. 3, n o 3,Mil novecentos e oitenta e um, p. 163–174 ( DOI 10.1016 / 0166-218X (81) 90013-5 ).

DG Corneil , Y. Perl e LK Stewart , “ Um algoritmo de reconhecimento linear para cographs ”, SIAM Journal on Computing , vol. 14, n o 4,1985, p. 926–934 ( DOI 10.1137 / 0214065 , Math Reviews 0807891 ).

Hans L. Bodlaender e Klaus Jansen , “ Sobre a Complexidade do Problema do Corte Máximo ”, Nord. J. Comput. , vol. 7, n o 1,2000, p. 14-31.

D. Seinsche , " Em uma propriedade da classe de gráficos n- coloríveis ", Journal of Combinatorial Theory, Series B , vol. 16, n o 21974, p. 191-193 ( DOI 10.1016 / 0095-8956 (74) 90063-X , Math Reviews 0337679 ).

Pierre Fraigniaud , Magnus M Halldorsson e Amos Korman , "Sobre o impacto dos identificadores na decisão local" , em Princípios de Sistemas Distribuídos ,2012, p. 224 -238