CONVEXIDADE EM GRAFOS ORIENTADOS
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
Licença
Autores que publicam nesta revista concordam com os seguintes termos:
a. Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Creative Commons Attribution License que permitindo o compartilhamento do trabalho com reconhecimento da autoria do trabalho e publicação inicial nesta revista.
b. Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
c. Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado.