다중 그래프

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

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

정의

기초적 정의

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

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

다중 그래프 ${\displaystyle G}$와 ${\displaystyle H}$ 사이의 사상 ${\displaystyle (f,g)}$은 다음 조건을 만족시키는 함수

${\displaystyle f\colon V(G)\to V(H)}$

${\displaystyle g\colon E(G)\to E(G)}$

의 순서쌍이다.

• 임의의 변 ${\displaystyle e\in E(G)}$에 대하여, ${\displaystyle \partial e=\{u,v\}}$라면 ${\displaystyle \partial g(e)=\{f(u),f(v)\}}$이다. 즉, 다음 그림이 가환한다.

  ${\displaystyle {\begin{matrix}E(G)&\xrightarrow {S^{2}(g)} &E(H)\\{\scriptstyle \partial }\downarrow &&\downarrow {\scriptstyle \partial }\\S^{2}(V(G))&{\xrightarrow[{S^{2}(f)}]{}}&S^{2}(V(H))\end{matrix}}}$

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

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

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

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

범주론적 정의

쉼표 범주를 통한 정의

다중 그래프의 범주 ${\displaystyle \operatorname {Multigraph} }$는 다음과 같은 쉼표 범주이다.

${\displaystyle \operatorname {Multigraph} =\operatorname {Set} \downarrow S^{2}}$

여기서 자기 함자 ${\displaystyle S^{2}\colon \operatorname {Set} \to \operatorname {Set} }$는

${\displaystyle S^{2}(V)=\{\{u,v\}\colon u,v\in V\}}$

${\displaystyle S^{2}(f\colon V\to V')\colon \{u,v\}\mapsto \{f(u),f(v)\}}$

이다.

그 밖에도 다양한 개념을 이렇게 정의할 수 있다.

${\displaystyle F\colon \operatorname {Set} \to \operatorname {Set} }$	${\displaystyle \operatorname {Set} \downarrow F}$
${\displaystyle F(V)=\{(u,v)\colon u,v\in V\}}$	다중 그래프의 범주
${\displaystyle F(V)=V\times V}$	화살집의 범주
멱집합 함자 ${\displaystyle F(V)={\mathcal {P}}(V)}$	다중 초그래프의 범주
${\displaystyle F(V)={\mathcal {P}}(V)\times {\mathcal {P}}(V)}$	유향 다중 초그래프의 범주

준층을 통한 정의

다중 그래프의 범주 ${\displaystyle \operatorname {Multigraph} }$는 다음과 같은 준층 범주이다.

${\displaystyle \operatorname {Multigraph} =\operatorname {Psh} ({\mathcal {C}},\operatorname {Set} )}$

여기서 ${\displaystyle {\mathcal {C}}}$는 작은 범주

${\displaystyle {\begin{matrix}V&\xrightarrow {s} &E\\{\scriptstyle t}\downarrow &\swarrow {\scriptstyle u}\\E\end{matrix}}}$

이다.

관련 개념

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

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

같이 보기

• 그래프 이론

참고 문헌

• 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.