Transversais em grafos

Resumo

Na área de teoria dos grafos, um problema clássico consiste em encontrar um conjunto de vértices ou arestastais que todo objeto de certo tipo no grafo contém pelo menos um elemento nesse conjunto. Um tal conjunto échamado de transversal, e em geral buscam-se transversais pequenas, possivelmente de tamanho mínimo. Quando não se conhece o tamanho de uma transversal mínima, naturalmente torna-se interessante a busca por boasdelimitações para esse tamanho. Quando encontrar uma transversal mínima é um problema NP-difícil, buscam-se aproximações para o problema. O foco deste projeto são alguns tipos de transversais em grafos, como por exemplo transversais de caminhos mais longos, de circuitos mais longos, de circuitos ímpares e transversais de cliques maximais. O objetivo é a determinação do tamanho de transversais mínimas para estes objetos senão em grafos arbitrários, em classes específicas de grafos.