Uma abordagem de Teoria dos Jogos para Coloração de Grafos
Autores
|
5745 |
Aline Cristina Azevedo e Silva
|
2650,257,414
|
|
5746 |
2650,257,414
|
|
|
5747 |
2650,257,414
|
Informações:
Publicações do PESC
Título
Uma abordagem de Teoria dos Jogos para Coloração de Grafos
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
10/2/2015
Resumo
Nesta dissertação usamos a Teoria dos Jogos como uma ferramenta para colorir propriamente os vértices de um grafo $G=(V,E)$ qualquer, onde o algoritmo tem por base a pesquisa local. Neste jogo, denotado por $\\\\Gamma(G)$, o conjunto de jogadores é o conjunto de vértices $V$, o conjunto de cores é o conjunto de estratégias possíveis para todos os vértices e a recompensa para cada vértice é o número de vértices que possui a sua cor. Começamos o jogo com uma coloração própria de vértices arbitrária (por exemplo, a coloração própria trivial onde para cada vértice é atribuída uma cor diferente), faz-se uma mudança local, permitindo que cada vértice (um por vez) mude para outra classe de cor com maior cardinalidade, até que não seja mais possível uma mudança local. Quando não é mais possível fazer esta mudança, temos que o algoritmo atingiu um \\\\textit{equilíbrio de Nash puro}.
Neste trabalho, analisamos limites superiores conhecidos na literatura para o número cromático $\\\\chi(G)$ e verificamos se são também limites superiores para $\\\\Gamma(G)$. Também estudamos o quão pior (Medida da Anarquia do Jogo) pode ser o número de cores retornado por $\\\\Gamma(G)$ comparado ao número cromático para as classes Bipartido, Caminhos e Ciclo. Estabelecemos duas conjecturas para o preço da anarquia das Árvores e da família de Mycielski. Consideramos três problemas de decisão: {\\\\sc{coloração do jogo}}, {\\\\sc{maior classe do jogo}} e {\\\\sc{anarquia bipartida}} associados ao jogo da coloração. Provamos que os problemas {\\\\sc{coloração do jogo}}, mesmo se $k=3$, e {\\\\sc{maior classe do jogo}}, mesmo se $G$ é cúbico, são NP-completos e conjecturamos que o problema {\\\\sc{anarquia bipartida}} é NP-completo.
Abstract
In this dissertation we use Game Theory as a tool to properly color the vertices of a graph $ G = (V, E) $, where the algorithm is based on local search. In this game, denoted by $ \\\\Gamma (G) $ the set of players is the set of vertices $ V $, the color set is the set of possible strategies for all vertices and the reward for each vertex is the number of vertices that have its color. We begin with an arbitrary proper vertex coloring (for example, the trivial proper coloring in which for each vertex a different color is assigned), a local change is made, allowing each vertex (one at time) to switch to another color class with higher cardinality, until a local change is no longer possible. When none can make any change, a \\\\textit{pure Nash equilibrium} is reached.
We explore known upper bounds in the literature for the chromatic number $ \\\\chi (G) $ and check if they are also upper bounds for $ \\\\Gamma (G) $. We also study how worse can be the number of colors returned by $\\\\Gamma (G)$ compared (The Anarchy Price) to the chromatic number for the classes Bipartite, Paths and Cycles. We have established two conjectures for the price of anarchy of Trees and Mycielski family. We consider three decision problems: {\\\\sc{game coloring}}, {\\\\sc{biggest class in the game}} and {\\\\sc{bipartite anarchy}} associated with game coloring. We have proved that the {\\\\sc{game coloring}}, even if $k=3$, and {\\\\sc{biggest class in the game}}, even if $ G $ is cubic, are NP-complete. We conjecture that the {\\\\sc{bipartite anarchy}} problem is NP-complete.
Arquivo