다중 그래프

1. 개요

다중 그래프는 그래프 이론에서 꼭짓점과 변으로 구성된 그래프의 일반화된 개념이다. 변은 여러 개가 존재할 수 있으며, 자기 자신으로 연결되는 고리(루프)를 허용한다. 다중 그래프는 무향, 유향, 혼합 다중 그래프로 분류되며, 변의 방향성 유무에 따라 정의가 달라진다. 또한, 다중 그래프는 변에 고유한 정체성이 있는지 여부에 따라 정의가 구분된다. 라벨링 개념을 지원하며, 라벨이 지정된 다중 그래프는 정점과 호에 라벨이 부여된 그래프로 정의된다.

2. 정의

다중 그래프 $G=(V,E,\backslash partial)$는 다음과 같은 순서쌍이다.

* $V$는 꼭짓점(vertex^영어)의 집합이다.
* $E$는 변(edge^영어)의 집합이다.
* $\backslash partial\backslash colon\; E\backslash to\; S^2(V)$는 함수이다. 여기서 $S^2(V)=\backslash \{\backslash \{u,v\backslash \}\backslash colon\; u,v\backslash in\; V\backslash \}$이다. 만약 $\backslash partial\; e=\backslash \{u,v\backslash \}$라면, $u$와 $v$를 $e$의 끝점(endpoint^영어)이라고 한다. 양 끝점이 같은 변은 고리(loop^영어)라고 한다.

일부 저자는 다중 그래프에서 루프를 허용한다. 다른 저자는 이러한 그래프를 의사 그래프라고 부르며, 루프가 없는 경우에만 다중 그래프라는 용어를 사용한다.

2.1. 무향 다중 그래프

무향 다중 그래프는 변에 방향성이 없는 다중 그래프이다. 무향 다중 그래프는 변에 고유한 정체성이 없는 경우와 있는 경우로 나누어 정의할 수 있으며, 자세한 내용은 하위 섹션을 참고할 수 있다.

꼭짓점 $v\backslash in\; V(G)$의 차수(degree^영어) $\backslash deg\; v$는 다음과 같이 정의된다.

:$\backslash deg\; v=\backslash left|\backslash left\backslash \{e\backslash in\; E(G)\backslash colon\; v\backslash in\backslash operatorname\{end\}(G)\backslash land|\backslash operatorname\{end\}(G)|=2\backslash right\backslash \}\backslash right|+2\backslash left|\backslash left\backslash \{e\backslash in\; E(G)\backslash colon\backslash \{v\backslash \}=\backslash operatorname\{end\}(G)\backslash right\backslash \}\backslash right|$

즉, 고리는 차수에서 두 배로 센다.

다중 그래프의 경우 그래프에 대한 대부분의 용어들이 적용되지만, 다른 경우도 있다. 예를 들어, 다중 그래프에서 변을 축약(contraction^영어)시키면, 중복되는 변들을 하나로 합치지 않으며, 고리 또한 남겨둔다.

2.1.1. 변에 고유한 정체성이 없는 경우

다중 그래프는 다음과 같이 정의된다.

* V는 집합이며, 정점 또는 노드라고 불린다.
* E는 정점의 순서가 없는 쌍의 멀티셋이며, 변 또는 선이라고 불린다.

2.1.2. 변에 고유한 정체성이 있는 경우

다중 그래프 $G=(V,E,\backslash partial)$는 다음과 같은 순서쌍이다.

* $V$는 집합이다. 이를 꼭짓점의 집합이라고 하며, 그 원소를 꼭짓점(vertex^영어)이라고 한다.
* $E$는 집합이다. 이를 변의 집합이라고 하며, 그 원소를 변(edge^영어)이라고 한다.
* $\backslash partial\backslash colon\; E\backslash to\; S^2(V)$는 함수이다. 여기서 $S^2(V)=\backslash \{\backslash \{u,v\backslash \}\backslash colon\; u,v\backslash in\; V\backslash \}$이다. 만약 $\backslash partial\; e=\backslash \{u,v\backslash \}$라면, $u$와 $v$를 $e$의 끝점(endpoint^영어)이라고 한다. 양 끝점이 같은 변을 고리(loop^영어)라고 한다. 다중 그래프 $G$의 꼭짓점의 집합은 $V(G)$, 변의 집합은 $E(G)$로 쓴다.

다중 그래프는 G := (V, E, r)로 구성된 순서쌍으로 정의할 수도 있다.

* V는 정점 또는 노드의 집합이다.
* E는 변 또는 선의 집합이다.
* r : E → {(x,y) : x, y ∈ V}, 각 변에 정점 쌍을 할당한다.

일부 저자는 다중 그래프가 루프를 가질 수 있도록 허용하는데, 즉 정점을 자기 자신에 연결하는 변을 허용한다. 반면, 다른 저자는 이러한 그래프를 의사 그래프라고 부르며, 루프가 없는 경우에만 다중 그래프라는 용어를 사용한다.

2.2. 유향 다중 그래프

변에 방향성이 있는 다중 그래프는 순서쌍 (V, A) 또는 (V, A, s, t)로 표현될 수 있다. 여기서 V는 꼭짓점 집합, A는 유향 변(호, 화살표) 집합, s는 각 변의 시작 꼭짓점을 나타내는 함수, t는 각 변의 끝 꼭짓점을 나타내는 함수이다.

다중 유향 그래프는 동일한 출발 노드와 도착 노드를 가진 다중 호(여러 개의 변)를 가질 수 있다는 점에서 유향 그래프와 다르다.

2.2.1. 변에 고유한 정체성이 없는 경우

다중 그래프는 유향 그래프의 일종으로, 동일한 출발 노드와 도착 노드를 가진 다중 호(여러 개의 변)를 가질 수 있다. 다중 유향 그래프는 꼭짓점 집합과 꼭짓점 순서쌍의 멀티셋(중복을 허용하는 집합)으로 정의된다.

2.2.2. 변에 고유한 정체성이 있는 경우 (화살집)

다중 그래프 화살통 G는 다음과 같은 4-튜플 순서쌍으로 정의된다.

: G := (V, A, s, t)

* V는 꼭짓점 또는 노드의 집합이다.
* A는 변 또는 선의 집합이다.
* $s\; :\; A\; \backslash rightarrow\; V$: 각 변에 그 시작 노드를 할당한다.
* $t\; :\; A\; \backslash rightarrow\; V$: 각 변에 그 목표 노드를 할당한다.

이 개념은 항공사가 제공하는 가능한 항공편 연결을 모델링하는 데 사용될 수 있다. 이 경우 다중 그래프는 도시들을 연결하는 방향이 있는 평행 변 쌍을 가진 유향 그래프가 되어, 해당 위치들 로와 에서 모두 비행하는 것이 가능하다는 것을 보여준다.

범주론에서 작은 범주는 연관적인 합성 법칙과 각 꼭짓점에서 합성의 좌항 및 우항 항등원으로 작용하는 구별되는 자체 루프를 갖춘 다중 그래프(자체 식별성을 가진 변)로 정의될 수 있다. 이러한 이유로 범주론에서 용어 그래프는 표준적으로 "다중 그래프"를 의미하며, 범주의 기본 다중 그래프는 기본 유향 그래프라고 한다.

3. 관련 개념

그래프는 고리가 없고, 두 꼭짓점 사이에 최대 하나의 변이 존재하는 다중 그래프이다.

화살집(quiver^영어)은 변이 방향을 갖춘 다중 그래프이다. 즉, 유향 그래프와 다중 그래프의 공통적인 일반화이다.

4. 라벨링

다중 그래프와 다중 유향 그래프는 그래프 라벨링 개념을 지원하지만, 이 경우 용어에 통일성은 없다. 라벨이 지정된 다중 유향 그래프는 라벨이 지정된 꼭짓점과 호(화살표)를 가진다.

4.1. 정의 1

라벨이 지정된 다중 방향 그래프는 라벨이 지정된 호(화살표)를 가진 라벨이 지정된 그래프이다.

형식적으로, 라벨이 지정된 다중 방향 그래프 G는 라벨이 지정된 정점과 호를 가진 다중 그래프이며, 8-튜플(tuple) $G=(\backslash Sigma\_V,\; \backslash Sigma\_A,\; V,\; A,\; s,\; t,\; \backslash ell\_V,\; \backslash ell\_A)$로 표현된다. 여기서:

* $V$는 정점의 집합이고, $A$는 호의 집합이다.
* $\backslash Sigma\_V$와 $\backslash Sigma\_A$는 사용 가능한 정점 및 호 라벨의 유한 알파벳이다.
* $s\backslash colon\; A\backslash rightarrow\backslash \; V$와 $t\backslash colon\; A\backslash rightarrow\backslash \; V$는 호의 시작 정점과 대상 정점을 나타내는 두 개의 맵(map)이다.
* $\backslash ell\_V\backslash colon\; V\backslash rightarrow\backslash Sigma\_V$와 $\backslash ell\_A\backslash colon\; A\backslash rightarrow\backslash Sigma\_A$는 정점과 호의 라벨링을 설명하는 두 개의 맵이다.

4.2. 정의 2

라벨이 지정된 다중 방향 그래프는 여러 개의 라벨이 지정된 호, 즉 동일한 끝 정점과 동일한 호 라벨을 가진 호를 가진 라벨이 지정된 그래프이다. (이 라벨이 지정된 그래프의 개념은 그래프 라벨링 문서에서 제공된 개념과 다르다.)