다중 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Multi-pseudograph.svg|섬네일|right|다중 그래프. 회색의 원은 꼭짓점을, 푸른 선은 고리를, 붉은 선은 중복되는 변을, 검은 선은 중복되지 않는 변을 나타낸다.]]
[[그래프 이론]]에서 '''다중 그래프'''(多重graph, {{llang|en|multigraph|멀티그래프}})는 두 꼭짓점 사이에 여러 변이 허용되는, [[그래프 (그래프 이론)|그래프]]의 일반화이다.

== 정의 ==
=== 기초적 정의 ===
'''다중 그래프''' <math>G=(V,E,\partial)</math>는 다음과 같은 [[순서쌍]]이다.
* <math>V</math>는 [[집합]]이다. 이를 '''꼭짓점의 집합'''이라고 하며, 그 원소를 '''꼭짓점'''({{llang|en|vertex}})이라고 한다.
* <math>E</math>는 [[집합]]이다. 이를 '''변의 집합'''이라고 하며, 그 원소를 '''변'''({{llang|en|edge}})이라고 한다.
* <math>\partial\colon E\to S^2(V)</math>는 [[함수]]이다. 여기서 <math>S^2(V)=\{\{u,v\}\colon u,v\in V\}</math>이다. 만약 <math>\partial e=\{u,v\}</math>라면, <math>u</math>와 <math>v</math>를 <math>e</math>의 '''끝점'''({{llang|en|endpoint}})이라고 한다. 양 끝점이 같은 변을 '''고리'''({{llang|en|loop|루프}})라고 한다. 다중 그래프 <math>G</math>의 꼭짓점의 집합은 <math>V(G)</math>, 변의 집합은 <math>E(G)</math>로 쓴다.

다중 그래프 <math>G</math>와 <math>H</math> 사이의 '''사상''' <math>(f,g)</math>은 다음 조건을 만족시키는 함수
:<math>f\colon V(G)\to V(H)</math>
:<math>g\colon E(G)\to E(G)</math>
의 [[순서쌍]]이다.
* 임의의 변 <math>e\in E(G)</math>에 대하여, <math>\partial e=\{u,v\}</math>라면 <math>\partial g(e)=\{f(u),f(v)\}</math>이다. 즉, 다음 그림이 가환한다.
*:<math>\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}
</math>

꼭짓점 <math>v\in V(G)</math>의 '''차수'''({{llang|en|degree}}) <math>\deg v</math>는 다음과 같다.
:<math>\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|</math>
즉, 고리들은 차수에서 두 배로 센다.

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

=== 범주론적 정의 ===
==== 쉼표 범주를 통한 정의 ====
다중 그래프의 범주 <math>\operatorname{Multigraph}</math>는 다음과 같은 [[쉼표 범주]]이다.
:<math>\operatorname{Multigraph}=\operatorname{Set}\downarrow S^2</math>
여기서 [[자기 함자]] <math>S^2\colon\operatorname{Set}\to\operatorname{Set}</math>는
:<math>S^2(V)=\{\{u,v\}\colon u,v\in V\}</math>
:<math>S^2(f\colon V\to V')\colon\{u,v\}\mapsto\{f(u),f(v)\}</math>
이다.

그 밖에도 다양한 개념을 이렇게 정의할 수 있다.
{| class="wikitable"
! <math>F\colon\operatorname{Set}\to\operatorname{Set}</math> !! <math>\operatorname{Set}\downarrow F</math>
|-
| <math>F(V)=\{(u,v)\colon u,v\in V\}</math> || 다중 그래프의 범주
|-
| <math>F(V)=V\times V</math> || [[화살집 (수학)|화살집]]의 범주
|-
| [[멱집합]] 함자 <math>F(V)=\mathcal P(V)</math> || [[다중 초그래프]]의 범주
|-
| <math>F(V)=\mathcal P(V)\times\mathcal P(V)</math> || [[유향 다중 초그래프]]의 범주
|}

==== 준층을 통한 정의 ====
다중 그래프의 범주 <math>\operatorname{Multigraph}</math>는 다음과 같은 [[준층]] 범주이다.
:<math>\operatorname{Multigraph}=\operatorname{Psh}(\mathcal C,\operatorname{Set})</math>
여기서 <math>\mathcal C</math>는 [[작은 범주]]
:<math>\begin{matrix}
V & \xrightarrow s & E \\
{\scriptstyle t}\downarrow & \swarrow{\scriptstyle u} \\
E
\end{matrix}
</math>
이다.

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

'''[[화살집 (수학)|화살집]]'''은 변이 방향을 갖춘 다중 그래프이다. 즉, [[유향 그래프]]와 다중 그래프의 공통적인 일반화이다.

== 같이 보기 ==
* [[그래프 이론]]

== 참고 문헌 ==
* {{서적 인용|제목=Graph theory|총서=Graduate Texts in Mathematics|권=173|성=Diestel|이름=Reinhard|판=4판|날짜=2010|isbn= 978-3-642-14278-9|url=http://diestel-graph-theory.com/|zbl=1204.05001|언어=en}}

== 외부 링크 ==
* {{eom|title=Multigraph}}
* {{매스월드|id=Multigraph|title=Multigraph}}

{{전거 통제}}

[[분류:그래프 이론]]