Essa é uma revisão anterior do documento!
Ponte
Definição
Uma ponte é uma aresta tal que a deleção dela aumenta a quantidade de componentes conexas no grafo.
No desenho abaixo as arestas vermelhas são pontes:
Grafos Perfeitos
Conforme discutido na seção 5.2, um número cromático alto pode ocorrer como um fenômeno puramente global: mesmo quando um grafo tem uma circunferência grande e, portanto, se parece localmente com uma árvore, seu número cromático pode ser arbitrariamente alto. Como essa 'dependência global' é obviamente difícil de lidar, pode-se interessar por grafos onde esse fenômeno não ocorre, ou seja, cujo número cromático é alto apenas quando há uma razão local para isso.
Antes de tornar isso preciso, vamos definir dois novos invariantes para um grafo G. O maior inteiro K tal que K é o número clique W de G, e o maior inteiro K tal que K (induzido) é o número de independência K de G . Claramente, K e K.
Um grafo é dito perfeito se todo subgrafo induzido H tem número cromático X, ou seja, se o limite inferior trivial de H cores sempre é suficiente para colorir os vértices de H. Assim, ao provar uma afirmação da forma X pode em geral ser difícil, mesmo em princípio, para um dado grafo G, isso sempre pode ser feito para um grafo perfeito simplesmente exibindo algum K subgrafo como um 'certificado' de não colorabilidade com K cores.
À primeira vista, a estrutura da classe dos grafos perfeitos parece um tanto artificial: embora seja fechada sob subgrafos ou supergrafos gerais, quanto mais menores. No entanto, a perfeição é uma noção importante na teoria dos grafos: o fato de várias classes fundamentais de grafos serem perfeitas (como por acaso) pode servir como uma indicação superficial disso. (A classe do grafo perfeito tem propriedades de dualidade com conexões profundas com a otimização e a teoria da complecidade, que estão longe de serem compreendidas. O teorema 5.5.6 mostra a ponta de um iceberg aqui; para mais, o leitor deve consultar a pesquisa de Lovasz citada nas notas .)
Quais gráficos, então, são perfeitos? Grafos bipartidos são, por exemplo. Menos trivialmente, os complementos de grafos bipartidos também são perfeitos, um fato equivalente ao teorema de dualidade de Konig 2.1.1. Os chamados gráficos de comparabilidade são perfeitos, assim como os gráficos de intervalos; ambos aparecem em inúmeras aplicações.
A fim de estudar pelo menos um desses exemplos com algum detalhe, provamos aqui que os grafos cordais são perfeitos: um grafo é cordal (ou triangulado) se cada um de seus ciclos de comprimento pelo menos 4 tiver uma corda, ou seja, se não contiver ciclos induzidos que não sejam triângulos.
Para mostrar que os grafos cordais são perfeitos, primeiro caracterizaremos sua estrutura. Se G é um grafo com subgrafos induzidos G e S tais que G e S , dizemos que G surge de G e G colando seus gráficos juntos ao longo de S.
Proposição 5.5.1
Um grafo é cordal se e somente se ele pode ser construído recursivamente colando subgrafos completos, começando de grafos completos.
Dem.:
Se G é obtido de dois grafos cordais G, G colando-os juntos ao longo de um subgrafo completo, então G é claramente novamente cordal: qualquer ciclo induzido em G reside em G ou G e, portanto, é um triângulo por suposição. Uma vez que os grafos completos são cordais, isso prova que todos os grafos construíveis conforme declarado são cordais.
Reciprocamente, seja G um grafo cordal. Mostramos por indução em G que G pode ser construído como descrito. Isso é trivial se G for completo. Portanto, assumimos que G não é completo, em particular G, e que todos os grafos cordais menores são construíveis conforme declarado. Seja G dois vértices não adjacentes, e seja X um separador B mínimo. Deixe C denotar o componente de G contendo K e G colando esses gráficos juntos ao longo de S.
Uma vez que G e G são cordais (sendo subgrafos induzidos de G) e portanto construíveis por indução, basta mostrar que S é completo. Suponha, então, que S não sejam adjacentes. Pela minimalidade de X como um separador de K, tanto S quanto T têm um vizinho em C. Portanto, existe um caminho X de S para T em G; deixamos P ser um tal caminho mais curto. Analogamente, G contém um caminho X mais curto P de S a T. Mas então P é um ciclo sem corda de comprimento 4, contraindo nossa suposição de que G é cordal.
(FIGURAAAAA
Proposição 5.5.2
Todo grafo cordal é perfeito.
Dem.:
Como grafos completos são perfeitos, basta pela Proposição 5.5.1 mostrar que qualquer grafo G obtido a partir de grafos perfeitos G colando-os juntos ao longo de um subgrafo completo S é novamente perfeito. Portanto, seja H um subgrafo induzido; mostramos que X.
Faça H para K , e deixe T. Então T é novamente completo, e H surge de H e H colando ao longo de T. Como um subgrafo induzido de G, cada H pode ser colorido com W cores. Uma vez que T é completo e, portanto, colorido injetadamente, duas dessas colorações, uma de H e uma de H, podem ser combinadas em uma coloração de H com M cores, se necessário, permutando as cores em um dos H.
Por definição, todo subgrafo induzido de um grafo perfeito é asiático perfeito. A propriedade de perfeição pode, portanto, ser caracterizada por subgrafos induzidos proibidos: existe um conjunto H de grafos imperfeitos tal que qualquer grafo é perfeito se e somente se não possui subgrafo induzido isomórfico a um elemento de H. (Por exemplo, podemos escolher como H o conjunto de todos os grafos imperfeitos com vértices em N.)
Naturalmente, gostaríamos de manter H o menor possível. É um dos resultados mais profundos da teoria dos grafos que H precisa conter apenas dois tipos de grafos: os ciclos ímpares de comprimento 5 e seus complementos. (Nenhum deles é perfeito; cf. Teorema 5.5.4 abaixo). Este fato, a famosa conjectura do grafo perfeito forte de Berge, foi provado apenas muito recentemente:
Teorema 5.5.3 (Chudnovsky, Robertson, Seymour & Thomas)
Um grafo G é perfeito se e somente se nem G nem G contém um ciclo ímpar de tamanho pelo menos 5 como um subgrafo induzido.
No contexto de grafos perfeitos, ciclos induzidos de comprimento de pelo menos 5 em G são geralmente referidos como buracos em G, enquanto buracos em G são antiburacos de G. Nesse jargão, o teorema do grafo perfeito forte diz que um grafo é perfeito se e somente se não tiver furos nem antiburacos.
A prova do teorema do grafo perfeito forte é longa e técnica, e não seria muito esclarecedor tentar esboçá-la. Para lançar mais luz sobre a noção de perfeição, damos duas provas diretas de sua consequência mais importante: o teorema do grafo perfeito, anteriormente a conjectura do grafo perfeito fraco de Berge:
Teorema 5.5.4 (Lovász)
Um grafo é perfeito se e somente se seu complemento é perfeito.
A primeira prova que damos para o Teorema 5.5.4 é a prova original de Lovász, que ainda é insuperável em sua clareza e quantidade de 'sensação' do problema que transmite. Nossa segunda prova, devido a Gasparian, é uma elegante prova de álgebra linear de outro teorema de Lovász (teorema 5.5.6), que facilmente implica o Teorema 5.5.4.
Preparemos nossa primeira prova do Teorema 5.5.4 por meio de um lema. Seja G um grafo e X um vértice, e seja G obtido de G adicionando um vértice X e unindo-o a X e todos os vizinhos de X. Dizemos que G é obtido de G expandindo o evrtex X para uma aresta X.
(FIGURAAAAA
Lema 5.5.5
Qualquer grafo obtido de um grafo perfeito pela expansão de um vértice é novamente perfeito.
Dem.:
Usamos indução na ordem do grafo perfeito desejado. expandir o vértice de K produz K, que é perfeito. Para o passo de indução, seja G um grafo perfeito não trivial , e seja G obtido de G expandindo um vértice G para uma aresta X. Para nossa prova de que G é perfeito basta mostrar X: todo subgrafo induzido próprio H de G é isomórfico a um subgrafo induzido de G ou obtido de um subgrafo induzido adequado de G pela expansão de X; em ambos os casos, H é perfeito por suposição e hipótese de indução e, portanto, pode ser colorido com cores W.
Seja W; então W. Se W, então X e terminamos. Então, vamos assumir que W. Então X não está em K: junto com X, isso produziria um K em G. Vamos colorir G com W cores. Como todo K atende à classe de cor X de X, mas não ao próprio X, o grafo H tem número de clique W.
(FIGURAAAA
Uma vez que G é perfeito, podemos esta cor H com cores W. Agora X é independente, então o conjunto X também é independente. Podemos, portanto, estender nossa coloração W de H para uma coloração W de G, mostrando que X é desejado.
Dem. Teorem 5.5.4
Aplicando indução em G, mostramos que o complemento G de qualquer grafo perfeito G é novamente perfeito. Para G isso é trivial, então seja G para a etapa de indução. Seja K o conjunto de todos os conjuntos de vértices de subgrafos completos de G. Coloque K e seja K o conjunto de todos os conjuntos de vértices independentes K em G com K.
Todo subgrafo induzido próprio de G é o complemento de um subgrafo induzido próprio de G e, portanto, é perfeito por indução. Para a perfeição de G basta provar X. Para isso, encontraremos um conjunto K tal que K para todo K; então W, então pela hipótese de indução X, conforme desejado.
Suponha que não exista tal K; assim, para todo K existe um conjunto K com K. Substituamos em G todo vértice X por um grafo completo G de ordem H, unindo todos os vértices de G a todos os vértices de G sempre que X e Y forem adjacentes em G . O grafo G assim obtido tem um conjunto de vértices V, e dois vértices V e W são adjacentes em G se e somente se X ou X. Além disso, G pode ser obtido por expansão repetida de vértices do grafo G. sendo um subgrafo induzido de G , este último grafo é perfeito por suposição, então G é perfeito pelo Lema 5.5.5. Em particular, W.
Suponha que não exista tal K; assim, para todo K existe um conjunto K com K. Substituamos em G todo vértice X por um grafo completo G de ordem H, unindo todos os vértices de G a todos os vértices de G sempre que X e Y forem adjacentes em G . O grafo G assim obtido tem um conjunto de vértices V, e dois vértices V e W são adjacentes em G se e somente se X ou X. Além disso, G pode ser obtido por expansão repetida de vértices do grafo G. sendo um subgrafo induzido de G , este último grafo é perfeito por suposição, então G é perfeito pelo Lema 5.5.5. Em particular, W.
Como G pela construção de G, isso implica X.
Juntando K e K, obtemos X, uma contradição de K.
À primeira vista, a prova do Teorema 5.5.4 parece mágica: começa com um lema não motivado sobre a expansão de um vértice, desloca o problema para um estranho grafo G obtido dessa maneira, faz uma dupla contagem e termina. Olhando para trás, no entanto, podemos entender um pouco melhor.
A prova é completamente natural até o ponto em que supomos que para todo K existe um K tal que K. Para mostrar que isso contradiz nossa suposição de que G é perfeito, gostaríamos de mostrar a seguir que seu subgrafo G induzido por todos os K tem um número cromático muito grande, maior que seu número clique. E, como sempre quando tentamos limitar o número cormático por baixo, nossa única esperança é limitar G, ou seja, mostrar que este é maior que W.
Mas é provável que o limite de G reflita o verdadeiro valor de X? Em um caso especial é: se os conjuntos K são disjuntos, temos G e X, com K como classes de cores. Como todo subgrafo completo de G encontra cada K no máximo uma vez e perde seu próprio K, então temos W com a contradição desejada.
É claro que os conjuntos K em geral não serão disjuntos. Mas podemos fazer isso: substituindo cada vértice X por K vértices, onde K é o número de conjuntos K em que ele vive ! Esta é a ideia por trás de G. O que resta é dotar G com o conjunto certo de arestas para torná-lo perfeito (supondo que G seja perfeito), o que leva diretamente à definição de expansão verteca e ao Lema 5.5.5.
Uma vez que a seguinte caracterização de perfeição é simétrica em G e G, ela implica claramente no Teorema 5.5.4. Como nossa prova do Teorema 5.5.6 será novamente a partir dos primeiros princípios, obtemos assim uma segunda prova independente do Teorema 5.5.4.
teorema 5.5.6 (Lovász)
Um grafo G é perfeito se, e somente se, H para todo subgrafo induzido H.
Dem.:
Pelo teorema 5.2.5, não podemos forçar um subgrafo K , mesmo para K, tornando o número cromático de um grafo suficientemente grande. No entanto, isso pode ser possível para gráficos com certas propriedades especificadas, que podem, por sua vez, dar alguma importância a essas propriedades que, de outra forma, não teriam. Por exemplo, os grafos sem buraco ímpar ou antiburaco parecem uma classe estranha para estudar. Mas o fato de que, pelo teorema do grafo perfeito forte, grafos de número cromático K nesta classe possuem K subgrafos, torna-os interessantes: alto número cromático, para grafos desta classe, sempre terá uma razão local.
De forma um pouco mais geral, uma classe G de grafos é chamada limitada por X se existe uma função F tal que X para cada grafo G em G. Em tais grafos, então, podemos forçar um subgrafo K tornando X maior que F.
Teorem 5.5.7
(i) O gráfico sem buracos ímpares é limitado por X com F.
(ii) Para cada inteiro K, o grafo sem furos de comprimento K são limitados por X.