"A Transversalidade da Ciência, Tecnologia e Inovações para o Planeta"
5 a 7 de outubro de 2021
Trabalho 15011
| ISSN | 2237-9045 |
|---|---|
| Instituição | Universidade Federal de Viçosa |
| Nível | Graduação |
| Modalidade | Pesquisa |
| Área de conhecimento | Ciências Exatas e Tecnológicas |
| Área temática | Matemática Aplicada |
| Setor | Instituto de Ciências Exatas e Tecnológicas - Campus Florestal |
| Conclusão de bolsa | Não |
| Primeiro autor | Luan Moises dos Santos Valadares |
| Orientador | SERGIO HENRIQUE NOGUEIRA |
| Título | Separadores de vértices em grafos cordais |
| Resumo | Neste trabalho estudamos propriedades de separadores de vértices em grafos cordais e uma caracterização de subclasses de grafos cordais por subgrafos induzidos proibidos. Este projeto teve como objetivo estudar os conceitos fundamentais de grafos, dentre os quais podemos destacar grafos, caminhos, ciclos e classes de grafos e por fim resultados relevantes sobre separadores de vértices. O projeto permitiu o desenvolvimento dos conhecimentos na área de Teoria de Grafos. Durante todo o projeto houve o estudo individual feito pelo orientando, depois disso eram feitos encontros semanais com o orientador. No início dos trabalhos, foram feitos estudos de definições básicas de teoria dos grafos, após isso foram estudados resultados relevantes na área. O trabalho se iniciou com as definições dentro da teoria de grafos que seriam importantes para o entendimento, como por exemplo grafos simples, subgrafos induzidos e cliques. Uma das partes importantes no estudo foi o estudo de uma classe de grafos, os grafos cordais. Um grafo G é um grafo cordal se todo ciclo de comprimento maior que três tiver uma corda. Uma corda é uma aresta que conecta dois vértices não consecutivos no ciclo. Na teoria dos grafos, dados dois vértices vi, vj ∈ V(G) é interessante avaliar se existe um caminho de vi para vj. Um conjunto S ⊂ V(G) desconecta dois vértices u e v em G se todo caminho em G entre u e v contiver algum vértice de S. Um conjunto não vazio S ⊂ V(G) é um separador minimal de vértices de G se houver u e v tais que S desconecta u e v em G e nenhum subconjunto próprio de S desconecta u e v em G. Uma caracterização importante dos grafos cordais deve-se a Dirac: Um grafo G é cordal se e somente se cada separador mínimal de vértices de G é uma clique, em que clique é um grafo completo. Duas cliques C1, C2 de G formam um par separador se C1 ∩ C2 não é vazio, e todo caminho em G de um vértice de C1\C2 a um vértice de C2\C1 contém um vértice de C1 ∩ C2 e temos um teorema: Um conjunto S é um separador minimal de vértices de um grafo cordal G se e somente se houver cliques C1,C2 de G formando par separador tal que S= C1 ∩ C2. Uma clique tree de um grafo cordal é uma árvore T cujos vértices são as cliques de G tais que para cada duas cliques Ci,Cj cada clique no caminho de Ci para Cj em T contém Ci ∩ Cj. Um grafo cordal também pode ser caracterizado usando clique tree como segue: um grafo é cordal se e somente se tiver uma Clique tree. Por fim, foi estudado um resultado de caracterização de subclases de grafos cordais por subgrafos induzidos proibidos, através das relações entres os pares separadores de vértices. Este resultado estuda como as possíveis relações entre dois separadores minimais podem ser usadas para caracterizar subclasses de grafos cordais por subgrafos induzidos proibidos. Ademais, apesar de ser um estudo introdutório na área de Teoria dos Grafos, este projeto possibilitou olhares para futuros estudos na área. |
| Palavras-chave | Grafos cordais, Separadores de vértices, Clique tree |
| Forma de apresentação..... | Vídeo |
| Link para apresentação | Vídeo |
|---|