Use este identificador para citar ou linkar para este item:
http://riu.ufam.edu.br/handle/prefix/6342| Tipo de documento: | Trabalho de Conclusão de Curso |
| Título: | O problema chinês do carteiro: um convite à Teoria dos Grafos |
| Autor(a): | Melo, John Wendell Labis |
| Orientador(a): | Bitar, Sandro Dimy Barbosa |
| metadata.dc.contributor.referee1: | Júnior, Mário Salvatierra |
| metadata.dc.contributor.referee2: | Bandeira, Karla Christina Tribuzy |
| Resumo: | O presente trabalho aborda o Problema Chinês do Carteiro (PCC), que é utilizado para resolver problemas de percursos fornecendo o passeio (caminho) de custo mínimo em um grafo. Este tem como objetivo convidar o leitor conhecer a Teoria dos Grafos através de um estudo do PCC. No inicio do trabalho, é abordado os fundamentos da teoria, tais como: conceitos; definições; noções entre outros, que é fundamental para qualquer estudo envolvendo a teoria. No PCC existe alguns casos de Grafos, sendo os mais comuns os casos: Grafo não Orientado; Grafo Orientado e Grafo Misto. Em cada um dos casos, o problema basicamente se resume em transformar o grafo em Euleriano e encontrar um passeio de custo mínimo percorrendo pelo menos uma vez cada aresta deste grafo através de algoritmos. Será abordado também uma formulação de Programação Linear para o PCC, com o intuito de mostrar uma outra maneira de obter a resolução de problemas desta natureza. |
| Resumo em outro idioma: | The present work addresses the Chinese Postman Problem (CCP), which is used to solve path problems by providing the least cost walk (path) in a graph. This aims to invite the reader to know the Theory of Graphs through a study of the PCC. At the beginning of the work, the fundamentals of the theory are approached, such as: concepts; Definitions; notions among others, which is fundamental for any study involving the theory. In the PCC there are some cases of Graphs, the most common cases being: Non-Oriented Graph; Oriented Graph and Mixed Graph. In each case, the problem basically boils down to transforming the graph into Eulerian and finding a minimum-cost walk through each edge of this graph at least once through algorithms. A formulation of Linear Programming for the PCC will also be discussed, in order to show another way to obtain the resolution of problems of this nature. |
| Palavras-chave: | Grafo de Euler (Euleriano) Circuito de Euler Problema Chinês do Carteiro (PCC) Grau do vértice |
| Área de conhecimento - CNPQ: | CIENCIAS EXATAS E DA TERRA MATEMATICA MATEMATICA APLICADA |
| Idioma: | por |
| País de publicação: | Brasil |
| Faculdade, Instituto ou Departamento: | ICE - Instituto de Ciências Exatas |
| metadata.dc.publisher.course: | Matemática Aplicada - Bacharelado - Manaus |
| Tipo de acesso: | Acesso Aberto |
| metadata.dc.rights.uri: | An error occurred getting the license - uri. |
| URI: | http://riu.ufam.edu.br/handle/prefix/6342 |
| Vocabulário controlado: | Otimização combinatória Matemática |
| Aparece nas coleções: | Trabalho de Conclusão de Curso - Graduação - Ciências Exatas e da Terra |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| TCC_John Wendell Labis Melo.pdf | 491,38 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.