Use este identificador para citar ou linkar para este item: http://riu.ufam.edu.br/handle/prefix/6342
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.advisor1Bitar, Sandro Dimy Barbosa-
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/9242299183536872pt_BR
dc.contributor.referee1Júnior, Mário Salvatierra-
dc.contributor.referee1Latteshttp://lattes.cnpq.br/7254679644374259pt_BR
dc.contributor.referee2Bandeira, Karla Christina Tribuzy-
dc.contributor.referee2Latteshttp://lattes.cnpq.br/8694138602724587pt_BR
dc.creatorMelo, John Wendell Labis-
dc.creator.Latteshttp://lattes.cnpq.br/0588970160583787pt_BR
dc.date.accessioned2022-09-29T17:02:00Z-
dc.date.available2022-10-30-
dc.date.available2022-09-29T17:02:00Z-
dc.identifier.urihttp://riu.ufam.edu.br/handle/prefix/6342-
dc.description.abstractThe 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.pt_BR
dc.description.resumoO 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.pt_BR
dc.languageporpt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentICE - Instituto de Ciências Exataspt_BR
dc.relation.referencesCARDOSO, D. M. Tópicos de teoria algébrica dos grafos. 2008. CARDOSO, D. M. Teoria dos grafos e aplicações. 2011. FILHO, M. G.; JUNQUEIRA, R. d. Á. R. Problema do carteiro chinês: escolha de métodos de solução e análise de tempos computacionais. Production, SciELO Brasil, v. 16, p. 538–551, 2006. GOMES, M. J. N.; JÚNIOR, W. R. C.; PALHANO, A. W. d. C.; COUTINHO, E. F.; CASTRO, G. A. d.; GOMES, F. J. N.; BARCELLOS, G. C.; REZENDE, B. F.; PEREIRA, L. W. L. O problema do carteiro chinês, algoritmos exatos e um ambiente mvi para análise de suas instâncias: sistema xnês. Pesquisa Operacional, SciELO Brasil, v. 29, p. 323–363, 2009. GONZÁLEZ, M. C. Problemas de rutas de vehículos por arcos. 2018. JURKIEWICZ, S. Grafos–uma introdução. São Paulo: OBMEP, 2009. MARY, U. d. L. Q. Teoria de Grafos e Aplicações. 2007. Disponível em: <https://webspace.maths.qmul.ac.uk/b.jackson/MAS210/>. Acesso em: 30 de janeiro de 2022. SILVA, A. A. da; LINS, S. L. S.; XAVIER, A. da S. Uma aplicação do problema do carteiro chinês direcionado na coleta de lixo urbano. Brazilian Journal of Development, v. 6, n. 5, p. 24640–24659, 2020.pt_BR
dc.rightsAcesso Abertopt_BR
dc.rights.uriAn error occurred getting the license - uri.*
dc.subjectGrafo de Euler (Euleriano)pt_BR
dc.subjectCircuito de Eulerpt_BR
dc.subjectProblema Chinês do Carteiro (PCC)pt_BR
dc.subjectGrau do vérticept_BR
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA MATEMATICA MATEMATICA APLICADApt_BR
dc.titleO problema chinês do carteiro: um convite à Teoria dos Grafospt_BR
dc.typeTrabalho de Conclusão de Cursopt_BR
dc.creator.affiliationUniversidade Federal do Amazonaspt_BR
dc.date.event2022-09-16-
dc.publisher.localpubManauspt_BR
dc.subject.controladoOtimização combinatóriapt_BR
dc.subject.controladoMatemáticapt_BR
dc.creator.affiliation-initUFAMpt_BR
dc.publisher.courseMatemática Aplicada - Bacharelado - Manauspt_BR
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 TamanhoFormato 
TCC_John Wendell Labis Melo.pdf491,38 kBAdobe PDFVisualizar/Abrir
Mostrar registro simples do item Recomendar este item


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.