Gráfico perfeito - Perfect graph
Na teoria dos grafos , um grafo perfeito é um grafo no qual o número cromático de cada subgrafo induzido é igual à ordem do maior clique daquele subgráfico ( número do clique ). Declarado de forma equivalente em termos simbólicos, um gráfico arbitrário é perfeito se e somente se para tudo o que temos .
Os gráficos perfeitos incluem muitas famílias importantes de gráficos e servem para unificar resultados relacionando cores e cliques nessas famílias. Por exemplo, em todos os gráficos perfeitos, o gráfico de coloração problema , problema máximo camarilha e máxima problema conjunto independente podem ser resolvidos em tempo polinomial . Além disso, vários teoremas mín-máx importantes em combinatória , como o teorema de Dilworth , podem ser expressos em termos da perfeição de certos gráficos associados.
Um gráfico é 1 perfeito se e somente se . Então, é perfeito se e somente se cada subgrafo de for 1-perfeito.
Propriedades
- Pelo teorema do gráfico perfeito , um gráfico é perfeito se e somente se seu complemento for perfeito.
- Pelo teorema do gráfico perfeito forte , os gráficos perfeitos são iguais aos gráficos de Berge, que são gráficos onde nem e nem contém um ciclo induzido de comprimento ímpar 5 ou mais.
Consulte a seção abaixo para obter mais detalhes.
História
A teoria dos grafos perfeitos desenvolvida a partir de um resultado de Tibor Gallai em 1958 que na linguagem moderna pode ser interpretada como afirmando que o complemento de um grafo bipartido é perfeito; este resultado também pode ser visto como um equivalente simples do teorema de Kőnig , um resultado muito anterior relacionando correspondências e coberturas de vértices em grafos bipartidos. O primeiro uso da frase "gráfico perfeito" parece ser em um artigo de 1963 de Claude Berge , que deu nome aos gráficos de Berge. Neste artigo, ele unificou o resultado de Gallai com vários resultados semelhantes, definindo gráficos perfeitos, e conjeturou a equivalência do gráfico perfeito e as definições de gráfico de Berge; sua conjectura foi provada em 2002 como o teorema do gráfico perfeito forte .
Famílias de gráficos que são perfeitos
Alguns dos gráficos perfeitos mais conhecidos são:
- Grafos bipartidos , que são gráficos que podem ser coloridos com duas cores, incluindo florestas (gráficos sem ciclos).
- Gráficos lineares de gráficos bipartidos (ver teorema de Kőnig ). Os gráficos de Rook (gráficos de linha de gráficos bipartidos completos ) são um caso especial.
-
Gráficos de acordes , os gráficos em que cada ciclo de quatro ou mais vértices possui um acorde , uma aresta entre dois vértices que não são consecutivos no ciclo. Esses incluem
- florestas, k -árvores (gráficos máximos com uma determinada largura de árvore ),
- gráficos de divisão (gráficos que podem ser particionados em um clique e um conjunto independente),
- gráficos de blocos (gráficos em que cada componente bicconectado é um clique),
- Gráficos ptolomaicos (gráficos cujas distâncias obedecem à desigualdade de Ptolomeu ),
- gráficos de intervalo (gráficos em que cada vértice representa um intervalo de uma linha e cada aresta representa uma interseção não vazia entre dois intervalos),
- gráficos trivialmente perfeitos ( gráficos de intervalo para intervalos aninhados), gráficos de limite (gráficos em que dois vértices são adjacentes quando seu peso total excede um limite numérico),
- gráficos de moinho de vento (formados pela união de cliques iguais em um vértice comum),
- e gráficos de acordes fortes ( gráficos de acordes em que cada ciclo par de comprimento seis ou mais tem um acorde ímpar).
-
Gráficos de comparabilidade formados a partir de conjuntos parcialmente ordenados conectando pares de elementos por uma aresta sempre que estiverem relacionados na ordem parcial. Esses incluem:
- gráficos bipartidos, complementos de gráficos de intervalo, gráficos trivialmente perfeitos, gráficos de limiar, gráficos de moinho de vento,
- gráficos de permutação (gráficos em que as arestas representam pares de elementos que são revertidos por uma permutação),
- e cografias (gráficos formados por operações recursivas de união disjunta e complementação).
-
Gráficos perfeitamente ordenáveis , que são gráficos que podem ser ordenados de forma que um algoritmo de coloração ganancioso seja ótimo em cada subgrafo induzido. Estes incluem os gráficos bipartidos, os gráficos cordais, os gráficos de comparabilidade,
- gráficos hereditários de distância (em que as distâncias de caminho mais curto em subgráficos induzidos conectados são iguais àquelas em todo o gráfico),
- e gráficos de roda com um número ímpar de vértices.
- Grafos trapézios , que são gráficos de interseção de trapézios cujos pares paralelos de arestas estão em duas linhas paralelas. Isso inclui os gráficos de intervalo, gráficos trivialmente perfeitos, gráficos de limiar, gráficos de moinho de vento e gráficos de permutação; seus complementos são um subconjunto dos gráficos de comparabilidade.
Relação com teoremas min-max
Em todos os gráficos, o número do clique fornece um limite inferior para o número cromático, já que todos os vértices em um clique devem receber cores distintas em qualquer coloração apropriada. Os gráficos perfeitos são aqueles para os quais esse limite inferior é restrito, não apenas no gráfico em si, mas em todos os seus subgráficos induzidos. Para gráficos que não são perfeitos, o número cromático e o número do clique podem ser diferentes; por exemplo, um ciclo de comprimento cinco requer três cores em qualquer coloração adequada, mas seu maior clique tem tamanho dois.
Uma prova de que uma classe de grafos é perfeita pode ser vista como um teorema min-max: o número mínimo de cores necessárias para esses grafos é igual ao tamanho máximo de um clique. Muitos teoremas mín-máx importantes em combinatória podem ser expressos nesses termos. Por exemplo, o teorema de Dilworth afirma que o número mínimo de cadeias em uma partição de um conjunto parcialmente ordenado em cadeias é igual ao tamanho máximo de uma anticadeia e pode ser reformulado afirmando que os complementos dos gráficos de comparabilidade são perfeitos. O teorema de Mirsky afirma que o número mínimo de antichains em uma partição em antichains é igual ao tamanho máximo de uma cadeia e corresponde da mesma forma à perfeição dos gráficos de comparabilidade.
A perfeição dos gráficos de permutação é equivalente à afirmação de que, em cada sequência de elementos ordenados, o comprimento da subsequência decrescente mais longa é igual ao número mínimo de sequências em uma partição em subsequências crescentes. O teorema de Erdős – Szekeres é uma consequência fácil desta afirmação.
O teorema de Kőnig na teoria dos grafos afirma que uma cobertura mínima de vértices em um grafo bipartido corresponde a um casamento máximo e vice-versa; pode ser interpretado como a perfeição dos complementos dos grafos bipartidos. Outro teorema sobre grafos bipartidos, que seu índice cromático é igual a seu grau máximo , é equivalente à perfeição dos grafos lineares de grafos bipartidos.
Caracterizações e teoremas do gráfico perfeito
Em seu trabalho inicial com gráficos perfeitos, Berge fez duas conjecturas importantes sobre sua estrutura, que só foram comprovadas mais tarde.
O primeiro desses dois teoremas foi o teorema do gráfico perfeito de Lovász (1972), afirmando que um gráfico é perfeito se e somente se seu complemento for perfeito. Assim, a perfeição (definida como a igualdade do tamanho máximo do clique e do número cromático em cada subgrafo induzido) é equivalente à igualdade do tamanho máximo do conjunto independente e do número de cobertura do clique.
O segundo teorema, conjecturado por Berge, forneceu uma caracterização de grafos proibida de grafos perfeitos. Um ciclo induzido de comprimento ímpar de pelo menos 5 é chamado de buraco ímpar . Um subgrafo induzido que é o complemento de um furo ímpar é chamado de anti- furo ímpar . Um ciclo ímpar de comprimento maior que 3 não pode ser perfeito, porque seu número cromático é três e seu número de clique é dois. Da mesma forma, o complemento de um ciclo ímpar de comprimento 2 k + 1 não pode ser perfeito, porque seu número cromático é k + 1 e seu número de clique é k . (Alternativamente, a imperfeição deste gráfico decorre do teorema do gráfico perfeito e da imperfeição do ciclo ímpar complementar). Como esses gráficos não são perfeitos, todo gráfico perfeito deve ser um gráfico de Berge , um gráfico sem buracos ímpares e sem anti-furos ímpares. Berge conjecturou o contrário, que todo gráfico de Berge é perfeito. Isso foi finalmente provado como o teorema do gráfico perfeito forte de Chudnovsky , Robertson , Seymour e Thomas (2006). Isso implica trivialmente o teorema do gráfico perfeito, daí o nome.
O teorema do gráfico perfeito tem uma prova curta, mas a prova do teorema do gráfico perfeito forte é longa e técnica, baseada em uma decomposição estrutural profunda dos grafos de Berge. Técnicas de decomposição relacionadas também deram frutos no estudo de outras classes de grafos, e em particular para os grafos sem garras .
Existe um terceiro teorema, novamente devido a Lovász, que foi originalmente sugerido por Hajnal . Afirma que um gráfico é perfeito se os tamanhos do maior clique e do maior conjunto independente, quando multiplicados juntos, igualam ou excedem o número de vértices do gráfico, e o mesmo é verdadeiro para qualquer subgrafo induzido. É uma consequência fácil do teorema do gráfico perfeito forte, enquanto o teorema do gráfico perfeito é uma consequência fácil dele.
A caracterização de Hajnal não é atendida por n- ciclos ímpares ou seus complementos para n > 3 : o ciclo ímpar em n > 3 vértices tem número de cliques 2 e número de independência ( n - 1) / 2 . O inverso é verdadeiro para o complemento, portanto, em ambos os casos, o produto é n - 1 .
Algoritmos em gráficos perfeitos
Em todos os gráficos perfeitas, o gráfico da coloração problema , problema máximo facção , e máxima problema conjunto independente podem ser resolvidos em tempo polinomial ( Grötschel, Lovász & Schrijver 1988 ). O algoritmo para o caso geral envolve o número de Lovász desses grafos, que (para o complemento de um dado grafo) está imprensado entre o número cromático e o número do clique. O cálculo do número de Lovász pode ser formulado como um programa semidefinido e aproximado numericamente em tempo polinomial usando o método elipsóide para programação linear . Para gráficos perfeitos, arredondar esta aproximação para um inteiro dá o número cromático e o número do clique em tempo polinomial; o conjunto máximo independente pode ser encontrado aplicando a mesma abordagem ao complemento do gráfico. No entanto, esse método é complicado e tem um expoente polinomial alto. Algoritmos combinatórios mais eficientes são conhecidos para muitos casos especiais.
Por muitos anos, a complexidade de reconhecer gráficos de Berge e gráficos perfeitos permaneceu em aberto. Da definição dos grafos de Berge, segue-se imediatamente que seu reconhecimento está em co-NP (Lovász 1983). Finalmente, após a prova do teorema do gráfico perfeito forte, um algoritmo de tempo polinomial foi descoberto por Chudnovsky, Cornuéjols, Liu, Seymour e Vušković.
Referências
- Berge, Claude (1961). "Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind". Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe . 10 : 114.
- Berge, Claude (1963). "Gráficos perfeitos". Seis artigos sobre teoria de grafos . Calcutá: Instituto de Estatística Indiano. pp. 1-21.
- Chudnovsky, Maria ; Cornuéjols, Gérard ; Liu, Xinming; Seymour, Paul ; Vušković, Kristina (2005). "Reconhecendo gráficos Berge" . Combinatorica . 25 (2): 143–186. doi : 10.1007 / s00493-005-0012-8 . S2CID 2229369 .
- Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2006). "Teorema do gráfico perfeito forte" . Annals of Mathematics . 164 (1): 51–229. arXiv : math / 0212070 . doi : 10.4007 / annals.2006.164.51 . S2CID 119151552 .
- Gallai, Tibor (1958). "Máximo-mínimo Sätze über Graphen" . Acta Mathematica Academiae Scientiarum Hungaricae . 9 (3–4): 395–434. doi : 10.1007 / BF02020271 . S2CID 123953062 .
- Golumbic, Martin Charles (1980). Teoria Algorítmica dos Grafos e Gráficos Perfeitos . Academic Press. ISBN 0-444-51530-5. Arquivado do original em 22/05/2010 . Página visitada em 2007-11-21 . Segunda edição, Annals of Discrete Mathematics 57, Elsevier, 2004.
- Grötschel, Martin ; Lovász, László ; Schrijver, Alexander (1988). Algoritmos geométricos e otimização combinatória . Springer-Verlag. Veja especialmente o capítulo 9, "Stable Sets in Graphs", pp. 273–303.
- Lovász, László (1972). "Hipergrafos normais e a conjectura do gráfico perfeito" . Discrete Mathematics . 2 (3): 253–267. doi : 10.1016 / 0012-365X (72) 90006-4 .
- Lovász, László (1972). “Uma caracterização de gráficos perfeitos” . Journal of Combinatorial Theory . Series B. 13 (2): 95–98. doi : 10.1016 / 0095-8956 (72) 90045-7 .
- Lovász, László (1983). "Gráficos perfeitos". Em Beineke, Lowell W .; Wilson, Robin J. (eds.). Tópicos selecionados em teoria de grafos, vol. 2 . Academic Press. pp. 55–87. ISBN 0-12-086202-6.
links externos
- O Teorema do Grafo Perfeito Forte, de Václav Chvátal .
- Problemas abertos em gráficos perfeitos , mantidos pelo American Institute of Mathematics .
- Perfect Problems , mantido por Václav Chvátal.
- Sistema de informação em inclusões de classes de gráficos : gráfico perfeito