Partição em Caminhos e Conjuntos Independentes em Digrafos

Resumo

Este projeto tem como tema a relação entre partições em caminhos econjuntos independentes em digrafos. Dizemos que uma partição dosvértices em caminhos direcionados em um digrafo e um conjuntoindependente são \emph{ortogonais} se cada caminho da partição temprecisamente um vértice do conjunto independente. Em 1960, Gallai eMilgram demonstraram que uma partição em caminhos com o menor númeropossível de caminhos em um digrafo sempre é ortogonal a algum conjuntoindependente do digrafo. Sendo assim, o menor número de caminhosnecessários para cobrir todos os vértices em uma partição em caminhos,denotado por $\pi$, é um limite inferior para o tamanho do maiorconjunto independente do digrafo, denotado por $\alpha$.Posteriormente, em 1982, Berge propôs uma conjectura que estende aobservação de Gallai e Milgram para uma noção mais generalizada deminimalidade em partições em caminhos e $k$-colorações em digrafos.Dado um $k$ inteiro e positivo, Berge propôs uma nova métrica deminimalidade de uma partição em caminhos em função de $k$, e buscoucom sua conjectura relacioná-la ao maior número de vértices que podemser coloridos com $k$ cores de forma que cada conjunto independenteseja ortogonal à partição em caminhos. O Teorema de Gallai e Milgram éum caso particular da Conjectura de Berge, no qual $k=1$. O objetivodesta iniciação científica é estudar essa antiga conjectura de Berge eentender os resultados parciais conhecidos até o momento, aprofundandoeste estudo no caso $k=1$, o mais importante resolvido. Para $k=1$existe algoritmo polinomial conhecido, derivado do Teorema de Gallai eMilgram, para encontrar a partição em caminhos ótima e um conjuntoindependente ortogonal à mesma.