Jogos Combinatórios em Teoria dos Grafos

Jogos combinatórios têm despertado o interesse do público em geral, pois demandam, na maioria das vezes, regras acessíveis e soluções, à primeira vista, naturais. De acordo com Berlekamp, nos jogos combinatórios as informações pertinentes ao jogo são públicas e, além disso, não há dados ou dispositivos aleatórios atuando durante as rodadas. Discutimos, nesta apresentação, um jogo particular  concebido por Hartell, em 1995, chamado de jogo do bombeiro. Este jogo inicia-se a partir de um incêndio em um ou mais vértices de um grafo. Em seguida, um conjunto não vazio de vértices não incendiados são defendidos tornando-se imunes ao fogo. A cada nova rodada o fogo se espalha através  dos vértices já incendiados por seus vértices adjacentes e, novamente, um ou mais vértices podem ser defendidos pelos bombeiros, até que o fogo pare de se espalhar. Um dos objetivos mais explorados na literatura para o jogo do bombeiro consiste em minimizar o número de vértices incendiados no grafo. Algoritmos gulosos tendem a ser organicamente pensados como estratégias ótimas para este jogo, no entanto, estratégias contraintuitivas tendem a viabilizar, para algumas classes de grafos, soluções mais eficientes.

Diego é professor do Ensino Básico, Técnico e Tecnológico do Colégio Pedro II (CPII), em regime de dedicação exclusiva, professor e coordenador do programa de Mestrado Profissional em Matemática em Rede Nacional - PROFMAT/CPII. Graduado em Matemática (2004) e em Licenciatura em Matemática (2008) pelo Instituto de Matemática da Universidade Federal do Rio de Janeiro - IM/UFRJ. Mestre em Ensino de Matemática (2010) pelo Programa de Pós-Graduação em Ensino de Matemática da Universidade Federal do Rio de Janeiro - PEMAT/UFRJ e doutor em Engenharia de Sistemas e Computação (2017) pelo Instituto Alberto Luiz Coimbra de Pós Graduação e Pesquisa de Engenharia da Universidade Federal do Rio de Janeiro - COPPE/UFRJ (Conceito CAPES 7). Bolsista do Conselho Nacional de desenvolvimento Científico e Tecnológico (CNPQ), com período sanduíche em Université Joseph Fourrier na França. Pós doutorando, desde julho de 2022, no Instituto de Matemática e Estatística da Universidade do Estado do Rio de Janeiro - CCOMP/IME/UERJ.