📂그래프이론

추상적 듀얼 그래프

빌드업

기하적 듀얼 그래프의 성질 [3]: 평면 그래프 $G$ 와 그 기하적 듀얼 그래프 $G^{ \ast }$ 에 대해,$C \subset E(G)$ 가 사이클 $\iff$ $C^{ \ast } \subset E \left( G^{ \ast } \right)$ 는 컷셋

추상적 듀얼 그래프는 직관적으로 평면 그래프에 대해 기하적 듀얼 그래프와 달리 일반적인 그래프에 대해서 추상적으로 정의된다. 듀얼 그래프가 어떠한 방법으로 만들어지는 것이 아니라, 듀얼의 성질을 가지면 듀얼 그래프라고 하는 식이다.

정의 ¹

그래프 $G$ 가 주어져있다고 하자. $E(G)$ 와 $E \left( G^{ \ast } \right)$ 사이에 다음을 만족하는 일대일대응이 존재하면 $G^{ \ast }$ 를 $G$ 의 추상적 듀얼 그래프라고한다.

기초 성질

추상적 듀얼 그래프는 다음과 같이 상식적인 성질을 가진다.

• [1]: $G^{ \ast }$ 가 $G$ 의 추상적 듀얼이면 $G$ 는 $G^{ \ast }$ 의 추상적 듀얼이다.
• [2]: 그래프가 평면 그래프인 것은 추상적 듀얼이 존재하는 것과 동치다.

설명

성질 [2]는 그 증명에서 쿠라토프스키 정리를 사용하는데 내용이 강력해지지는 않기 때문에 학습자가 굳이 증명해야한다고 말할만한 가치는 없을지도 모른다. 그러나 그 스테이트먼트가 전해주는 의미는 짚고 넘어갈만하다. 평면 그래프의 추상적 듀얼이 존재한다는 것은 당연한 일이지만, 듀얼이 어떠한 형태든 존재한다는 것만으로 원래 그래프의 형태를 결정 짓는다는 사실은 수학적으로 전혀 당연하지 않기 때문이다.

이러한 쌍대성Duality의 개념은 조합론의 매트로이드로 이어진다.