📂그래프이론

그래프 이론에서 지도의 정의

정의 ¹

1. $3$-연결 평면 그래프를 지도라 정의한다.
2. 같은 에지를 사이에 두고 이웃한 페이스끼리 다른 색이 되도록 $k$ 개의 색을 칠할 수 있는 지도를 $k$-페이스 채색가능 지도라 한다.
3. 기존의 $k$-채색가능 그래프를 $k$-버텍스 채색가능 그래프라 한다.

---

• 평면 그래프가 그려지면서 평면 상에서 구분되는 영역들을 페이스라 부른다.

설명

1. $3$-그래프란 쉽게 말해 다음과 같이 지도라고 부를 수 없는 케이스를 제외시키기 위한 제약인데, 너무나 짧고 명료해서 아주 좋은 정의다. 다음은 각각 $1$개, $2$개의 버텍스로 단절되는 그래프의 예시로, 실제 지도에서는 있을 수 없는 경우다. 왼쪽의 경우엔 비현실적인 에지가 있어 하나의 붉은 버텍스를 제거하면 단절 그래프가 되며, 오른쪽의 경우엔 비현실적인 버텍스가 있어 양 옆의 붉은 버텍스를 제거하면 단절 그래프가 된다.

2. 이러한 지도의 각 구역, 즉 페이스를 구분되도록 다른 색으로 칠하려면 최소한 몇 가지 색이 있어야할까? 지도가 복잡할수록 색은 많아져야할 것 같지만, 바로 옆이랑만 다르면 되기 때문에 생각보다 많은 색이 필요하지는 않다. 예를 들어 다음은 세계지도를 단 $4$개의 색으로 칠한 것이다. 이러한 질문은 $k$-페이스 채색이라는 수학적 개념으로 추상화될 수 있다. 이는 전형적인 조합론 스타일의 문제로써, 단지 세계지도가 아니라 존재할 수 있는 모든 지도가 $4$개의 색으로 구별되게 채색이 가능한지에 대한 질문이 바로 $4$색 문제다.

3. 버텍스 컬러링은 단지 지도의 페이스 컬러링과 구분하기 위해 사용하는 말이다. $4$색 문제는 다음과 같은 정리를 통해 그래프 이론의 문제로 바꿔서 풀 수 있다.

정리

$G$ 가 심플 연결 평면 그래프고 $G^{ \ast }$ 는 그 기하적 듀얼이라고 하면 다음이 성립한다. $G$ 는 $k$-버텍스 채색가능 $\iff$ $G^{ \ast }$ 는 $k$-페이스 채색가능

증명

전략: 사실 증명이랄 것도 없고 듀얼 그래프의 개념에서 자연스럽게 얻을 수 있는 결과다.

---

$(\Rightarrow)$

$G$ 는 심플 연결 그래프이므로 $G^{ \ast }$ 는 지도다. 만약 $G$ 가 버텍스에 대한 $k$-컬러링을 가지면, 각각의 $v \in V(G)$ 에 대응되는 $G^{ \ast }$ 의 페이스 $f^{ \ast }$ 에 대해서도 그와 정확히 같은 $k$-컬러링을 줄 수 있다. 가정에서 $G$ 에서 인접한 버텍스끼리는 다르게 채색되었으므로, $G^{ \ast }$ 의 인접한 페이스끼리도 다르게 채색된다. 따라서 $G^{ \ast }$ 는 $k$-페이스 채색가능이다.

---

$(\Leftarrow)$

역의 증명과 본질적으로 다를 게 없다.

■