توصيفگر ها :
عدد رنگي بازي , بازي رنگآميزي رأسي همبند , عدد رنگي بازي همبند , بازي رنگآميزي همبند
چكيده فارسي :
بازي روي گراف ها همواره از موضوعات جالب و مورد توجه بوده است. از جمله اين بازي ها، بازي رنگ آميزي رأسي، بازي
احاطه گري، بازي علامت گذاري و ... هستند. در اين پايان نامه بازي رنگ آميزي رأسي و بازي رنگ آميزي رأسي همبند
مورد مطالعه قرار گرفته است.
بازي رنگ آميزي رأسي همبند يك بازي دو نفره است كه بين دو بازيكن مانند آليس و باب انجام مي شود. آليس و
رنگي كه به آنها داده شده است، به نوبت رأس هاي گراف را رنگ آميزي مي كنند به طوري -k باب با توجه به مجموعه ي
كه رأس هاي مجاور هم رنگ نباشند. در اين بازي هدف بازيكن شروع كننده تكميل رنگ آميزي كل گراف است ولي هدف
بازيكن ديگر اين است كه از دستيابي به رنگ آميزي كل گراف جلوگيري كند.
چكيده انگليسي :
The coloring game is played by two players called Alice and Bob on the vertices of a graph G as follows: Using
colors from a set X = {1, 2, ..., k} of k distinct colors, the players take turns in assigning colors to the vertices of
G such that no two adjacent vertices will receive the same color. The two players play alternately with Alice always
moving first. The game ends when either all the all the vertices have been colored, or it is no longer possible to color
an uncolored vertex. Alice wins in the first case and Bob wins otherwise.
The game chromatic number ofGdenoted by χg(G), is the smallest integer k for which Alice has a winning strategy
when playing the graph coloring game on G with k colors.
A new version of the graph coloring game is the connected graph coloring game. The connected graph coloring game
played on connected graphs, by requiring that, after each player’s turn, the subgraph induced by the set of colored
vertices is connected. In onther words, on their turn, each player must color an uncolored neighbor except for Alice
on her first move.
The connected game chromatic number of G denoted by χcg(G), is the smallest integer k for which Alice has a
winning strategy when playing the connected graph coloring game on G with k colors.
One of the graph coloring game is the marking game. In the play of the marking game, Alice and Bob take turns
marking vertices of a graph, with Alice marking first. In a play of marking game on a graphG, each vertex v receives
a score equal to the number of neighbors of v marked before v, and that play of the marking game receives an overall
score equal to the maximum score of a vertex. Alice’s goal in the marking game is to minimize the play score, and
Bob’s goal is to maximum the play score. The game coloring number of a graphG, written colg(G), is the minimum
integer k for which Alice has a strategy in the marking game on G to limit the number of marked neighbors of each
unmarked vertex at each game state to k−1-that is, colg(G)−1 is the minimum play score that Alice can guarantee
in the marking game on a graph G.
One of the graph coloring game is the connected marking game. The connected marking game for a graph G, which
have the same rules as their traditional counterparts with the exception that Alice and Bob must play so that the set of
played vertices always forms a connected set, These connected games give rise to the graph parameters of connected
game coloring number, written respectively as colcg(G).
