📂그래프이론

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

정의

평면 그래프

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

설명

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

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

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

정리

쿠라토프스키 정리 ¹

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

의의

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

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

자폐증 테스트

오래된 인터넷 밈 중 하나로써, 위와 같은 문제를 자폐증 테스트^{autism test}라 한다. 문제에서는 수도와 전력, 가스를 세 개의 집에 공급하되 그 선이 교차해서는 안 된다는 제한을 걸며 “어렵지만 가능하다"고 말한다. 이것을 오로지 수학문제로 바라본다면, 우리는 이것이 쿠라토프스키 정리에 의해 불가능하다고 반박할 수 있다. 이런 짤들이 ‘자폐증 테스트’라 불리는 이유는 아마 ‘불가능한데도 풀이에 집착하게 만들고, 그렇게 모든 경우의 수를 따져보게 되는 모습이 자폐증과 비슷하다’는 식의 경멸적, 혐오성 조크라서 아닌가 싶다.

수학문제가 아닌 식으로 접근하면 위와 같은 해법도 있다. 사실 자폐증 테스트의 건전한 재미는 이렇게 문제의 조건은 어겨서 억지스럽거나 신박한 반칙들에 있다.