Grafo perfeito

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido. Ajude e colabore com a tradução.
O grafo de Paley de ordem 9, colorido com três cores e mostrando uma clique de três vértices. Neste grafo e em cada um dos subgrafos induzidos o número cromático é igual ao número da clique, por isso é um grafo perfeito.

Em teoria dos grafos, um grafo perfeito é um grafo em que o número cromático de cada subgrafo induzido é igual ao tamanho da maior clique deste subgrafo.

Em qualquer grafo, o número de clique fornece um limite inferior para o número cromático, assim como todos os vértices em uma clique devem ser atribuídos cores distintas em qualquer coloração adequada. Os grafos perfeitos são aqueles para os quais este limite inferior é apertado, não apenas no grafo em si, mas em todos os seus subgrafos induzidos. Para grafos de forma mais geral, o número cromático e o número da clique podem diferir; por exemplo, um ciclo de comprimento 5, requer três cores em qualquer coloração adequada, mas a sua maior clique tem tamanho 2.

Grafos perfeitos incluem muitas famílias importantes de grafos, e servem para unificar os resultados relativos a colorações e cliques nessas famílias. Por exemplo, em todos os grafos perfeitos, o problema da coloração de grafos, o problema da clique máxima e o problema do conjunto independente máximo podem ser resolvidos em tempo polinomial[1] . Além disso, vários teoremas importantes min-max em análise combinatória, como o teorema de Dilworth, podem ser expressos em termos da perfeição de alguns grafos associados.

A teoria dos grafos perfeitos desenvolveu-se a partir um resultado de 1958 de Tibor Gallai que em linguagem moderna, pode ser interpretado como indicando que o complementar de um grafo bipartido é perfeito; este resultado também pode ser visto como um simples equivalente do teorema de König, um resultado bem mais anterior relacionando acoplamentos e coberturas de vértices em grafos bipartidos. O primeiro uso da expressão "grafo perfeito" parece estar em um artigo de 1963 de Claude Berge. Neste artigo ele unificou o resultado de Gallai com vários resultados semelhantes através da definição de grafos perfeitos e conjecturando uma caracterização destes grafos que mais tarde foi comprovado como o Teorema Forte dos Grafos Perfeitos.

Familias de grafos que são perfeitos[editar | editar código-fonte]

Alguns dos mais conhecidos grafos perfeitos são


Referências

  1. GRÖTSCHEL, Martin; LOVÁSZ, László; SCHRIJVER, Alexander. Geometric Algorithms and Combinatorial Optimization. Berlin/Nova York: Springer-Verlag, 1988. Capítulo 9, "Stable Sets in Graphs". p. 273–303.