CONVEXIDADE EM GRAFOS ORIENTADOS

Resumo

Neste trabalho foi estudada a convexidade em grafos orientados, também chamados de grafos direcionados. Foi realizada a leitura de diversos artigos sobre limitantes inferiores e superiores para o número de envoltória, número geodético, número de Radon, número de Helly, número de Carathéodory e o rank de várias classes de grafos, como grafos bipartidos, cografos, grafos livres de triângulos, dentre outros. Um grafo direcionado é composto por um conjunto de vértices, geralmente representados graficamente por pontos, e por um conjunto de arestas, tal que cada arestas é associada a um par de vértices distintos, possuindo uma determinada direção, representada graficamente como uma seta. Também foram analisados artigos que tratam sobre algoritmos de redução para diferentes problemas envolvendo os parâmetros citados, e sobre a análise da complexidade de problemas envolvendo esses parâmetros em grafos diversos. Finalmente, como resultado, é apresentada uma prova alternativa para o seguinte teorema: se G é um grafo conexo com n vértices, então o número de envoltória de G é igual a n se, e somente se, G for um grafo completo. Para provar isso, os grafos foram separados em dois casos: os que possuem um P4 (caminho com 4 vértices) como subgrafo induzido (se ele possuir todas as arestas que ocorrem em G incidindo sobre o mesmo conjunto de vértices) e os que não possuem P4 como subgrafo induzido, conhecidos como cografos. A partir disso é feita uma análise detalhada dos caminhos no grafo. Nota-se que esse tema é relativamente pouco explorado em trabalhos existentes e que é um campo fértil para a futura exploração e novos resultados. Agradecimentos ao CNPq pelo financiamento deste trabalho.