CONVEXIDADE EM GRAFOS ORIENTADOS

Autores

  • Carolina Araujo Dias
  • Julio Cesar Silva Araujo

Resumo

Neste trabalho foi estudada a convexidade em grafos orientados (ou direcionados). Foi realizada a leitura de diversos artigos sobre limitantes inferiores e superiores para o número de envoltória e para o número geodético 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 aresta é associada a um par de vértices distintos, possuindo uma determinada direção, representada graficamente como uma seta. Também foram analisados alguns artigos que tratavam sobre algoritmos de redução para diferentes problemas envolvendo o número de envoltória e o número geodético, e sobre a análise da complexidade de problemas envolvendo esses parâmetros em grafos. 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 possui 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. Agradecimentos ao CNPq pelo financiamento deste trabalho.

Publicado

2019-01-01

Edição

Seção

XXXVIII Encontro de Iniciação Científica