듀얼 그래프

듀얼 그래프 (Dual Graph)는 주어진 평면 그래프 또는 다면체의 각 면에 정점을 할당하고, 인접한 면끼리 변으로 연결하여 얻는 그래프이다. 원래 그래프를 원 그래프라고 부르며, 원 그래프의 위상적 성질을 보존하는 중요한 개념이다.

정의

평면 그래프 G의 듀얼 그래프 G*는 다음과 같이 정의된다.

1. G의 각 면 f에 대해 G*에 정점 v_f를 할당한다.
2. G의 두 면 f₁과 f₂가 변 e를 공유할 때, G에서 v_f1과 v_f2 사이에 변 e를 추가한다.

특징

• 원 그래프가 평면 그래프이면 듀얼 그래프 또한 평면 그래프이다.
• 듀얼 그래프의 듀얼 그래프는 원 그래프와 동형일 필요는 없다. (특히, 원 그래프가 연결 그래프가 아닐 경우)
• 각 면을 정점으로 바꾸고 인접한 면을 변으로 연결하는 방식이므로, 원 그래프의 면의 수는 듀얼 그래프의 정점의 수가 되고, 원 그래프의 정점의 수는 듀얼 그래프의 면의 수가 된다.
• 듀얼 그래프는 그래프 채색 문제, 네트워크 흐름 문제 등 다양한 그래프 이론 문제 해결에 활용된다.
• 원 그래프가 다면체인 경우, 듀얼 그래프는 해당 다면체의 쌍대 다면체와 관련된다.

예시

정사각형 격자 그래프의 듀얼 그래프는 정사각형 격자 그래프이다. 정육면체의 듀얼 그래프는 팔면체이다.

주의 사항

• 그래프가 평면 그래프가 아니면 듀얼 그래프를 정의하기 어렵다.
• 듀얼 그래프는 유일하게 결정되지 않을 수 있다. (특히, 원 그래프에 다중 변이 있는 경우)