Cops and Robbers é um jogo de perseguição-evasão com informação perfeita em um grafo. Determinar se k policiais sempre capturam um ladrão é o problema do Número de Policiais.
Configuração do Jogo
- Grafo G = (V, E): Vértices = localizações; Arestas = movimentos.
- Policias (k): Escolhem vértices iniciais. Movem um policial por turno para vértice adjacente (ou ficam).
- Ladrão (1): Escolhe início após policiais. Move para vértice adjacente (ou fica) cada turno.
- Captura: Policial ocupa mesmo vértice do ladrão. Policiais vencem se captura garantida; ladrão vence se evade para sempre.
Abordagem de Solução (Teórica)
- Calcule Número de Policiais c(G): Mínimo de policiais para garantir captura.
- c(G) = 1 ⇔ Grafo é desmantelável (tem vértice de canto — vizinhança subconjunto de outra). Árvores, grafos cordais, grafos de intervalo têm c(G)=1.
- c(G) ≤ 3 para grafos planares (Aigner & Fromme, 1984).
- c(G) pode ser arbitrariamente grande (conjectura de Meyniel: c(G) = O(√n) — aberta).
- Algorítmico (Grafos Pequenos): Modele como jogo de alcançabilidade em grafo produto (posições policiais × posição ladrão). Resolva via análise retrógrada / BFS no espaço de estados (exponencial em k).
- Heurísticas para Jogo:
- Policias: Guardem conjuntos dominantes, centroides, vértices de articulação; encurralem ladrão para becos.
- Ladrão: Fique em áreas de alto girth, evite pontos de articulação, explore falhas de coordenação dos policiais.
Ferramentas Práticas
- NetworkX (Python): `networkx.algorithms.approximation.cops_and_robbers` (heurística).
- Cops and Robbers Simulator (web): Busque visualizações interativas.
- Literatura: "The Game of Cops and Robbers on Graphs" (Bonato & Nowakowski, 2011) — texto definitivo.
Para um grafo específico, desenhe, identifique cantos/conjuntos dominantes, e simule estratégias de policiais manualmente ou com código.
