Navegando por Assunto "Complexidade"
Agora exibindo 1 - 1 de 1
Resultados por página
Opções de Ordenação
Trabalho de Curso - Graduação - Monografia Acesso aberto (Open Access) Introdução à Teoria dos Grafos com aspectos computacionais e convexidade de grafos(2025-12-18) MELÉM, Breno Roberto Mota Guedes; SILVA, Rômulo Luiz Oliveira da; http://lattes.cnpq.br/8265719000886842; https://orcid.org/0000-0001-6255-8016A Teoria dos grafos constitui uma fonte vastíssima de problemas, tanto práticos quanto teóricos. Esses problemas costumam ter enunciados simples, mas frequentemente escondem estruturas matemáticas complexas que exigem modelagem cuidadosa. Diversos problemas presentes em aplicações reais podem ser representados por meio de grafos. Entretanto, muitos desses desafios pertencem a classe dos problemas NP-difíceis, o que significa que, salvo se P = NP, não existem algoritmos eficientes conhecidos para resolvê-los em geral. A fim de discorrer sobre as principais classes de grafos; Grafos Bipartidos, Grafos Cordais, Grafos Inflados, grafos Euleriano, Hamiltonianos, com a finalidade para ser uma base ao novo pesquisador que visa dar início ao desenvolvimento científico dentro da área. Neste trabalho, estabelecemos as bases teóricas necessárias para o estudo dos temas abordados, com ênfase em teoremas de caracterização. Discutimos a convexidade em grafos, apresentando seus principais parâmetros e relacionando-a à convexidade clássica. Também analisamos aspectos de complexidade computacional e, por fim, exploramos a classe de grafos introduzida recentemente, em 2022, denominada clique expandidos em que H é um grafo clique-expandido quando for obtido por um processo de expansão de dado grafo G com um operador f-clique-expandido. Se f(vi) = k para todo vi ∈ V (G) e para algum k ∈ N, podemos dizer que H é um grafo k-clique-expandido.