디랙의 정리(Dirac's Theorem)

written by jjycjn 2017. 2. 21. 12:59

어떤 마을에 $n$ 개의 집이 있다고 하자. 이제 이 마을에 어떤 집에 문제가 생겼을 때 각 집에 이 사실을 알릴 수 있는 비상연락망을 만들고자 한다. 이 때, 비상연락망이란 ABCDEA와 같이 순환적인 연락망 (이 때, 연락망이란 A가 B의 연락처를 알고 B 또한 A의 연락처를 아는 것을 뜻한다.) 이 존재하여 만일 집 C에 문제가 생겨도 DEAB 순으로 서로 연락이 가능해야 함을 뜻한다. 이러한 비상연락망을 만들기 위해서 각 집마다 다른 집의 연락처를 모두 알고 있다면 제일 이상적이겠지만, (비용 또는 보안의 문제 때문에) 각 집에서 알아야 하는 연락처의 개수를 최소화 하고 싶다. 이러한 상황에서 각 집은 최소한 몇개의 다른 집의 연락처를 알아야 할까?

만일 $n = 5$ 라 가정해 보자. 만일 모든 집이 적어도 두개의 다른 집의 연락처를 알고 있다면, 아래와 같이 비상연락망이 존재하는 경우, 또는 존재하지 않는 경우가 생긴다.

예를 들어 위 그림에서 첫번째 경우, 어떤 집에 문제가 생기더라도 나머지 네개의 집이 서로 연락이 가능하지만, 두번째 경우는, 만약 집 C가 문제가 생긴다면 예를 들어 집 A와 E는 서로 연락할 방법이 없다. 하지만, 모든 집이 적어도 세개의 다른 집의 연락처를 알고 있다면 언제나 비상연락망을 만들 수 있음을 알 수 있다. 아래 그림은 이러한 경우 중 몇가지 예를 보여준다.

이러한 차이가 생기는 이유는 무엇일까? 만약 $n$ 개의 집이 있다면, 각 집이 최소 몇 개의 다른집의 연락처를 알아야만 언제나 비상연락망을 만들 수 있을까? 이 문제에 대한 해답을 1952년 디랙(Gabriel Andrew Dirac)이 증명하였다. 아래의 디랙의 정리(Dirac's Theorem)와 그 증명을 간단하게 정리해 본다.

디랙의 정리 (Dirac's Theorem)

$G$ 가 $n \geq e$ 개의 점을 가진 단순그래프(simple graph)라 하자. 만약 $G$ 의 모든 점의 차수가 $n / 2$ 이상이면, $G$ 는 해밀턴그래프(Hamiltonian graph)이다. (즉, $G$ 의 한점에서 출발하여 모든 점을 거쳐 다시 출발점으로 돌아오는 경로가 존재한다.)

증명. $E$ 를 $G$ 의 모든 변(edge)들의 집합이라 하자. 우선 $G$ 가 연결그래프(connected graph)임을 보이자. 만약 $G$ 가 연결그래프가 아니라 가정하고 $G_{0}$ 을 $G$ 의 최소연결성분(minimal connected component)라 하자. 그러면 $G_{0}$ 의 최소성에 의해 자명하게 $| G_{0} | \leq n / 2$ 가 성립한다. 그러면 $G_{0}$ 의 점 $p$ 에 대하여

$\deg (p) \leq | G_{0} | - 1 \leq \frac{n}{2} - 1$

이 되어 문제의 가정에 모순이 생긴다.

이제 $P = v_{1} v_{2} \cdot v_{k}$ 가 $G$ 에서 최대경로(maximal path)라 하자. 그러면 점 $v_{1}$ 와 연결된 모든 점은 집합 ${v_{2}, v_{3}, \dots, v_{k}}$ 에 속해야만 한다. 만약 그렇지 않다면 (즉, $P$ 에 속하지 않는 점 $p$ 가 존재하여 $p v_{1} \in E$ 라면) $p v_{1} v_{2} \cdot v_{k}$ 인 경로가 존재하여 $P$ 의 최대성에 모순이 생기기 때문이다. 또한 $v_{1}$ 은 자기 자신과는 인접할 수 없으므로

$k \geq \deg (v_{1}) + 1 = \frac{n}{2} + 1$

이 성립한다. 여기서 $n \geq 3$ 을 가정했으므로 $k \geq 3$ 임을 알 수 있다.

또한 위와 유사한 논리를 적용하여 $v_{k}$ 와 연결된 모든 변은 ${v_{1}, v_{2}, \dots, v_{k - 1}}$ 에 속해야 함을 보일 수 있다. 이상의 사실을 다시 표현하면, 적어도 $n / 2$ 개의 $v_{i} \in {v_{2}, v_{3}, \dots, v_{k}}$ 는 $v_{1} v_{i} \in E$ 를 만족하고 동시에 적어도 $n / 2$ 개의 $v_{i} \in {v_{2}, v_{3}, \dots, v_{k}}$ 는 $v_{i - 1} v_{k} \in E$ 를 만족한다.

여기서 ( $v / 2 + v / 2 = n$ 개의 변과 $k - 1 \leq n - 1$ 개의 점에 대한) 비둘기집의 원리를 적용하면, 적어도 하나의 $v_{j} \in {v_{2}, v_{3}, \dots, v_{k}}$ 가 존재하여 $v_{1} v_{j} \in E$ 이고, $v_{j - 1} v_{k} \in E$ 임을 알 수 있다. 그러면

$C = v_{1} v_{j} v_{j + 1} \dots v_{k} v_{j - 1} v_{j - 2} \dots v_{1}$

은 순환(cycle)이 된다.

다음으로 이 순환 $C$ 가 해밀턴순환(Hamiltonian cycle)임을, 다시 말해 $k = n$ 임을 보이자. 만약 $C$ 에 속하지 않는 점 $p$ 가 존재한다면, $G$ 가 연결그래프이므로 어떤 $v_{i} \in C$ 가 존재하여 $p v_{i} \in E$ 가 성립한다. 하지만 이 경우 $p$ 와 $C$ 의 모든 점들을 잇는 경로를 만들 수 있으므로 $P$ 의 최대성에 모순이 생긴다. 따라서 $G$ 의 모든 점이 순환 $C$ 에 속하고 $G$ 는 해밀턴그래프임을 알 수 있다.