Estratégias vencedoras para jogos de convexidade em grafos

Authors

  • João Brito UFC
  • Rudini Sampaio UFC

Abstract

Em 1981, foi publicado o primeiro artigo em inglês de convexidade em grafos. Três anos depois, em 1984, um de seus autores, Frank Harary, introduziu os primeiros jogos de convexidade. Apesar de definidos há muito tempo, as últimas pesquisas sobre jogos de convexidade datavam de 2003, com poucos resultados significativos devido a sua dificuldade. Neste trabalho, conseguimos usar a Teoria de Sprague-Grundy para resolver jogos de convexidade em grafos especiais, como árvores. Além disso, provamos que um desses jogos é PSPACE-difícil, o que o coloca um nível de complexidade acima dos problemas NP-difíceis.

Downloads

Não há dados estatísticos.

Referências

Bouton, C. L. (1901). Nim, a game with a complete mathematical theory. Annals of Mathematics, 3(1/4):35–39.

Buckley, F. and Harary, F. (1985a). Closed geodetic games for graphs. Congr Numerantium, 47:131–138. Proc 16th Southeastern Combinatorics, Graph Th and Comput.

Buckley, F. and Harary, F. (1985b). Geodetic games for graphs. Quaest Math, 8:321–334.

Grundy, P. M. (1939). Mathematics and games. Eureka, 2:6–8.

Harary, F. (1984). Convexity in graphs: Achievement and avoidance games. In Annals of Discrete Mathematics (20), volume 87, page 323. North-Holland.

Harary, F. and Nieminem, J. (1981). Convexity in graphs. J Differ Geom, 16(1):185–190.

Haynes, T., Henning, M., and Tiller, C. (2003). Geodetic achievement and avoidance games for graphs. Quaestiones Mathematicae, 26:389–397.

Hearn, R. and Demaine, E. (2009). Games, Puzzles and Computation. A. K. Peters Ltd.

Nečásková, M. (1988). A note on achievement geodetic game. Quaest Math, 12:115–119.

Schaefer, T. (1978). On the complexity of some two-person perfect-information games. Journal of Computer and System Sciences, 16(2):185–225.

Sprague, R. (1936). Über mathematische Kampfspiele. Tôhoku Math J, 41:438–444.

Zermelo, E. (1913). Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. In Proc. 5th Int. Congress of Mathematicians, pages 501–504.

Downloads

Published

2024-06-28

Como Citar

Brito, J., & Sampaio, R. (2024). Estratégias vencedoras para jogos de convexidade em grafos. Revista Eletrônica De Iniciação Científica Em Computação, 22(1), 11–20. Recuperado de https://journals-sol.sbc.org.br/index.php/reic/article/view/4644

Issue

Vol. 22 No. 1 (2024)

Section

Artigos

Licença

Copyright (c) 2024 Os autores

Creative Commons License

Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial 4.0 International License.