Sobre problemas de lista coloração e a propriedade de selecionabilidade em grafos
Nesta dissertação, o problema da lista coloração e a propriedade da selecionabilidade em grafos são abordados. Lista coloração é uma generalização do problema da coloração de vértices em grafos, e tal como este problema clássico, consiste em colorir um grafo simples de modo que vértices adjacente...
| Autor principal: | Gama, Simone Ingrid Monteiro |
|---|---|
| Outros Autores: | http://lattes.cnpq.br/1415954961112300 |
| Grau: | Dissertação |
| Idioma: | por |
| Publicado em: |
Universidade Federal do Amazonas
2017
|
| Assuntos: | |
| Acesso em linha: |
http://tede.ufam.edu.br/handle/tede/5650 |
| id |
oai:https:--tede.ufam.edu.br-handle-:tede-5650 |
|---|---|
| recordtype |
dspace |
| spelling |
oai:https:--tede.ufam.edu.br-handle-:tede-56502017-04-19T05:03:59Z Sobre problemas de lista coloração e a propriedade de selecionabilidade em grafos Gama, Simone Ingrid Monteiro Rodrigues, Rosiane de Freitas http://lattes.cnpq.br/1415954961112300 http://lattes.cnpq.br/8358219976594707 Santos , Eulanda Miranda dos Bonorno , Flávia Pio , Jose Luiz de Souza Coloração em grafos Complexidade computational Selecionabilidade em grafos Teoria dos grafos CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO Nesta dissertação, o problema da lista coloração e a propriedade da selecionabilidade em grafos são abordados. Lista coloração é uma generalização do problema da coloração de vértices em grafos, e tal como este problema clássico, consiste em colorir um grafo simples de modo que vértices adjacentes possuam cores distintas, mas, respeitando- se a restrição adicional de que cada vértice possui uma lista restrita de possíveis cores a serem usadas. Tal problema possui algumas variações, como a (g;μ)-coloração, que envolve listas sequenciais com limite inferior e superior conhecidos. A k-selecionabilidade consiste em determinar o menor tamanho de lista k para o qual sempre há uma lista coloração, seja qual for a distribuição de lista no grafo. Nesta dissertação, se investigou a correlação entre a propriedade da k-selecionabilidade e a (g;μ)-coloração, sendo definida a propriedade de k-(g;μ)-selecionabilidade. Com isto, foram também estudadas algumas técnicas de prova em selecionabilidade, aplicadas para se determinar a k-(g;μ)-selecionabilidade para classes específicas de grafos, como a técnica de degeneração em grafos, usada para provar que grafos periplanares são 3-(g;μ)-selecionáveis e a técnica de Marshal Hall, usada para provar que grafos bipartidos completos são 2-(g;μ)-selecionáveis. O resultado mais geral, obtido através de uma prova formal, consistiu em determinar que se um grafo é k-colorível, então tal grafo também é k-(g;μ)-selecionável, deixando de ser Pp 2-completo para ser NP-completo. Adicionalmente, foram estudados e implementados alguns algoritmos para determinar a lista coloração e k-selecionabilidade em grafos simples gerais In this work, the list coloring problem and choosability property in graphs are investigated. List coloring is a generalization of the vertex coloring problem in graph, and as this classic problem is to color a simple graph so that adjacent vertices have different colors, but respecting the additional constraint thaht each vertex has a list of porrible colors to be used. This problem has some variations as the (g;μ)-coloring, which involves sequential lists with lower and upper bounds known. The k-choosability is to determine the smallest size list k for which there is always a valid list coloring, whatever the distribution of the list in the graph. Thus, we investigated the correlation between k-choosability and (g;μ)-coloring, porposing the k-(g;μ)-choosability property. With this, we also analysed some proof tecnhiques in choosability, applied to determine k-(g;μ)-choosability for specific graphs are 3-(g;μ)-choosable and the technique of Marshal Hall, applied to prove that complete bipartite graphs are 2-(g;μ)-choosable. The most general result, obtaines throught a relatively simple formal proof, consisted to determine if a graph is k-colorable, then this graph is algo k-(g;μ)-choosable, leaving to be Pp 2-complete for NP-complete. Additionally, it was studied and implemented some algorithms to determine the list coloration and k-choosability for simple general graphs. CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior 2017-04-18T19:25:33Z 2016-04-19 Dissertação GAMA, Simone Ingrid Monteiro. Sobre problemas de lista coloração e a propriedade de selecionabilidade em grafos. 2016. 95 f. Dissertação (Mestrado em Informática) - Universidade Federal do Amazonas, Manaus, 2016. http://tede.ufam.edu.br/handle/tede/5650 por Acesso Aberto http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Universidade Federal do Amazonas Instituto de Computação Brasil UFAM Programa de Pós-graduação em Informática |
| institution |
TEDE - Universidade Federal do Amazonas |
| collection |
TEDE-UFAM |
| language |
por |
| topic |
Coloração em grafos Complexidade computational Selecionabilidade em grafos Teoria dos grafos CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO |
| spellingShingle |
Coloração em grafos Complexidade computational Selecionabilidade em grafos Teoria dos grafos CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO Gama, Simone Ingrid Monteiro Sobre problemas de lista coloração e a propriedade de selecionabilidade em grafos |
| topic_facet |
Coloração em grafos Complexidade computational Selecionabilidade em grafos Teoria dos grafos CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO |
| description |
Nesta dissertação, o problema da lista coloração e a propriedade da selecionabilidade
em grafos são abordados. Lista coloração é uma generalização do problema da coloração
de vértices em grafos, e tal como este problema clássico, consiste em colorir um grafo
simples de modo que vértices adjacentes possuam cores distintas, mas, respeitando- se a
restrição adicional de que cada vértice possui uma lista restrita de possíveis cores a serem
usadas. Tal problema possui algumas variações, como a (g;μ)-coloração, que envolve listas
sequenciais com limite inferior e superior conhecidos. A k-selecionabilidade consiste
em determinar o menor tamanho de lista k para o qual sempre há uma lista coloração,
seja qual for a distribuição de lista no grafo. Nesta dissertação, se investigou a correlação
entre a propriedade da k-selecionabilidade e a (g;μ)-coloração, sendo definida a propriedade
de k-(g;μ)-selecionabilidade. Com isto, foram também estudadas algumas técnicas
de prova em selecionabilidade, aplicadas para se determinar a k-(g;μ)-selecionabilidade
para classes específicas de grafos, como a técnica de degeneração em grafos, usada para
provar que grafos periplanares são 3-(g;μ)-selecionáveis e a técnica de Marshal Hall,
usada para provar que grafos bipartidos completos são 2-(g;μ)-selecionáveis. O resultado
mais geral, obtido através de uma prova formal, consistiu em determinar que se um grafo é
k-colorível, então tal grafo também é k-(g;μ)-selecionável, deixando de ser Pp
2-completo
para ser NP-completo. Adicionalmente, foram estudados e implementados alguns algoritmos
para determinar a lista coloração e k-selecionabilidade em grafos simples gerais |
| author_additional |
Rodrigues, Rosiane de Freitas |
| author_additionalStr |
Rodrigues, Rosiane de Freitas |
| format |
Dissertação |
| author |
Gama, Simone Ingrid Monteiro |
| author2 |
http://lattes.cnpq.br/1415954961112300 |
| author2Str |
http://lattes.cnpq.br/1415954961112300 |
| title |
Sobre problemas de lista coloração e a propriedade de selecionabilidade em grafos |
| title_short |
Sobre problemas de lista coloração e a propriedade de selecionabilidade em grafos |
| title_full |
Sobre problemas de lista coloração e a propriedade de selecionabilidade em grafos |
| title_fullStr |
Sobre problemas de lista coloração e a propriedade de selecionabilidade em grafos |
| title_full_unstemmed |
Sobre problemas de lista coloração e a propriedade de selecionabilidade em grafos |
| title_sort |
sobre problemas de lista coloração e a propriedade de selecionabilidade em grafos |
| publisher |
Universidade Federal do Amazonas |
| publishDate |
2017 |
| url |
http://tede.ufam.edu.br/handle/tede/5650 |
| _version_ |
1781302206392172544 |
| score |
11.653393 |