띠그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Ribbon_Graph.png|thumb|right|띠그래프의 예. 각 꼭짓점에 인접한 변들의 집합 위에는 순환 순열이 주어지며, 이 순환은 원형 점선 화살표로 표시되었다.]]
[[그래프 이론]]과 [[위상수학]]에서, '''띠그래프'''({{llang|en|ribbon graph|리본 그래프}}) 또는 '''뚱뚱한 그래프'''({{llang|en|fat graph}})는 주어진 꼭짓점에 인접한 변들에 대한 순환 [[순열]]이 주어진 [[그래프]]이다. 주어진 띠그래프로부터, 이에 대응하는 [[곡면]]을 구성할 수 있다.

== 정의 ==
[[그래프]] <math>\Gamma</math>의 '''반변'''(半邊, {{llang|en|half-edge}}) 또는 '''유향변'''(有向邊, {{llang|en|oriented edge}})는 [[꼭짓점]] <math>v\in\operatorname V(\Gamma)</math>와, 이에 인접한 변 <math>e=\{v,u\}\in\operatorname E(\Gamma)</math>의 [[순서쌍]]이다. (이는 변 <math>(v,u)</math>의 <math>v</math>쪽 “절반”, 즉 “<math>(v,[u+v]/2)</math>”로 생각할 수 있다. 이에 따라, 반변의 집합 <math>\operatorname{\bar E}(\Gamma)\subseteq \operatorname V(\Gamma)\times\operatorname V(\Gamma)</math>은 <math>\operatorname V(\Gamma)\times\operatorname V(\Gamma)</math>의 부분 집합이다.

반변의 집합 <math>\operatorname{\bar E}(\Gamma)</math> 위에는 다음과 같은 자연스러운 [[집합의 분할]]이 존재한다.
:<math>\operatorname{\bar E}(\Gamma)=\bigsqcup_{v\in V}\operatorname{\bar E}_v(\Gamma)</math>
:<math>\operatorname{\bar E}_v(\Gamma)=\{(v,u)\colon (v,u)\in\operatorname{\bar E}(\Gamma),\;u\in\operatorname V(\Gamma)\}</math>

'''띠그래프''' <math>(\Gamma,\sigma)</math>는 다음과 같은 데이터로 구성된다.<ref name="MP">{{저널 인용|arxiv=math-ph/9811024|제목=Ribbon graphs, quadratic differentials on Riemann surfaces, and algebraic curves defined over ℚ̄|이름=Motohico|성=Mulase|이름2=Michael|성2=Penkava|저널=The Asian Journal of Mathematics|권=2|호=4|쪽=875–920|날짜=1998|bibcode=1998math.ph..11024M|언어=en}}</ref>{{rp|Definition 1.5}}
* <math>\Gamma</math>는 [[그래프]]이며, 모든 꼭짓점의 차수는 유한하다. 즉, 임의의 <math>v\in\operatorname V(\Gamma)</math>에 대하여 <math>\operatorname{\bar E}_v(\Gamma)</math>는 유한하다.
* <math>\sigma\colon\operatorname{\bar E}(\Gamma)\to\operatorname{\bar E}(\Gamma)</math>는 [[전단사 함수]](즉, [[순열]])이며, 다음 조건을 만족시킨다.
*:[[순열]] <math>\sigma</math>에 따라, <math>\operatorname{\bar E}(\Gamma)</math>는 <math>\sigma</math>의 순환들로 [[집합의 분할|분할]]되는데, 이 분할은 <math>\textstyle\bigsqcup_{v\in V}\operatorname{\bar E}_v(\Gamma)</math>과 일치한다.

=== 띠그래프에 대응되는 곡면 ===
띠그래프 <math>(\Gamma,\sigma)</math>가 주어졌을 때, 다음을 정의하자.
* 각 꼭짓점 <math>v\in\operatorname V(\Gamma)</math>에 대하여, <math>\deg v=k</math>일 때, <math>k</math>-[[정다각형]] <math>e_v</math>. 정다각형의 변들은 각각 <math>v</math>와 인접한 반변 <math>(v,u_1),\dotsc,(v,u_k)</math>들과 대응시킬 수 있으며, 이들은 (시계 반대 방향으로) <math>\sigma</math>에 의하여 정의된 순환 순열에 따라 배치된다.

그렇다면, 이 정다각형의 족 <math>(e_v)_{v\in\operatorname V(\Gamma)}</math>가 주어졌을 때, 이들을 다음과 같이 짜깁기할 수 있다.
* 각 변 <math>(u,v)\in\operatorname E(\Gamma)</math>에 대하여, <math>e_u</math>에서 <math>v</math>에 대응하는 변과 <math>e_v</math>에서 <math>u</math>에 대응하는 변을 ([[방향 (다양체)|방향]]을 보존하며) 짜깁기한다.
그렇다면, 어떤 [[유향 다양체|유향]] 곡면(2차원 [[다양체]]) <math>\Sigma_{\Gamma,\sigma}</math>를 얻는다. 이를 띠그래프 <math>(\Gamma,\sigma)</math>의 '''기하학적 실현'''({{llang|en|geometric realization}})이라고 한다.

=== 띠그래프에 대응되는 리만 곡면 ===
'''계량 띠그래프'''({{llang|en|metric ribbon graph}}) <math>(\Gamma,\sigma,\ell)</math>는 다음과 같은 데이터로 구성된다.
* <math>(\Gamma,\sigma)</math>는 유한 개의 꼭짓점과 변을 갖는 연결 띠그래프이다.
* <math>\ell\colon\operatorname E(\Gamma)\to\mathbb R^+</math>는 각 변에 양의 실수를 대응시키는 [[함수]]이다. 이를 변의 '''길이'''({{llang|en|length}})라고 한다.
그렇다면, 각 계량 띠그래프에 표준적으로 어떤 [[연결 공간|연결]] [[콤팩트 공간|콤팩트]] [[리만 곡면]] <math>\Sigma</math> 및 그 속의 유한 집합 <math>\{z_1,\dotsc,z_n\}</math> 및 이에 대한 [[슈트레벨 미분]]을 대응시킬 수 있다.<ref name="MP"/>{{rp|§5}} 또한, <math>\Sigma\setminus\{z_1,\dotsc,z_n\}</math>은 <math>(\Gamma,\sigma)</math>의 기하학적 실현과 [[위상 동형]]이다.

구체적으로, 계량 띠그래프 <math>(\Gamma,\sigma,\ell)</math>에 대하여 다음을 정의하자.
* <math>\textstyle r=\min_{(u,v)\in\operatorname E(\Gamma)}\ell(u,v)</math>. (사실 이는 이 값 이하의 임의의 양의 실수로 놓아도 된다.)
* 각 꼭짓점 <math>v\in\operatorname V(\Gamma)</math>에 대하여, 원 <math>U_v=
\{z\in\mathbb C\colon |z|<r\}</math>.
* 각 유향변 <math>(u,v)\in\operatorname{\bar E}(\Gamma)</math>에 대하여, [[복소평면]]의 [[부분 집합]] <math>U_{(u,v)}=\{z\in\mathbb C\colon0<\operatorname{Re}(z)<\ell(u,v)\}</math>
* 각 경계 성분 <math>b=(v_1,v_2,\dotsc,v_k)</math>에 대하여, 단위 원 <math>U_b=\{z\in\mathbb C\colon |z|<1\}</math>
* 각 유향변 <math>(u,v)\in\operatorname{\bar E}(\Gamma)</math>에 대하여, 함수
*:<math>f_{(u,v)}\colon U_{(u,v)}\to U_{(v,u)}</math>
*:<math>f_{(u,v)}\colon z\mapsto \ell(u,v)-z</math>
* 각 꼭짓점 <math>v</math> 및 <math>k\in\{1,\dotsc,\deg v\}</math>번째 유향변 <math>(v,u_i)\in\operatorname{\bar E}_v(\Gamma)</math>에 대하여, 함수
*:<math>g_{(v,u_k)}\colon \{z\in U_{(v,u_k)\colon |z|<r}\to U_v</math>
*:<math>g_{(v,u_k)}\colon z\mapsto \left(\exp\frac{2\pi\mathrm ik}{\deg v}\right) z^{2/\deg v}</math>
* 길이 <math>n</math>의 경계 성분 <math>b=(v_0,v_1,v_2,\dotsc,v_{n-1},v_n=v_0)</math> 및 <math>k\in\{0,\dotsc,n-1\}</math>에 대하여, 함수
*:<math>h_{b,k}\colon\{z\in U_{(v_k,v_{k+1})}\colon\operatorname{Im}z>0\}\to U_b</math>
*:<math>h_{b,k}\colon z\mapsto \exp\left(2\pi\mathrm i\frac{\left(\ell(v_0,v_1)+\ell(v_1,v_2)+\dotsb+\ell(v_{k-1},v_k)+z)\right)}{\ell(v_0,v_1)+\ell(v_1,v_2)+\dotsb+\ell(v_{n-1},v_n)}\right)</math>
그렇다면,
* 모든 <math>U_v</math>들과 <math>U_{(u,v)}</math>들과 <math>U_b</math>들을 정칙 함수 <math>f,g,h</math>들로 짜깁기하여 [[리만 곡면]] <math>\Sigma</math>를 만들 수 있다. <math>U_{(u,v)}</math>의 경계들은 모두 <math>U_v</math> 및 <math>U_b</math>에 의하여 덮이므로, 이는 [[콤팩트 공간|콤팩트]] [[리만 곡면]]이다.
* 또한, <math>U_b</math>들의 원점들은 특별한 [[유한 집합]] <math>\{z_1,\dotsc,z_n\}\subsetneq\Sigma</math>을 구성한다.
* <math>U_{(u,v)}</math> 위의 상수 [[정칙 이차 미분]]들은 짜깁기를 통해 <math>\Sigma\setminus\{z_1,\dotsc,z_n\}</math> 위의 [[정칙 이차 미분]]을 구성한다. 이는 각 <math>z_i</math> 근처에서 2차 [[극 (복소해석학)|극]]을 가져, <math>\Sigma\setminus\{z_1,\dotsc,z_n\}</math>의 [[슈트레벨 미분]]을 이룬다. 이 경우, 경계 성분 <math>b</math>에 대응되는 양의 실수는 <math>b</math>를 구성하는 유향변들의 길이들의 합이다.

=== 띠그래프에 대응되는 벨리 사상 ===
<math>(\Gamma,\sigma,\ell)</math>가 계량 띠그래프이며, 그 어떤 꼭짓점도 차수가 0, 1 또는 2가 아니라고 하자. 그렇다면, 다음 두 조건이 서로 [[동치]]이다.<ref name="MP"/>{{rp|Theorem 6.5}}
* <math>(\Gamma,\sigma,\ell)</math>로 정의되는 [[리만 곡면]] <math>\Sigma</math>는 [[대수적 수]]의 체 <math>\bar{\mathbb Q}</math> 위의 [[대수 곡선]]을 이룬다. 즉, [[벨리 사상]] <math>\Sigma\to\mathbb{CP}^1</math> 및 이에 대응되는 [[데생당팡]]이 존재한다.
* 모든 변의 길이가 같다.

== 성질 ==
=== 조합론적 성질 ===
그래프 <math>\Gamma</math> 위의 띠그래프 구조들의 수는 다음과 같다.
:<math>\prod_{v\in\operatorname V(\Gamma)}(\deg_\Gamma v-1)!</math>
여기서 <math>\deg_\Gamma(-)</math>는 꼭짓점의 차수(즉, 꼭짓점과 인접한 변의 수)이다. 특히, 모든 꼭짓점의 차수가 2 이하라면, 띠그래프 구조는 유일하다.

=== 위상수학적 성질 ===
띠그래프는 ([[CW 복합체]]로 여겼을 때) 그 기하학적 실현과 항상 [[호모토피 동치]]이지만, 보통 [[위상 동형]]이 아니다.

띠그래프 <math>(\Gamma,\sigma)</math>가 주어졌을 때, [[전단사 함수]]
:<math>i\colon\operatorname{\bar E}(\Gamma)\to\operatorname{\bar E}(\Gamma)</math>
:<math>i\colon (u,v)\mapsto(v,u)</math>
를 생각하자. 그렇다면, <math>f\circ i</math>와 <math>i\circ f</math>의 순환들을 생각할 수 있다. 그렇다면, 다음 세 집합 사이에는 표준적인 [[일대일 대응]]이 존재한다.
* 순열 <math>\sigma\circ i</math>의 순환들의 집합
* 순열 <math>i\circ \sigma</math>의 순환들의 집합
* <math>\Sigma_{\Gamma,\sigma}</math>의 구멍들의 집합

또한, <math>\Gamma</math>가 연결 유한 그래프이고, <math>\Sigma_{\Gamma,\sigma}</math>의 구멍들의 수를 <math>n</math>이라고 하고, 그 종수를 <math>g</math>라고 할 때, 다음이 성립한다.
:<math>g=\frac12\left(2-|\operatorname V(\Gamma)|+|\operatorname E(\Gamma)|-n\right)</math>

== 예 ==
=== 나무 ===
[[나무 (그래프 이론)|나무]]에 대응되는 곡면은 (띠그래프 구조에 상관 없이) 항상 <math>\Sigma_{0,1}</math>, 즉 하나의 구멍이 뚫린 [[구 (기하학)|구]]이다.

=== 순환 그래프 ===
꼭짓점 <math>k</math>개의 [[순환 그래프]]는 유일한 띠그래프 구조를 갖는다. 구체적으로, 꼭짓점들을 <math>(v_i)_{i\in\mathbb Z/(k)}</math>라고 하면,
:<math>\sigma\colon (v_i,v_{i+1})\mapsto (v_i,v_{i-1})</math>
:<math>\sigma\colon (v_i,v_{i-1})\mapsto (v_i,v_{i+1})</math>
이다. 이에 대응하는 곡면은 <math>\Sigma_{0,2}</math>, 즉 두 개의 구멍이 뚫린 [[구 (기하학)|구]]이다. 순환 그래프 <math>\Gamma</math>의 경우
:<math>|\operatorname V(\Gamma)|=|\operatorname E(\Gamma)|=k</math>
이며, 순열
:<math>\sigma\circ i\colon (v_i,v_{i+1})\mapsto (v_{i+1},v_{i+2})</math>
:<math>\sigma\circ i\colon (v_i,v_{i-1})\mapsto (v_{i-1},v_{i-2})</math>
및
:<math>i\circ\sigma\colon (v_i,v_{i+1})\mapsto (v_{i-1},v_i)</math>
:<math>i\circ\sigma\colon (v_i,v_{i-1})\mapsto (v_{i+1},v_i)</math>
둘 다 각각 두 개의 순환을 갖는다. 이에 따라 종수가
:<math>g=\frac12(2-k+k-2)=0</math>
임을 알 수 있다.

== 참고 문헌 ==
{{각주}}

== 외부 링크 ==
* {{nlab|id=ribbon graph|title=Ribbon graph}}
* {{웹 인용|url=https://mathoverflow.net/questions/51978/why-does-ribbon-graph-cohomology-compute-cohomology-of-mcg|제목=Why does (Ribbon) Graph (co)Homology Compute (co)Homology of MCG?|출판사=Math Overflow|언어=en|확인날짜=2017-04-28|보존url=https://web.archive.org/web/20151031062228/http://mathoverflow.net/questions/51978/why-does-ribbon-graph-cohomology-compute-cohomology-of-mcg|보존날짜=2015-10-31|url-status=dead}}

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