Registro fonte: Coloração total de grafos bipartidos

Coloração total de grafos bipartidos

A 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...

ver descrição completa

Autor principal:	Becher, Gabriel Coplas
Formato:	Trabalho de Conclusão de Curso (Graduação)
Idioma:	Português
Publicado em:	Universidade Tecnológica Federal do Paraná 2020
Assuntos:	Representações dos grafos Cor - Percepção Análise de sistemas Algorítmos Representations of graphs Color vision System analysis Algorithms CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Acesso em linha:	http://repositorio.utfpr.edu.br/jspui/handle/1/16000
Tags:	Adicionar Tag Sem tags, seja o primeiro a adicionar uma tag!

id	riut-1-16000
recordtype	dspace
spelling	riut-1-160002020-11-19T18:25:28Z Coloração total de grafos bipartidos Total coloring of bipartite graphs Becher, Gabriel Coplas Almeida, Sheila Morais de Almeida, Sheila Morais de Alves, Gleifer Vaz Queiroz, Saulo Jorge Beltrao de Maciel, Denise do Rocio Representações dos grafos Cor - Percepção Análise de sistemas Algorítmos Representations of graphs Color vision System analysis Algorithms CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO A 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. Uma 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. 2020-11-19T18:25:27Z 2020-11-19T18:25:27Z 2019-06-26 bachelorThesis BECHER, 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. http://repositorio.utfpr.edu.br/jspui/handle/1/16000 por openAccess application/pdf Universidade Tecnológica Federal do Paraná Ponta Grossa Brasil Departamento Acadêmico de Informática Ciência da Computação UTFPR
institution	Universidade Tecnológica Federal do Paraná
collection	RIUT
language	Português
topic	Representações dos grafos Cor - Percepção Análise de sistemas Algorítmos Representations of graphs Color vision System analysis Algorithms CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
spellingShingle	Representações dos grafos Cor - Percepção Análise de sistemas Algorítmos Representations of graphs Color vision System analysis Algorithms CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Becher, Gabriel Coplas Coloração total de grafos bipartidos
description	A 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.
format	Trabalho de Conclusão de Curso (Graduação)
author	Becher, Gabriel Coplas
author_sort	Becher, Gabriel Coplas
title	Coloração total de grafos bipartidos
title_short	Coloração total de grafos bipartidos
title_full	Coloração total de grafos bipartidos
title_fullStr	Coloração total de grafos bipartidos
title_full_unstemmed	Coloração total de grafos bipartidos
title_sort	coloração total de grafos bipartidos
publisher	Universidade Tecnológica Federal do Paraná
publishDate	2020
citation	BECHER, 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.
url	http://repositorio.utfpr.edu.br/jspui/handle/1/16000
_version_	1805305326338048000
score	10,814766

Coloração total de grafos bipartidos

Registros relacionados