Busca avançada
Ano de início
Entree

Partição em caminhos e conjuntos independentes em digrafos

Processo: 17/21345-7
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de abril de 2018
Vigência (Término): 30 de junho de 2019
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Candida Nunes da Silva
Beneficiário:Lucas Rigo Yoshimura
Instituição-sede: Centro de Ciências em Gestão e Tecnologia (CCGT). Universidade Federal de São Carlos (UFSCAR). Campus de Sorocaba. Sorocaba , SP, Brasil
Assunto(s):Teoria dos grafos   Dígrafos

Resumo

Este projeto tem como tema a relação entre partições em caminhos e conjuntos independentes em digrafos. Dizemos que uma partição dos vértices em caminhos direcionados em um digrafo e um conjunto independente são \emph{ortogonais} se cada caminho da partição tem precisamente um vértice do conjunto independente. Em 1960, Gallai e Milgram demonstraram que uma partição em caminhos com o menor número possível de caminhos em um digrafo sempre é ortogonal a algum conjunto independente do digrafo. Sendo assim, o menor número de caminhos necessários para cobrir todos os vértices em uma partição em caminhos, denotado por $\pi$, é um limite inferior para o tamanho do maior conjunto independente do digrafo, denotado por $\alpha$. Posteriormente, em 1982, Berge propôs uma conjectura que estende a observação de Gallai e Milgram para uma noção mais generalizada de minimalidade em partições em caminhos e $k$-colorações em digrafos. Dado um $k$ inteiro e positivo, Berge propôs uma nova métrica de minimalidade de uma partição em caminhos em função de $k$, e buscou com sua conjectura relacioná-la ao maior número de vértices que podem ser coloridos com $k$ cores de forma que cada conjunto independente seja ortogonal à partição em caminhos. O Teorema de Gallai e Milgram é um caso particular da Conjectura de Berge, no qual $k=1$. O objetivo desta iniciação científica é estudar essa antiga conjectura de Berge e entender os resultados parciais conhecidos até o momento, aprofundando este estudo no caso $k=1$, o mais importante resolvido. Para $k=1$ existe algoritmo polinomial conhecido, derivado do Teorema de Gallai e Milgram, para encontrar a partição em caminhos ótima e um conjunto independente ortogonal à mesma. (AU)