Use este identificador para citar ou linkar para este item: http://www.monografias.ufop.br/handle/35400000/1680
Registro completo de metadados
Campo Dublin CoreValorIdioma
dc.contributor.advisorFonseca, George Henrique Godim dapt_BR
dc.contributor.authorVieira, Mariane Regina Afonso-
dc.date.accessioned2019-02-06T17:20:07Z-
dc.date.available2019-02-06T17:20:07Z-
dc.date.issued2018-
dc.identifier.citationVIEIRA, Mariane Regina Afonso. Heurística matemática aplicada ao problema da coloração de grafos. 2018. 60 f. Monografia (Graduação em Engenharia de Computação) - Instituto de Ciências Exatas e Aplicadas, Universidade Federal de Ouro Preto, João Monlevade, 2018.pt_BR
dc.identifier.urihttp://www.monografias.ufop.br/handle/35400000/1680-
dc.description.abstractDado um grafo G = (V, E) composto por um conjunto de vértices V e um conjunto de arestas E, o Problema da Coloração de Grafos (PCG) consiste em atribuir uma cor a cada vértice do grafo, de modo que vértices adjacentes não possuam a mesma cor, utilizando o menor número de cores possível. Esse é um dos problemas mais estudados na área de Otimização Combinatória devido a suas inúmeras aplicações. Este trabalho propõe a aplicação de uma heurística matemática, mipHeuristic, baseada em decomposição para resolver o Problema da Coloração de Grafos, faz uma comparação dos resultados da heurística matemática proposta com algoritmos já consagrados na literatura, como a heurística de refinamento recol e a meta-heurística Simulated Aneealing, e apresenta a análise dos resultados obtidos em relação ao estado da arte. Os resultados obtidos sugerem que a heurística matemática mipHeuristic funciona melhor quando aplicada à instâncias menores e que a utilização de heurísticas matemáticas para o Problema da Coloração de Grafos (PCG) apresenta resultados promissores.pt_BR
dc.language.isopt_BRpt_BR
dc.rightsopen accesspt_BR
dc.subjectHeurísticapt_BR
dc.subjectAlgoritmospt_BR
dc.subjectProgramação heurísticapt_BR
dc.titleHeurística matemática aplicada ao problema da coloração de grafos.pt_BR
dc.typeTCC-Graduaçãopt_BR
dc.rights.licenseAutorização concedida à Biblioteca Digital de TCC’s da UFOP pelo(a) autor(a) em 21/11/2018 com as seguintes condições: disponível sob Licença Creative Commons 4.0 que permite copiar, distribuir e transmitir o trabalho desde que sejam citados o autor e o licenciante. Não permite o uso para fins comerciais nem a adaptação.pt_BR
dc.contributor.refereeFonseca, George Henrique Godim dapt_BR
dc.contributor.refereeCosta, Tatiana Alvespt_BR
dc.contributor.refereeOliveira, Fernando Bernardes dept_BR
dc.description.abstractenGiven a graph G = (V, E) composed of a set of vertex V = {v1, v2, ..., vn} and a set of edges E = {e1, e2, ..., em}, the Graph Coloring Problem (GCP) consists in assigning a color to each vertex of the graph, so that adjacent vertex, using the smallest number of colors that is possible. This is one of the most studied problems in Combinatorial Optimization due to its numerous applications. This work proposes the application of a math-heuristic based on decomposition to solve the Graph Coloring Problem, makes a comparison of the results of the proposed math-heuristic with algorithms already established in the literature, such as, the heuristic refinement recol and the meta-heuristic Simulated Annealing, and presents the analysis of the results obtained in relation to the state of the art. The results suggest that the mathematical heuristics mipHeuristic works best when applied to smaller instances and the use of mathematical heuristics for Graph Coloring Problem (GCP) presents promising results.pt_BR
Aparece nas coleções:Engenharia de Computação - JMV

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
MONOGRAFIA_HeurísticaMatemáticaAplicada.pdf2,19 MBAdobe PDFVisualizar/Abrir


Este item está licenciado sob uma Licença Creative Commons Creative Commons