Ciclos hamiltonianos: uma abordagem com jogo de tabuleiro

Abstract

Graph Theory is an important field of Discrete Mathematics and Computer Science, widely applied to the modeling and solution of problems involving networks, connectivity, and route optimization. Among the classical problems in this area, the Hamiltonian Cycle Problem stands out, consisting of determining the existence of a path capable of visiting every vertex of a graph exactly once and returning to the starting vertex. Despite its theoretical and practical relevance, understanding this concept may be challenging due to its high level of abstraction. In this context, the present work proposes the use of a board game as a tool to represent and analyze the formation of Hamiltonian cycles in graphs. To achieve this objective, a board game based on a simple undirected graph was developed, in which participants must construct valid cycles while complying with different gameplay restrictions. Two game modes were implemented, differing in the way edge weights are assigned, allowing the evaluation of the impact of these restrictions on the players’ experience. The methodology involved the development of a prototype, the execution of experimental sessions with participants, and the application of a Likert-scale questionnaire to analyze players’ perceptions. The results indicated that the implemented restrictions influenced decision-making and the strategies adopted during gameplay, although they produced only minor differences in the quantitative metrics observed. Furthermore, participants showed a preference for the global weight system, which was perceived as more balanced and fair. Therefore, this study demonstrates the feasibility of using board games as a means of representing Graph Theory problems, enabling a practical analysis of the influence of restrictions on the formation of Hamiltonian cycles.