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 dissertao usamos a Teoria dos Jogos como uma ferramenta para colorir propriamente os vrtices 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 vrtices $V$, o conjunto de cores o conjunto de estratgias possveis para todos os vrtices e a recompensa para cada vrtice o nmero de vrtices que possui a sua cor. Comeamos o jogo com uma colorao prpria de vrtices arbitrria (por exemplo, a colorao prpria trivial onde para cada vrtice atribuda uma cor diferente), faz-se uma mudana local, permitindo que cada vrtice (um por vez) mude para outra classe de cor com maior cardinalidade, at que no seja mais possvel uma mudana local. Quando no mais possvel fazer esta mudana, temos que o algoritmo atingiu um \\\\textit{equilbrio de Nash puro}.

Neste trabalho, analisamos limites superiores conhecidos na literatura para o nmero cromtico $\\\\chi(G)$ e verificamos se so tambm limites superiores para $\\\\Gamma(G)$. Tambm estudamos o quo pior (Medida da Anarquia do Jogo) pode ser o nmero de cores retornado por $\\\\Gamma(G)$ comparado ao nmero cromtico para as classes Bipartido, Caminhos e Ciclo. Estabelecemos duas conjecturas para o preo da anarquia das rvores e da famlia de Mycielski. Consideramos trs problemas de deciso: {\\\\sc{colorao do jogo}}, {\\\\sc{maior classe do jogo}} e {\\\\sc{anarquia bipartida}} associados ao jogo da colorao. Provamos que os problemas {\\\\sc{colorao do jogo}}, mesmo se $k=3$, e {\\\\sc{maior classe do jogo}}, mesmo se $G$ cbico, so 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.
Topo