오일러 그래프
정의
$G$ 가 연결 그래프라고 하자. $G$ 의 모든 에지를 포함하는 닫힌 트레일이 존재하면 $G$ 를 오일러 그래프라 하고 그 트레일을 오일러 트레일이라 한다. 모든 에지를 포함하지만 닫혀있지 않은 트레일이 존재하면 $G$ 를 세미 오일러 그래프라 한다.
설명
우리에게는 한 붓 그리기 문제로도 익숙한 개념이다.
오일러 그래프에 대한 논의는 그 유명한 쾨니히스베르크의 다리 문제에서 시작되었다. 이 문제는 다음과 같이 도시에 놓인 7개의 다리를 한 번씩만 건너면서 처음 있는 위치로 돌아올 수 있는지에 관한 것이었다.
해법을 모른다면 언뜻 경우의 수를 다 따져봐야하는 막막한 문제로 보인다. 일단 수학 문제처럼 보이지도 않고, 모든 경우를 다 따져보면 풀릴 것 같은데 막상 따져보기가 쉽지는 않다.
위대한 수학자 오일러는 이것을 그래프 문제로 바꿔서 멋지게 해결해냈다. 놀라운 건 그래프 이론이 당시에 학계의 관심을 받기는커녕 공간을 위상적으로 바라본다는 발상 자체도 없었을 때의 해법이라는 것이다. 말하자면 오일러는 미래의 개념을 가져와 미래의 방법으로 문제를 풀어버렸다.
다음은 그 풀이의 핵심이 되는, 오일러 그래프의 동치 조건을 보이는 정리다.
정리 1
$G$ 가 연결 그래프라고 하자.
$G$ 가 오일러 그래프인 것과 $G$ 의 모든 버텍스의 차수가 짝수인 것은 동치다.
증명
$(\Rightarrow)$
$P$ 가 $G$ 의 오일러 트레일이라고 하자. $P$ 는 어떤 버텍스를 지날 때 그 버텍스에 딸린 에지를 두 개 지나야한다. 모든 에지는 $P$ 에 단 한번씩만 속하므로, 각각의 버텍스의 차수는 $2$ 를 몇 번 더한 것이 된다. 따라서 모든 버텍스의 차수는 짝수여야한다.
$(\Leftarrow)$
$G$ 는 모든 버텍스의 차수가 짝수이므로 $2$ 이상이고 $G$ 에는 사이클 $C$ 가 존재함을 보장할 수 있다. $G$ 의 모든 에지가 $C$ 에 속하면 증명할 것이 없다. 이제 이 $C$ 가 지나는 에지만을 모두 지운 그래프 $H = G \setminus C$ 를 생각해보자. $H$ 는 $G$ 에서 어떤 사이클 $C$ 가 사라져있으므로 연결성은 잃었을 수 있지만, 각 버텍스 당 에지는 $2$ 개씩만 줄어들었으므로 차수는 여전히 짝수다. 또한 $H$ 의 각 컴포넌트는 $C$ 와 공통된 버텍스를 적어도 하나씩은 가진다. 같은 방법으로 각 컴포넌트에 대해 새로운 사이클을 찾아 제거하는 것을 널 그래프가 될 때까지 반복하고, 그 사이클들의 시퀀스를 $\mathcal{C}_{k}$ 라 하자. 이 사이클들은 그 전에 찾아진 사이클들과 반드시 공통된 버텍스를 가지므로 모든 사이클을 경유할 수 있고, 따라서 모든 에지를 지나는 트레일이 존재하게 되므로 $G$ 는 오일러 그래프다.
■
같이보기
- 모든 버텍스를 포함하는 닫힌 패스가 존재하는 그래프 : 헤밀톤 그래프
- 오일러 트레일의 존재성과 구체적으로 찾는 것은 다른 일이다. 오일러 그래프임이 보장되었을 때 오일러 트레일을 찾는 알고리즘으로써 플뢰리 알고리즘이 알려져있다.
Wilson. (1970). Introduction to Graph Theory: p32. ↩︎