다중 그래프(多重graph, 영어: multigraph)는 그래프 이론에서 다루는 수학적 대상의 하나로, 두 꼭짓점(vertex) 사이에 여러 개의 변(edge)이 허용되는 그래프의 일반화이다. 일반적인 그래프(단순 그래프, simple graph)에서는 두 꼭짓점 사이에 최대 하나의 변만 존재할 수 있지만, 다중 그래프에서는 동일한 두 꼭짓점을 연결하는 여러 개의 변, 즉 중복 변(parallel edge 또는 multiple edge)이 존재할 수 있다. 또한 일부 정의에서는 한 꼭짓점에서 출발하여 자기 자신으로 돌아오는 변인 고리(loop)도 허용된다.
정의
다중 그래프는 기초적으로 다음과 같은 순서쌍으로 정의된다. G = (V, E, ∂)에서 V는 꼭짓점의 집합, E는 변의 집합, ∂: E → S²(V)는 각 변에 그 끝점을 할당하는 함수이다. 여기서 S²(V) = {{u, v} : u, v ∈ V}는 V의 원소들로 구성된 모든 2원소 부분집합(또는 1원소 부분집합, 즉 고리)의 집합이다. 만약 ∂e = {u, v}라면 u와 v를 변 e의 끝점(endpoint)이라고 한다. 양 끝점이 같은 변(즉 ∂e = {v}인 경우)을 고리(loop)라고 한다.
다중 그래프에서 꼭짓점 v의 차수(degree)는 다음과 같이 계산된다. deg v = |{e ∈ E(G) : v ∈ ∂e ∧ |∂e| = 2}| + 2|{e ∈ E(G) : {v} = ∂e}|. 즉, 고리는 차수에서 두 배로 계산된다.
관련 개념과의 관계
단순 그래프(simple graph)는 고리가 없고 두 꼭짓점 사이에 최대 하나의 변만 존재하는 다중 그래프의 특수한 경우이다. 반대로, 주어진 다중 그래프에서 변의 중복을 무시하고 고리를 삭제하면 단순 그래프를 얻을 수 있다.
화살집(quiver)은 변에 방향이 부여된 다중 그래프로, 유향 그래프(directed graph)와 다중 그래프의 공통적인 일반화로 볼 수 있다. 유향 다중 그래프(directed multigraph)는 각 변이 방향을 가지며, 동일한 시점과 종점을 가지는 여러 개의 호(arc)를 허용한다.
표현과 응용
다중 그래프는 인접 행렬(adjacency matrix)로 표현할 경우, 행렬의 각 성분이 0 또는 1 대신 두 꼭짓점 사이의 변의 개수를 나타내는 정수값을 가진다. 고리가 있는 경우 대각 성분에 해당 값이 기록된다.
다중 그래프는 항공사의 항로망(동일한 두 도시를 연결하는 여러 항공편), 전기 회로 분석, 통신 네트워크, 한붓그리기 문제(오일러 경로) 등 두 대상 사이에 여러 관계가 존재할 수 있는 현실 세계의 다양한 상황을 모델링하는 데 사용된다.
범주론적 관점
범주론에서 다중 그래프의 범주(Multigraph)는 쉼표 범주(comma category) Set ↓ S²로 정의될 수 있으며, 여기서 S²: Set → Set는 S²(V) = {{u, v} : u, v ∈ V}로 주어지는 자기 함자이다. 또한 다중 그래프의 범주는 특정 작은 범주 위의 준층 범주(presheaf category)로도 표현될 수 있다.
참고 문헌
- Diestel, Reinhard (2010). Graph Theory, 4th ed. Graduate Texts in Mathematics 173. Springer. ISBN 978-3-642-14278-9.
- "Multigraph". Encyclopedia of Mathematics. Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
- Weisstein, Eric Wolfgang. "Multigraph". Wolfram MathWorld.
