1. Repositório Institucional da Universidade Tecnológica Federal do Paraná (RIUT)
  2. GRAD - Cursos de Graduação
  3. TCC - Trabalhos de Conclusão de Curso de Graduação
  4. Ponta Grossa
  5. PG - Ciência da Computação
Use este identificador para citar ou linkar para este item: http://repositorio.utfpr.edu.br/jspui/handle/1/16000
Registro completo de metadados
Campo DCValorIdioma
dc.creatorBecher, Gabriel Coplas
dc.date.accessioned2020-11-19T18:25:27Z-
dc.date.available2020-11-19T18:25:27Z-
dc.date.issued2019-06-26
dc.identifier.citationBECHER, Gabriel Coplas. Coloração total de grafos bipartidos. 2019. 58 f. Trabalho de Conclusão de Curso (Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2019.pt_BR
dc.identifier.urihttp://repositorio.utfpr.edu.br/jspui/handle/1/16000-
dc.description.abstractA total coloring in a graph G is a color assignment to elements to G so that any two adjacent elements have different colors. The Total Coloring Problem is to determine the smallest number of colors to obtain a total coloring for a given graph G. This number is called the total chromatic number and it is denoted by X"(G). In its decision version, the Total Coloring Problem receives as input a graph G and an integer number, k, and it is desired to know if there is a total coloring for G with at most k colors. The decision version of Total Coloring Problem is an NP - Complete problem, even when restricted to the class of bipartite graphs, which are those whose vertices can be partitioned into two independent sets. An efficient algorithm that solves any of the NP-Complete problems in polynomial time is unknown, but if any algorithm of polynomial complexity exists, then it can be used to solve any problem of the class NP. Presenting an efficient algorithm for an NP - complete problem or proving that such an algorithm does not exist is one of the seven most challenging problems of the millennium, according to the Clay Mathematics Institute. In this work we present a subset of bipartite graphs for which the Total Coloring Problem remains open.pt_BR
dc.languageporpt_BR
dc.publisherUniversidade Tecnológica Federal do Paranápt_BR
dc.rightsopenAccesspt_BR
dc.subjectRepresentações dos grafospt_BR
dc.subjectCor - Percepçãopt_BR
dc.subjectAnálise de sistemaspt_BR
dc.subjectAlgorítmospt_BR
dc.subjectRepresentations of graphspt_BR
dc.subjectColor visionpt_BR
dc.subjectSystem analysispt_BR
dc.subjectAlgorithmspt_BR
dc.titleColoração total de grafos bipartidospt_BR
dc.title.alternativeTotal coloring of bipartite graphspt_BR
dc.typebachelorThesispt_BR
dc.description.resumoUma coloração total em um grafo G é uma atribuição de cores para os elementos de G de forma que quaisquer dois elementos adjacentes tenham cores diferentes. O Problema da Coloração Total é determinar o menor número de cores com que se pode obter uma coloração total de um dado grafo G. Esse número é denominado de número cromático total e denotado por X"(G). Em sua versão de decisão, o Problema da Coloração Total recebe como entrada um grafo G e um número inteiro k para os quais deseja-se saber se é possível realizar uma coloração total de G com no máximo k cores. A versão de decisão do Problema da Coloração Total é um problema NP - completo mesmo quando restrita à classe dos grafos bipartidos, que são aqueles cujos vértices podem ser particionados em dois conjuntos independentes. Não se conhece algoritmo eficiente que resolva em tempo polinomial qualquer dos problemas NP - completos, mas caso algum algoritmo de complexidade polinomial exista, então o mesmo poderá ser utilizado para resolver qualquer problema da classe de problemas NP. Apresentar um algoritmo eficiente para um problema NP - completo ou provar que tal algoritmo não existe é um dos sete problemas mais desafiadores do milênio, segundo o Clay Mathematics Institute. Nesse trabalho determinou-se um subconjunto dos grafos bipartidos em que o Problema da Coloração Total permanece em aberto.pt_BR
dc.degree.localPonta Grossapt_BR
dc.publisher.localPonta Grossapt_BR
dc.contributor.advisor1Almeida, Sheila Morais de
dc.contributor.referee1Almeida, Sheila Morais de
dc.contributor.referee2Alves, Gleifer Vaz
dc.contributor.referee3Queiroz, Saulo Jorge Beltrao de
dc.contributor.referee4Maciel, Denise do Rocio
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentDepartamento Acadêmico de Informáticapt_BR
dc.publisher.programCiência da Computaçãopt_BR
dc.publisher.initialsUTFPRpt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpt_BR
Aparece nas coleções:PG - Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
PG_COCIC_2019_1_12.pdf2,7 MBAdobe PDFThumbnail
Visualizar/Abrir
Mostrar registro simples do item Recomendar este item Visualizar estatísticas


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