Estratégias vencedoras para jogos de convexidade em grafos

Abstract

The combinatorial games theory is a branch of mathematics and theoretical computer science that studies sequential games with perfect information. A combinatorial game is called impartial if the only difference between the first players and second player is that the first started the game, but both players have the same possibility of play. The Sprague-Grundy’s theory says that every finite impartial game can be associated with a number, called nimber, regarding size of a Nim game heap, a classical impartial game solved for C. Bouton in 1901. . Therefore, determine the nimber of a impartial game is important to obtain a winning strategy, acoording to know winning strategies of the Nim game. Moreover, a combinatorial game is called partizan if the some moves are allowed for a player and not to another. One of John H. Conway’s contributions in partizan game theory was associated a dyadic number with this games in order to obtain winning strategies in them. Futhermore, accordingly to Duchet (1987), the first paper of convexity on graphs, in english, it the paper "Convexity in graphs"published in 1981. One of its authors, Frank Harary, introduced in 1984 the first graph convexity games, focused on the geodesic convexity, which were investigated in a sequence of five papers tha endend in 2003. In this work, we continue this research line, extend these games to other graph convexities, and obtain winning strategies results. Among them, we obtain winning strategies for trees from the Sprague-Grundy theory on impartial games and Conway’s combinatorial game theory on partizan games.