"Ciências Básicas para o Desenvolvimento Sustentável"
24 a 26 de outubro de 2023
Trabalho 18280
| ISSN | 2237-9045 |
|---|---|
| Instituição | Universidade Federal de Viçosa |
| Nível | Ensino médio |
| 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 |
| Bolsa | BIC-Júnior |
| Conclusão de bolsa | Sim |
| Apoio financeiro | FAPEMIG |
| Primeiro autor | Arthur Gustavo Santos Fernandes |
| Orientador | LUIS FELIPE GONCALVES FONSECA |
| Título | Uma Introdução à Teoria dos Grafos |
| Resumo | Neste trabalho, foi feita uma introdução abrangente dos fundamentos da teoria dos grafos. Foi utilizado, principalmente, uma apostila da Obmep do professor Samuel Jurkiewicz, Grafos – Uma Introdução, volume 5. A nossa pesquisa abordou conceitos essenciais dos grafos. Foram promovidos encontros semanais entre o orientador e o orientando. Além de explorar temas específicos, como grafos eulerianos, grafos hamiltonianos, grafos planares, árvores, o trabalhou fez uma incursão em assuntos clássicos da teoria dos grafos, tais como o Problema das Pontes de Königsberg, o Problema do Caixeiro Viajante, o Problema do Carteiro Chinês e o Teorema das Quatro Cores. Problema das Pontes de Königsberg: Este é um problema histórico que deu origem à teoria dos grafos. A cidade de Königsberg na Prússia (hoje Kaliningrado, Rússia) tinha sete pontes, e o desafio era passear pela cidade cruzando cada ponte uma única vez e retornar ao ponto de partida. O matemático Leonhard Euler provou que isso era impossível, formando a base da teoria dos grafos e criando o conceito de grafo euleriano. Problema do Caixeiro Viajante: Este é um problema clássico de otimização combinatória. O desafio é encontrar a rota mais curta que um caixeiro viajante deve tomar para visitar um determinado número de cidades e retornar à sua cidade de origem, visitando cada cidade apenas uma vez. O problema é NP-difícil, o que significa que não há uma solução rápida conhecida para encontrar a rota mais curta entre um grande número de cidades. Problema do Carteiro Chinês: Este é um problema de otimização de rota em que se procura encontrar o caminho mais curto que passa por cada aresta de um grafo pelo menos uma vez e retorna ao ponto de partida. Este problema difere do problema das pontes de Königsberg porque permite passar por uma mesma aresta mais de uma vez. Teorema das Quatro Cores: Este teorema afirma que, dado qualquer mapa plano, é possível colorir as regiões do mapa de tal forma que nenhuma região compartilha uma fronteira com outra região da mesma cor usando apenas quatro cores diferentes. A demonstração deste teorema foi notável por ser um dos primeiros teoremas provados usando um computador. O projeto incluiu uma breve introdução aos conceitos básicos da linguagem de programação Python. Houve a implementação do algoritmo de Dijkstra para problemas de caminho mínimo via Python. O objetivo desta etapa foi aplicar o algoritmo para problemas de roteamento de redes. Concluímos que, além da matemática, os grafos são importantes em computação, redes de telecomunicação e outras áreas do conhecimento. |
| Palavras-chave | Grafos, grafos hamiltonianos, grafos eulerianos |
| Forma de apresentação..... | Vídeo |
| Link para apresentação | Vídeo |
|---|