📂그래프이론

기하적 듀얼 그래프

정의 ¹

주어진 평면 그래프 $G$ 에 대해 기하적 듀얼 그래프 $G^{ \ast }$ 는 다음과 같이 만들어진다.

• Step 1.
  $G$ 의 각 페이스 $f$ 에 대응되는 버텍스 $v^{ \ast }$ 를 찍는다.
• Step 2.
  $G$ 의 각 에지 $e$ 와 겹치도록 대응되는 에지 $e^{ \ast }$ 를 긋는다.
• Step 3.
  원래의 그래프는 지우고 $v^{ \ast }$ 와 $e^{ \ast }$ 로 이루어진 그래프를 $G^{ \ast }$ 로 둔다.

---

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

설명

쌍대성^duality 이란 수학과 물리학 전반에서 흔히 찾아볼 수 있는 보편적 개념으로써, 함수해석학에서는 듀얼 스페이스와 같은 식으로 등장한다. 구체적으로 다음의 그래프 $G$ 에 대해 그 듀얼 그래프 $G^{ \ast }$ 를 만들어보자:

그래프 $G$ 는 세 개의 페이스 $f_{1} , f_{2}, f_{3}$ 를 가지고 있다. 각 페이스에 다음과 같이 세 개의 버텍스 $v^{ \ast }$ 를 찍자.

이제 각 $v^{ \ast }$ 를 잇는 에지 $e^{ \ast }$ 를 긋는다. 단, 이때 에지들은 모두 원래 그래프 $G$ 의 에지를 지나가도록 그어야한다.

원래의 그래프를 지우면 우리가 원하던 $G$ 의 듀얼 그래프 $G^{ \ast }$ 만이 남는다. 보다시피 $G$ 가 심플 그래프라고 $G^{ \ast }$ 역시 심플 그래프일 이유는 없음에 주목하라.

한편 듀얼 그래프는 다음과 같이 상식적인 성질들을 가지며, 특히 성질 [3]은 듀얼이라는 개념이 추상적으로 확장될 수 있다는 가능성을 준다.

기초 성질

• [1]: 연결 평면 그래프 $G$ 가 $n$ 개의 버텍스, $m$ 개의 에지, $f$ 개의 페이스를 가지고 있고 그 기하적 듀얼 그래프 $G^{ \ast }$ 가 $n^{ \ast }$ 개의 버텍스, $m^{ \ast }$ 개의 에지, $f^{ \ast }$ 개의 페이스를 가진다고 하면 $$ n^{ \ast } = f \\ m^{ \ast } = m \\ f^{ \ast } = n $$
• [2]: $G$ 가 연결 평면 그래프면 $G^{\ast \ast}$ 는 $G$ 와 아이소멀픽하다.
• [3]: 평면 그래프 $G$ 와 그 기하적 듀얼 그래프 $G^{ \ast }$ 에 대해, $C \subset E(G)$ 가 사이클 $\iff$ $C^{ \ast } \subset E \left( G^{ \ast } \right)$ 는 컷셋

증명

[3]

$(\Rightarrow)$

$G$ 의 사이클 $C$ 는 적어도 하나의 페이스를 둘러싸고 있으므로 이 페이스들에 대응되는 $G^{ \ast }$ 의 버텍스 집합 $S \ne \emptyset$ 가 존재할 것이다. $C$ 에 대응되는 $C^{ \ast }$ 을 $G^{ \ast }$ 에서 제거하면 $G^{ \ast }$ 는 $S$ 만으로 이루어진 그래프와 $V(G) \setminus S$ 만으로 이루어진 두 개의 서브그래프로 나뉘어지므로, $C^{ \ast }$ 는 $G^{ \ast }$ 의 컷셋이 된다.

---

$(\Leftarrow)$

사실상 위와 같으므로 생략한다.

■