Please use this identifier to cite or link to this item: http://riu.ufam.edu.br/handle/prefix/4856
metadata.dc.type: Relatório de Pesquisa
Title: Sobre o Problema da Lista Coloração em Grafos
metadata.dc.creator: Nadny Maciel Dantas
metadata.dc.contributor.advisor1: Rosiane de Freitas Rodrigues
metadata.dc.description.resumo: Este projeto de pesquisa é continuação do projeto de PIBIC-Jr 2013-2014 envolvendo introdução à Teoria do Grafos (projeto PIBJR-E0001, sobre Grafos Geométricos, algoritmos e aplicações, do qual a presente aluna é atualmente bolsista), que motivou o ingresso da referida aluna no curso de Bacharelado em Ciência da Computação. Este projeto, portanto, visa a investigação de uma variação do problema clássico de coloração de vértices em grafos, conhecido por problema da lista coloração, envolvendo seus algoritmos e complexidade computacional para classes específicas de grafos, bem como explorando as propriedades de f-selecionabilidade e k-selecionailidade (do inglês, f e k-choosability). Um grafo é um par ordenado G=(V,E), onde V é um conjunto de n elementos denominados de vértices, e E é um conjunto de m pares não-ordenados de elementos de V, denominados de arestas. O problema clássico de coloração de vértices de um grafo, envolve a determinação de uma coloração própria dos vértices deste grafos, onde vértices adjacentes tenham cores distintas, usando o menor número de cores possíveis. Uma k-coloração é uma coloração de um grafo com k cores, e um grafo é k-colorível se tem uma k-coloração. O inteiro positivo mínimo k para o qual um grafo G é k-colorível é seu número cromático [BONDY e MURTY, 2008] [DIESTEL, 2000]. Existem inúmeras variações do problema clássico de coloração de vértices em grafos, um deles é o problema da lista coloração. Neste caso, dado um grafo G=(V,E), existe um conjunto associado L(v) de cores permitidas para cada vértice v de V(G), que consiste na lista de cores disponíveis para se colorir o vértice v, onde tal vértice só pode ser colorido por uma das cores de sua lista de cores L(v). Sendo assim, uma Lista Coloração (do inglês, List Coloring) de G é uma coloração própria de G tal que a cor c(v) atribuída ao vértice v, deve pertencer a lista de cores L(v), para cada vértice do grafo.
Abstract: 
Keywords: algoritmos
lista coloração
teoria dos grafos, otimização
metadata.dc.subject.cnpq: Ciências Exatas e da Terra: Ciencia da Computacao
metadata.dc.language: pt_BR
metadata.dc.publisher.country: Brasil
Publisher: Universidade Federal do Amazonas
metadata.dc.publisher.initials: UFAM
metadata.dc.publisher.department: Ciências da Computacao
Instituto de Ciências Exatas
metadata.dc.publisher.program: PROGRAMA PIBIC 2014
metadata.dc.rights: Acesso Restrito
URI: http://riu.ufam.edu.br/handle/prefix/4856
Issue Date: 31-Jul-2015
Appears in Collections:Relatórios finais de Iniciação Científica

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.