Grafos de Intervalo: Caracterizações, Problemas e Algoritmos

O estudo dos grafos perfeitos, grafos cujos subgrafos induzidos possuem número cromático e tamanho de clique máxima iguais, necessariamente deve incluir estudos sobre muitas subclasses importantes : grafos de comparabilidade, grafos triangularizados, grafos de permutação, "threshold graphs" e grafos de intervalo, para citar apenas algumas .

O objetivo desta dissertação é fazer uma resenha, tão completa quanto possível , de uma destas subclasses , os chamados grafos de intervalo , grafos isomorfos a um conjunto de intervalos.

Este trabalho se divide essencialmente em três partes. A primeira parte se dedica a coletar as caracterizações mais importantes e Úteis (de um ponto de v i s t a algorítmico) dos grafos de intervalo (Capítulo 2) e dos grafos de indiferença (Capitulo 3), uma conhecida subclasse dos grafos de intervalo na qual os grafos podem ser representados por modelos onde todos os intervalos têm o mesmo comprimento.

A segunda parte trata de problemas em teoria dos grafos restritos ao caso dos grafos de intervalo: Reconhecimento e Isomorfismo (Capítulo 4), Conjunto Independente Máxi mo, Cobertura Mínima por Cliques , Coloração Mínima, Caminho Hamiltoniano, Circuito Hamiltoniano, Conjunto Dominante Minimo, entre outros (Capítulo 5). Os algoritmos propostos para a solução destes e de outros problemas, como é lógico, fazem largo uso das caracterizações previamente descritas e de propriedades matemáticas afins satisfeitas pela estrutura dos grafos de intervalo. Estas caracterizações e propriedades permitem-nos reduzir a complexidade de tempo requerido. para a solução de problemas que, para grafos em geral, exigem complexidades maiores - muitos deles NP-completos.

Finalmente, a terceira parte contém alguns tópicos relacionados com o estudo dos grafos perfeitos: o número de intervalo, o "interval count", hipergrafos de intervalo, grafos de intersecção e dígrafos de intervalo.