Jogo de perseguição em grafos infinitos

• Processo: 25/09834-9
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de agosto de 2025
• Data de Término da vigência: 31 de julho de 2026
• Área de conhecimento: Ciências Exatas e da Terra - Matemática
• Pesquisador responsável: Leandro Fiorini Aurichi
• Beneficiário: Felipe Vilas Boas Marprates
• Instituição Sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
• Assunto(s): Combinatória Grafos
• Palavra(s)-Chave do Pesquisador: combinatória | conjuntos | grafos

Resumo

Neste projeto, estudamos o jogo de perseguição e evasão em grafos infinitos, no qual dois jogadores, um policial e um ladrão, se movimentam alternadamente pelos vértices de um grafo. O objetivo do policial é alcançar o ladrão, enquanto o do ladrão é escapar indefinidamente. Embora exista uma caracterização dos grafos nos quais o policial possui uma estratégia vencedora no caso finito, essa equivalência não se mantém no contexto de grafos infinitos. Analisamos, diferentes generalizações do conceito de grafos \textit{cop-win}, como grafos \textit{fracamente cop-win} e \textit{C-fracamente cop-win}, além de suas conexões com construibilidade, grafos desmontáveis, estratégias protetoras e grafos de Helly. Apresentamos também as principais contribuições desses trabalhos, destacando os avanços e limitações na caracterização de estratégias vencedoras em grafos infinitos.