Das Cops-and-Robber-Spiel auf Graphen

Sei \(G = (V,E)\) ein Graph und \(k \in \mathbb{N}\) eine natürliche Zahl.

Das Cops-and-Robber-Spiel auf \(G\) mit \(k\) Cops wird von zwei Spieler*innen gespielt: Cops und Robber. Die Spielerin Cops steuert die Polizistinnen \(C_1, \dots, C_k\) und der Spieler Robber steuert den Räuber \(R\). Das Spiel verläuft in Runden. Zunächst legen die Spieler*innen die Startpositionen ihrer Spielfiguren fest und im Anschluss wird abwechselnd gezogen. Die Positionen sind dabei die Knoten des Graphens und in einem Zug können die Spielfiguren auf benachbarte Knoten gezogen werden oder stehen bleiben. Ziel von Cops ist, den Räuber zu fangen, und Ziel von Robber ist es, sich nicht fangen zu lassen.

In Runde 0 bestimmt Cops die Positionen \(c_0 = (c_{0,1}, \dots, c_{0,k}) \in V^k\) der Polizistinnen \(C_1, \dots, C_k\).

In Runde 1 bestimmt Robber die Position \(r_1 \in V\) des Räubers und anschließend bewegt Cops die Polizistinnen auf die Positionen \(c_1 = (c_{1,1}, \dots, c_{1,k}) \in V^k\).

In allen darauf folgenden Runden \(i+1\) bewegt zunächst Robber den Räuber von Position \(r_i\) auf \(r_{i+1}\) und im Anschluss bewegt Cops die Polizistinnen von \(c_i\) nach \(c_{i+1}\).

Dabei gilt für alle \(i \geq 1\), dass \(r_{i+1} \in N(r_i) \cup \{r_i\}\). Weiterhin gilt für alle \(i \geq 0\) und alle \(j \in [k]\), dass \(c_{i+1,j} \in N(c_{i,j}) \cup \{c_{i,j}\}\).

Wer einen ungültigen Zug macht, verliert das Spiel. Darüber hinaus gewinnt die Spielerin Cops, wenn eine Polizistin den Räuber fängt, also falls eine Runde \(i \geq 1\) und eine Polizistin \(C_j\) existiert, sodass \(c_{i,j} = r_i\) gilt. Sonst gewinnt der Spieler Robber.