기하적 듀얼 그래프

기하적 듀얼 그래프

정의 1

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


설명

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

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

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

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

20200415\_145722.png

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

기초 성질

증명

[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)$

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


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

댓글