Introdução à Teoria dos Grafos com aspectos computacionais e convexidade de grafos
| dc.contributor.advisor1 | SILVA, Rômulo Luiz Oliveira da | |
| dc.contributor.advisor1Lattes | http://lattes.cnpq.br/8265719000886842 | pt_BR |
| dc.contributor.advisor1ORCID | https://orcid.org/0000-0001-6255-8016 | pt_BR |
| dc.creator | MELÉM, Breno Roberto Mota Guedes | |
| dc.creator.Lattes | http://lattes.cnpq.br/6466903362612123 | pt_BR |
| dc.date.accessioned | 2026-05-21T02:02:11Z | |
| dc.date.available | 2026-05-21T02:02:11Z | |
| dc.date.issued | 2025-12-18 | |
| dc.description.abstract | Graph Theory constitutes an extremely rich source of both practical and theoretical problems. These problems often have simple statements, but they frequently hide complex mathematical structures that require careful modeling. Several problems arising from real-world applications can be represented by means of graphs. However, many of these challenges belong to the class of NP-hard problems, which means that, unless P = NP, no efficient algorithms are known to solve them in general. In order to discuss the main classes of graphs—Bipartite Graphs, Chordal Graphs, Inflated Graphs, Eulerian and Hamiltonian Graphs—this work aims to serve as a foundation for new researchers beginning their scientific development in the area. In this study, we establish the theoretical bases necessary for examining the topics addressed, with emphasis on characterization theorems. We discuss graph convexity, presenting its main parameters and relating it to classical convexity. We also analyze aspects of computational complexity and, finally, explore the class of graphs introduced recently, in 2022, known as clique-expanded graphs, in which H is a clique-expanded graph when it is obtained from a given graph G through an f-clique-expanded operator. If f(vi) = k for every vi ∈ V (G) and for some k ∈ N, we may say that H is a k-clique-expanded graph. | en |
| dc.description.resumo | 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 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. | pt_BR |
| dc.identifier.citation | MELÉM, Breno Roberto Mota Guedes. Introdução à Teoria dos Grafos com aspectos computacionais e convexidade de grafos. Orientador: Rômulo Luiz Oliveira da Silva. 2026. 61 f. Trabalho de Curso (Bacharelado em Ciência e Tecnologia) – Faculdade de Ciência e Tecnologia, Campus Universitário de Ananindeua, Universidade Federal do Pará, Ananindeua, 2025. Disponível em: https://bdm.ufpa.br/handle/prefix/9553. Acesso em:. | pt_BR |
| dc.identifier.uri | https://bdm.ufpa.br/handle/prefix/9553 | |
| dc.rights | Acesso Aberto | pt_BR |
| dc.source | Disponível na internet via Sagitta | pt_BR |
| dc.subject | Algoritmos | pt_BR |
| dc.subject | Grafos inflados | pt_BR |
| dc.subject | Clique-expandido | pt_BR |
| dc.subject | Complexidade | pt_BR |
| dc.subject | Convexidade | pt_BR |
| dc.subject | Algorithms | en |
| dc.subject | Inflated graphs | en |
| dc.subject | Clique-expanded | en |
| dc.subject | Complexity | en |
| dc.subject | Convexity | en |
| dc.subject.cnpq | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::MATEMATICA DA COMPUTACAO | pt_BR |
| dc.title | Introdução à Teoria dos Grafos com aspectos computacionais e convexidade de grafos | pt_BR |
| dc.type | Trabalho de Curso - Graduação - Monografia | pt_BR |