평면 그래프와 쿠라토프스키 정리

평면 그래프와 쿠라토프스키 정리

평면 그래프의 정의

그래프를 평면에 그렸을 때 에지가 겹치지 않게 그릴 수 있으면 그 그래프를 평면 그래프라 한다.

설명

평면 그래프가 그려지면서 평면 상에서 구분되는 영역들을 페이스Face라 부른다. 다음과 같은 평면 그래프 $K_{4}$ 는 네 개의 페이스 $f_{1}, f_{2}, f_{3}, f_{4}$ 를 가지며, 그 중에서도 특히 바운드 되지 않은 $f_{4}$ 를 무한 페이스Infinite Face라 부른다.

20200406\_120429.png

평면 그래프는 그 이름 그대로 평면에 겹치는 부분 없이 그려낼 수 있는 그래프를 말한다. 이해를 돕기 위해서는 평면 그래프가 아닌 그래프가 뭔지 보는 편이 더 좋다. 가령 컴플리트 그래프 $K_{5}$ 와 이분 그래프 $K_{3,3}$ 은 평면 그래프가 아닌데, 다음과 같이 무슨 수를 써도 겹치는 에지가 있기 때문이다.

20200406\_020040.png 수학도라면 당연히 평면 그래프가 되는 조건이 무엇인가가 궁금해진다. 이에 대해서는 위의 예가 일반화된 정리가 알려져있다.

쿠라토프스키 정리 1

그래프가 평면 그래프인 것과 그 그래프의 서브 그래프 중 $K_{5}$ 나 $K_{3,3}$ 과 호메오멀픽한 것이 없는 것은 동치다.

의의

쉽게 말해 $K_{5}$ 비슷한 것과 $K_{3,3}$ 비슷한 것이 포함 되어 있으면 평면 그래프가 아니고, 없으면 평면 그래프라는 것을 보장해주는 정리다. 언뜻 평면 그래프는 이 정리로 모든 것이 정복되는 것처럼 보이지만, 그래프 이론은 평면 그래프를 뿌리로 수많은 개념과 문제들을 쏟아내게 되었다. 가장 간단한 일반화로써 $k \in \mathbb{N}$ 개의 에지가 겹치는 것을 허용하는 것으로 시작해 수학 전반에서 흔히 등장하는 듀얼, 점과 선과 면 같은 도형을 다루는 논증기하학의 영역은 물론 공간의 구조 자체에 관심을 가지는 조합위상론으로도 이어지는 대장정의 시작인 것이다.

그러니 그래프 전공자가 아닌 이상 평면 그래프에 대한 다양한 정리를 숙지하고 증명에 익숙해져야한다고는 하지 않겠지만, 좀 더 넓은 수학의 세계를 보기 위해 반드시 알아두긴 해야할 개념이라고는 할 수 있겠다. 정의를 보면 알겠지만 애초에 평면 그래프를 이해하기 위해 방대한 수학적 기반이 필요한 것도 아니다. 그저, 알아두기라도 하자.


  1. Wilson. (1970). Introduction to Graph Theory: p2. ↩︎

댓글