A game of cops and robbers on planar graph
A game of cops and robbers on planar graph
“Cops and Robbers” 게임은 그래프 $G$ 상에서 정의되는 추격-회피 문제의 한 유형이다. 이 게임은 두 명의 플레이어, ‘Cop’ (C)와 ‘Robber’ (R)가 참여한다.
게임의 규칙은 다음과 같다. 먼저 Cop이, 그 다음 Robber가 그래프 상의 정점을 선택하여 위치한다. 이후 두 플레이어는 교대로 인접한 정점으로 이동한다. Cop이 Robber와 동일한 정점을 차지하게 되면 Cop의 승리로, Robber가 이러한 상황을 무한히 회피할 수 있다면 Robber의 승리로 규정된다. 본 논의는 Robber가 현재 위치에 머무르는 것을 허용하는 버전을 기준으로 한다.
그래프의 구조에 따라 게임의 결과가 결정된다. 예를 들어, 트리 그래프는 Cop이 항상 승리하는 ‘cop-win’ 그래프의 예시이다. 반면, 길이가 4 이상인 사이클 그래프는 Robber가 Cop의 반대편 위치를 유지함으로써 승리할 수 있는 ‘robber-win’ 그래프이다.
Cop 플레이어가 여러 명($k$)으로 확장될 경우, Robber를 포획하는 데 필요한 최소한의 Cop 수를 해당 그래프 $G$의 cop number라 정의하고 $c(G)$로 표기한다.
그러나 그래프의 클래스를 평면 그래프로 한정할 경우, 주목할 만한 결과가 도출된다. 이 글은 평면 그래프의 cop number에 대한 상한을 제시한다.
Theorem: 모든 유한 연결 평면 그래프 $G$에 대하여, $c(G) \le 3$ 이다.
평면 그래프 Cop Number의 하한선과 등호 성립
모든 평면 그래프 $G$에 대해 $c(G) \le 3$’이라는 상한을 증명하기에 앞서, 이 상한선 ‘3’이 실제로 도달 가능한 값인지 검토한다. 이를 위해 특정 조건을 만족하는 그래프의 cop number 하한선을 규명하는 다음 정리를 살펴본다.
Theorem 1. 그래프 $G$의 최소 차수가 $\delta(G) \ge n$ 이고, 3-사이클 또는 4-사이클을 포함하지 않는다면, $c(G) \ge n$ 이 성립한다.
Proof) 위 정리는 $n-1$명의 Cop으로는 Robber를 포획할 수 없는 Robber의 승리 전략이 존재함을 보여줌으로써 증명된다.
$n-1$명의 Cop이 $r$을 포획하기 위해 이동했을 때, 각각의 Cop은 $r$의 인접 정점들 중 최대 1개만을 ‘위협’(즉, 해당 정점을 점유하거나 또는 그 정점과 인접함)할 수 있다. 만약 어떤 Cop $C$가 $r$의 인접 정점 두 개($n_1, n_2$)와 동시에 인접하다면, $r-n_1-C-n_2-r$ 형태의 4-사이클이 생성되어 모순된다. 만약 어떤 Cop $C$가 $r$의 인접 정점 $n_1$에 위치하고 $n_2$와 인접하다면, $r-n_1(=C)-n_2-r$ 형태의 3-사이클이 생성되어 모순된다.
결론: $n-1$명의 Cop은 최대 $n-1$개의 $r$의 인접 정점만을 위협할 수 있다. $r$은 최소 $n$개의 인접 정점을 가지므로, Robber에게는 항상 최소 1개 이상의 ‘안전한’ 인접 정점이 다음 이동을 위해 보장된다. Robber는 이 전략을 무한히 반복하여 포획을 회피할 수 있다.
평면그래프인 정12면체에 Theorem 1을 적용할 수 있다.
-
정십이면체 그래프는 모든 정점의 차수가 3이다.
-
그래프 구조상 3-사이클과 4-사이클을 포함하지 않는다.
-
마지막으로 이 그래프는 평면 그래프이다.
Theorem 1을 $n=3$으로 적용하면, 정십이면체 그래프의 cop number는 $3$ 이상임을 도출할 수 있다.
Cop의 path 통제
평면 그래프에서 3명의 Cop이 승리하는 전략을 구축하기 위해서는, 먼저 Cop 한 명이 그래프의 특정 path를 효과적으로 방어하는 방법을 이해해야 한다.
Lemma. 그래프 $G$ 내의 두 정점 $u, v$ 사이의 임의의 최단 경로 $P$가 주어졌을 때, Cop 한 명($C$)은 유한한 수의 이동을 통해 이 경로 $P$를 ‘통제’할 수 있다. 단, $G$ 내에 최소 2명 이상의 Cop이 존재한다고 가정한다. (이 가정은 Robber가 자신의 턴에 움직이지 않고 머무를 때, 경로를 통제하는 Cop 역시 경로 상의 특정 위치에서 대기할 수 있어야 함을 보장하기 위해 필요하다.)
여기서 ‘경로를 통제한다’는 것은, Robber가 경로 $P$ 상의 어떤 정점으로든 이동하는 순간 즉시 Cop에게 잡히게 됨을 의미한다. 즉, Cop은 경로 $P$ 전체를 Robber의 접근이 불가능한 영역으로 만든다.
Proof) 이 보조정리의 증명은 Cop이 특정 거리 조건을 만족시키고 유지하는 전략을 통해 달성된다.
Cop C는 경로 $P$ 상의 정점 $c$에, Robber R은 그래프 상의 임의의 정점 $r$에 위치한다. Cop의 목표는 $P$ 상의 모든 정점 $z$에 대하여 $d(r, z) \ge d(c, z)$을 만족시키는 것이다. (*)
Cop은 이 조건(*)을 항상 유지할 수 있다.
-
초기화: Cop은 $P$ 위의 정점으로 이동한 뒤, 만약 $d(r, z) < d(c, z)$ 를 만족하는 $z \in P$가 있다면 그 $z$ 방향으로 $P$를 따라 이동함으로써 유한한 이동 내에 조건(*)을 만족시킬 수 있다. Cop을 기준으로 path의 양쪽 방향으로 $d(r, z) < d(c, z)$를 만족하는 $z$가 있으면 $P$의 최단경로 정의에 모순이다.
-
Cop의 대응: (*)를 만족하는 상황에서 Robber가 $r$에서 인접한 정점 $s$로 이동했다고 가정하자. 삼각 부등식에 의해 모든 $z \in P$에 대해 $d(s, z) \ge d(r, z) - 1$ 이며, 조건(*)에 의해 $d(s, z) \ge d(c, z) - 1$ 이 성립한다. 만약 Robber의 이동으로 인해 $d(s, z_0) = d(c, z_0) - 1$ 이 되는 정점 $z_0 \in P$가 존재한다면, Cop은 $P$를 따라 $z_0$ 방향으로 한 칸 이동하여 새로운 위치 $c’$가 된다. 이때 $d(c’, z_0) = d(c, z_0) - 1$ 이므로, $d(s, z_0) = d(c’, z_0)$ 가 되어 조건(*)은 새로운 위치 $c’$에 대해서도 여전히 유지된다. $d(s, z_0) = d(c, z_0)-1$을 만족하는 $z_0$가 $c$를 기준으로 path의 양방향에 존재한다면 $P$의 최단경로 정의에 모순이다.
결론: 결론적으로, Cop 한 명은 자신이 위치한 최단 경로 $P$를 Robber가 절대 밟을 수 없는 영역으로 만들 수 있다. 이 ‘경로 통제’ 능력은 3명의 Cop이 평면 그래프 전체를 분할하고 Robber의 영역을 체계적으로 축소시키는 핵심 도구로 사용된다.
Main theorem: $c(G) \le 3$
$c(G) \ge 3$ 인 평면 그래프가 존재함을 보였고, Cop의 경로 통제 보조정리를 확립했다. 이제 이 요소들을 결합하여 본 글의 핵심 정리를 증명한다.
Theorem 2. 모든 유한 연결 평면 그래프 $G$에 대하여, $c(G) \le 3$ 이다.
증명 전략 개요: 증명은 3명의 Cop ($C_1, C_2, C_3$)을 이용해서 robber가 안전하게 있을 수 있는 영역을 축소한다. $i$번째 단계에서 Robber가 안전하게 위치할 수 있는 영역을 $G$의 부분 그래프 $R_i$로 정의한다. Cop들의 유한한 수의 이동을 통해, 이 영역을 $R_{i+1} \subsetneq R_i$ 로 엄격하게 축소시킬 수 있음을 보인다. $G$는 유한 그래프이므로, 이 과정은 유한한 단계 내에 $R_i$를 공집합 또는 단일 정점으로 만들어 Robber의 포획을 보장한다.
이 전략은 Cop이 Robber의 영역을 경계 짓는 방식에 따라 두 가지 주요 상황으로 나뉜다.
(상황 A) 1-Cop 경계: 1명의 Cop ($C_1$)이 특정 정점 $u$에 위치한다. Robber는 $G-u$의 연결 컴포넌트 중 하나인 $R_i$에 위치한다. $C_1$은 $u$에 머무르며 Robber가 $u$를 통해 $R_i$를 탈출하는 것을 방지한다.
(상황 B) 2-Cop 경계: 2명의 Cop ($C_1, C_2$)이 각각 두 개의 교차하지 않는 $u, v$ 경로 ($P_1, P_2$)를 통제한다. $P_1$과 $P_2$는 $u$와 $v$에서만 만나며, 평면 그래프를 안과 밖으로 분할한다. $P_1$과 $P_2$로 이루어진 cycle의 바깥을 $R_i$로 정의하자. $P_1$은 $P_1 \cup P_2 \cup R_i$에서 $u$와 $v$를 잇는 최단경로이고, $P_2$는 $P_2 \cup R_i$에서 $u$와 $v$ 사이의 최단경로이다. Robber는 $P_1, P_2$로 이루어진 사이클의 외부와 대응하는 영역 $R_i$에 갇혀 있다.
이제 각 상황에 대해서 경찰이 어떻게 움직일지 정해보자.
(상황 A) 1-Cop 경계
- $u$와 $R_i$ 사이의 간선이 $uu’$ 1개라면 $u’$에 새로운 cop을 투입한다. 상황 A로 다시 돌아온다.
- $R_i$에 $u$와 인접한 정점이 2개 이상인 경우 $u$와 인접한 $R_i$ 내부의 두 정점을 $a$와 $b$라고 하자. $a$와 $b$를 잇는 최단경로와 ${a, u, b}$를 $P_1, P_2$로 하면 상황 B가 된다.
(상황 B) 2-Cop 경계
- $P_1$과 $P_2$ 이외의 $u, v$ 경로가 존재하지 않는 경우는 $R_i$가 $P_1, P_2$로 이루어진 사이클과 정확히 1개의 정점을 공유하는 컴포넌트로 이루어진 경우이다. 이때는 $r$이 존재하는 컴포넌트와 $P_1P_2$의 교점에 cop을 놓아서 상황 A로 변경할 수 있다. 아래 그림을 참고하라.
- $P_1$과 $P_2$ 이외의 $u, v$ 경로가 존재한다고 가정하자. $u, v$ 경로 중 $P_1, P_2$가 아닌 최단경로 $P_3$를 잡아보자. 경우에 따라 $P_3$와 $P_1$과 $P_2$ 중 하나를 연결해 새로운 사이클을 만들어 상황 B로 다시 돌아올 수 있다. 자세한 증명은 논문을 참고하기를 바란다.
결론: (상황 A)와 (상황 B)에서 Robber의 영역 $R_i$를 엄격하게 축소시키는 시행을 반복할 수 있다. $G$는 유한 그래프이므로, $R_i$의 정점 수는 유한하다. 따라서 이 과정은 유한한 횟수만큼 반복된 후, $R_i$는 결국 Robber가 위치한 단일 정점으로 축소된다. 이때 3명의 Cop은 Robber가 인접한 모든 정점으로 이동하는 것을 차단하고 포획할 수 있다.
참고문헌
Aigner, M., & Fromme, M. (1984). A game of cops and robbers. Discrete Applied Mathematics, 8(1), 1-11. https://www.sciencedirect.com/science/article/pii/0166218X84900738