다중 그래프

그래프 이론에서 다중 그래프(多重graph, 영어: multigraph 멀티그래프^[*])는 두 꼭짓점 사이에 여러 변이 허용되는, 그래프의 일반화이다.

다중 그래프. 회색의 원은 꼭짓점을, 푸른 선은 고리를, 붉은 선은 중복되는 변을, 검은 선은 중복되지 않는 변을 나타낸다.

정의

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

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

꼭짓점 $v\in V(G)$의 차수(영어: degree) $\deg v$는 다음과 같다.

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

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

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

관련 개념

(단순) 그래프는 고리가 없고, 두 꼭짓점 사이에 최대 하나의 변이 존재하는 다중 그래프이다. 반대로, 주어진 다중 그래프에서 변의 중복수를 잊고, 고리를 삭제한다면 그래프를 얻는다.

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

참고 문헌

• Diestel, Reinhard (2010). 《Graph theory》. Graduate Texts in Mathematics (영어) 173 4판. ISBN 978-3-642-14278-9. Zbl 1204.05001.  CS1 관리 - 추가 문구 (링크)

외부 링크

• “Multigraph”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Multigraph”. 《Wolfram MathWorld》 (영어). Wolfram Research.