Lights Out em grafos: apagando luzes da menor maneira
Resumo
Lights Out é um quebra-cabeça eletrônico cujo objetivo é encontrar um conjunto de botões que, quando pressionados, apaguem todas as luzes do tabuleiro. Neste trabalho, consideramos a generalização cuja entrada é um grafo e focamos na versão de minimização, onde o objetivo é determinar o número mínimo de vértices que devem ser acionados para apagar todo o grafo. Trabalhamos com grafos Caterpillar, Snarks Flor e Snarks Goldberg. Para auxiliar na obtenção dos resultados, implementamos um software que simula o jogo para qualquer grafo de entrada e também um algoritmo força-bruta que soluciona a versão de minimização.
Palavras-chave:
Lights Out, Snark, Grafos
Referências
Berman, A., Borer, F., and Hungerbühler, N. (2019). Lights out on graphs. arXiv:1903.06942.
Fleischer, R. and Yu, J. (2013). A survey of the game lights out! LNCS, 8066.
Isaacs, R. (1975). Infinite families of nontrivial trivalent graphs which are not tait colorable. The American Mathematical Monthly.
Sutner, K. (1988). Additive automata on graphs. complex systems 2. Stevens Institute of Technology.
Fleischer, R. and Yu, J. (2013). A survey of the game lights out! LNCS, 8066.
Isaacs, R. (1975). Infinite families of nontrivial trivalent graphs which are not tait colorable. The American Mathematical Monthly.
Sutner, K. (1988). Additive automata on graphs. complex systems 2. Stevens Institute of Technology.
Publicado
31/07/2022
Como Citar
COUTO, Fernanda; BRITO, Ighor Bruno de; SENTO SÉ, Willian de Assis.
Lights Out em grafos: apagando luzes da menor maneira. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 137-140.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2022.223319.
