Introdução à Teoria dos Grafos com aspectos computacionais e convexidade de grafos

A 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 cliqueexpandidos 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.