다중 그래프

다중 그래프 (Multigraph)는 그래프 이론에서 두 정점 사이에 여러 개의 변(edge)을 가질 수 있는 그래프를 의미한다. 일반적인 그래프에서는 두 정점 사이에 최대 하나의 변만이 존재할 수 있지만, 다중 그래프에서는 여러 개의 변이 존재할 수 있다는 점에서 차이를 보인다. 이러한 변들을 다중 변(multiple edges) 또는 평행 변(parallel edges)이라고 부른다.

다중 그래프는 네트워크 모델링, 관계 표현, 데이터 구조 등 다양한 분야에서 활용된다. 예를 들어, 도로망에서 두 도시 사이에 여러 개의 도로가 존재하는 경우, 소셜 네트워크에서 두 사용자 간에 여러 종류의 관계가 존재하는 경우 등을 다중 그래프로 표현할 수 있다.

정의

다중 그래프는 다음과 같이 형식적으로 정의될 수 있다:

• 정점 집합 (V): 그래프를 구성하는 정점들의 집합
• 변 집합 (E): 정점 쌍을 연결하는 변들의 집합. 이 때, 변은 정점 쌍과 연결되는 변의 개수를 나타내는 multiplicity를 가질 수 있다.

표기법

다중 그래프는 G = (V, E)로 표기하며, 여기서 V는 정점 집합, E는 변 집합을 나타낸다. 변 집합 E는 각 변과 그 변의 multiplicity를 나타내는 함수 m: V x V -> N (여기서 N은 음이 아닌 정수 집합)으로 정의될 수도 있다.

예시

두 정점 A와 B 사이에 세 개의 변이 존재하는 다중 그래프는 다음과 같이 표현할 수 있다:

• V = {A, B}
• E = {(A, B), (A, B), (A, B)}

또는, multiplicity 함수를 사용하여 m(A, B) = 3으로 표현할 수도 있다.

관련 개념

• 단순 그래프 (Simple Graph): 두 정점 사이에 최대 하나의 변만 존재하는 그래프.
• 가중 그래프 (Weighted Graph): 각 변에 가중치가 할당된 그래프.
• 방향 그래프 (Directed Graph): 변에 방향이 있는 그래프. 다중 그래프는 방향 그래프와 결합하여 다중 방향 그래프(directed multigraph)를 형성할 수도 있다.

응용 분야

• 교통 네트워크: 도로망, 철도망 등에서 두 지점 사이의 경로를 나타낼 때 유용하게 사용될 수 있다.
• 통신 네트워크: 네트워크 연결 상태를 모델링할 때, 여러 개의 연결을 표현하는 데 사용될 수 있다.
• 소셜 네트워크: 사용자 간의 다양한 관계를 표현하는 데 활용될 수 있다.