띠그래프

그래프 이론과 위상수학에서, 띠그래프(영어: ribbon graph 리본 그래프^[*]) 또는 뚱뚱한 그래프(영어: fat graph)는 주어진 꼭짓점에 인접한 변들에 대한 순환 순열이 주어진 그래프이다. 주어진 띠그래프로부터, 이에 대응하는 곡면을 구성할 수 있다.

띠그래프의 예. 각 꼭짓점에 인접한 변들의 집합 위에는 순환 순열이 주어지며, 이 순환은 원형 점선 화살표로 표시되었다.

정의

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

반변의 집합 ${\displaystyle \operatorname {\bar {E}} (\Gamma )}$ 위에는 다음과 같은 자연스러운 집합의 분할이 존재한다.

${\displaystyle \operatorname {\bar {E}} (\Gamma )=\bigsqcup _{v\in V}\operatorname {\bar {E}} _{v}(\Gamma )}$

${\displaystyle \operatorname {\bar {E}} _{v}(\Gamma )=\{(v,u)\colon (v,u)\in \operatorname {\bar {E}} (\Gamma ),\;u\in \operatorname {V} (\Gamma )\}}$

띠그래프 ${\displaystyle (\Gamma ,\sigma )}$는 다음과 같은 데이터로 구성된다.^{[1]:Definition 1.5}

• ${\displaystyle \Gamma }$는 그래프이며, 모든 꼭짓점의 차수는 유한하다. 즉, 임의의 ${\displaystyle v\in \operatorname {V} (\Gamma )}$에 대하여 ${\displaystyle \operatorname {\bar {E}} _{v}(\Gamma )}$는 유한하다.
• ${\displaystyle \sigma \colon \operatorname {\bar {E}} (\Gamma )\to \operatorname {\bar {E}} (\Gamma )}$는 전단사 함수(즉, 순열)이며, 다음 조건을 만족시킨다.

  순열 ${\displaystyle \sigma }$에 따라, ${\displaystyle \operatorname {\bar {E}} (\Gamma )}$는 ${\displaystyle \sigma }$의 순환들로 분할되는데, 이 분할은 ${\displaystyle \textstyle \bigsqcup _{v\in V}\operatorname {\bar {E}} _{v}(\Gamma )}$과 일치한다.

띠그래프에 대응되는 곡면

띠그래프 ${\displaystyle (\Gamma ,\sigma )}$가 주어졌을 때, 다음을 정의하자.

• 각 꼭짓점 ${\displaystyle v\in \operatorname {V} (\Gamma )}$에 대하여, ${\displaystyle \deg v=k}$일 때, ${\displaystyle k}$-정다각형 ${\displaystyle e_{v}}$. 정다각형의 변들은 각각 ${\displaystyle v}$와 인접한 반변 ${\displaystyle (v,u_{1}),\dotsc ,(v,u_{k})}$들과 대응시킬 수 있으며, 이들은 (시계 반대 방향으로) ${\displaystyle \sigma }$에 의하여 정의된 순환 순열에 따라 배치된다.

그렇다면, 이 정다각형의 족 ${\displaystyle (e_{v})_{v\in \operatorname {V} (\Gamma )}}$가 주어졌을 때, 이들을 다음과 같이 짜깁기할 수 있다.

• 각 변 ${\displaystyle (u,v)\in \operatorname {E} (\Gamma )}$에 대하여, ${\displaystyle e_{u}}$에서 ${\displaystyle v}$에 대응하는 변과 ${\displaystyle e_{v}}$에서 ${\displaystyle u}$에 대응하는 변을 (방향을 보존하며) 짜깁기한다.

그렇다면, 어떤 유향 곡면(2차원 다양체) ${\displaystyle \Sigma _{\Gamma ,\sigma }}$를 얻는다. 이를 띠그래프 ${\displaystyle (\Gamma ,\sigma )}$의 기하학적 실현(영어: geometric realization)이라고 한다.

띠그래프에 대응되는 리만 곡면

계량 띠그래프(영어: metric ribbon graph) ${\displaystyle (\Gamma ,\sigma ,\ell )}$는 다음과 같은 데이터로 구성된다.

• ${\displaystyle (\Gamma ,\sigma )}$는 유한 개의 꼭짓점과 변을 갖는 연결 띠그래프이다.
• ${\displaystyle \ell \colon \operatorname {E} (\Gamma )\to \mathbb {R} ^{+}}$는 각 변에 양의 실수를 대응시키는 함수이다. 이를 변의 길이(영어: length)라고 한다.

그렇다면, 각 계량 띠그래프에 표준적으로 어떤 연결 콤팩트 리만 곡면 ${\displaystyle \Sigma }$ 및 그 속의 유한 집합 ${\displaystyle \{z_{1},\dotsc ,z_{n}\}}$ 및 이에 대한 슈트레벨 미분을 대응시킬 수 있다.^[1]:§5 또한, ${\displaystyle \Sigma \setminus \{z_{1},\dotsc ,z_{n}\}}$은 ${\displaystyle (\Gamma ,\sigma )}$의 기하학적 실현과 위상 동형이다.

구체적으로, 계량 띠그래프 ${\displaystyle (\Gamma ,\sigma ,\ell )}$에 대하여 다음을 정의하자.

• ${\displaystyle \textstyle r=\min _{(u,v)\in \operatorname {E} (\Gamma )}\ell (u,v)}$. (사실 이는 이 값 이하의 임의의 양의 실수로 놓아도 된다.)
• 각 꼭짓점 ${\displaystyle v\in \operatorname {V} (\Gamma )}$에 대하여, 원 ${\displaystyle U_{v}=\{z\in \mathbb {C} \colon |z|<r\}}$.
• 각 유향변 ${\displaystyle (u,v)\in \operatorname {\bar {E}} (\Gamma )}$에 대하여, 복소평면의 부분 집합 ${\displaystyle U_{(u,v)}=\{z\in \mathbb {C} \colon 0<\operatorname {Re} (z)<\ell (u,v)\}}$
• 각 경계 성분 ${\displaystyle b=(v_{1},v_{2},\dotsc ,v_{k})}$에 대하여, 단위 원 ${\displaystyle U_{b}=\{z\in \mathbb {C} \colon |z|<1\}}$
• 각 유향변 ${\displaystyle (u,v)\in \operatorname {\bar {E}} (\Gamma )}$에 대하여, 함수

  ${\displaystyle f_{(u,v)}\colon U_{(u,v)}\to U_{(v,u)}}$

  ${\displaystyle f_{(u,v)}\colon z\mapsto \ell (u,v)-z}$

• 각 꼭짓점 ${\displaystyle v}$ 및 ${\displaystyle k\in \{1,\dotsc ,\deg v\}}$번째 유향변 ${\displaystyle (v,u_{i})\in \operatorname {\bar {E}} _{v}(\Gamma )}$에 대하여, 함수

  ${\displaystyle g_{(v,u_{k})}\colon \{z\in U_{(v,u_{k})\colon |z|<r}\to U_{v}}$

  ${\displaystyle g_{(v,u_{k})}\colon z\mapsto \left(\exp {\frac {2\pi \mathrm {i} k}{\deg v}}\right)z^{2/\deg v}}$

• 길이 ${\displaystyle n}$의 경계 성분 ${\displaystyle b=(v_{0},v_{1},v_{2},\dotsc ,v_{n-1},v_{n}=v_{0})}$ 및 ${\displaystyle k\in \{0,\dotsc ,n-1\}}$에 대하여, 함수

  ${\displaystyle h_{b,k}\colon \{z\in U_{(v_{k},v_{k+1})}\colon \operatorname {Im} z>0\}\to U_{b}}$

  ${\displaystyle 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)}$

그렇다면,

• 모든 ${\displaystyle U_{v}}$들과 ${\displaystyle U_{(u,v)}}$들과 ${\displaystyle U_{b}}$들을 정칙 함수 ${\displaystyle f,g,h}$들로 짜깁기하여 리만 곡면 ${\displaystyle \Sigma }$를 만들 수 있다. ${\displaystyle U_{(u,v)}}$의 경계들은 모두 ${\displaystyle U_{v}}$ 및 ${\displaystyle U_{b}}$에 의하여 덮이므로, 이는 콤팩트 리만 곡면이다.
• 또한, ${\displaystyle U_{b}}$들의 원점들은 특별한 유한 집합 ${\displaystyle \{z_{1},\dotsc ,z_{n}\}\subsetneq \Sigma }$을 구성한다.
• ${\displaystyle U_{(u,v)}}$ 위의 상수 정칙 이차 미분들은 짜깁기를 통해 ${\displaystyle \Sigma \setminus \{z_{1},\dotsc ,z_{n}\}}$ 위의 정칙 이차 미분을 구성한다. 이는 각 ${\displaystyle z_{i}}$ 근처에서 2차 극을 가져, ${\displaystyle \Sigma \setminus \{z_{1},\dotsc ,z_{n}\}}$의 슈트레벨 미분을 이룬다. 이 경우, 경계 성분 ${\displaystyle b}$에 대응되는 양의 실수는 ${\displaystyle b}$를 구성하는 유향변들의 길이들의 합이다.

띠그래프에 대응되는 벨리 사상

${\displaystyle (\Gamma ,\sigma ,\ell )}$가 계량 띠그래프이며, 그 어떤 꼭짓점도 차수가 0, 1 또는 2가 아니라고 하자. 그렇다면, 다음 두 조건이 서로 동치이다.^{[1]:Theorem 6.5}

• ${\displaystyle (\Gamma ,\sigma ,\ell )}$로 정의되는 리만 곡면 ${\displaystyle \Sigma }$는 대수적 수의 체 ${\displaystyle {\bar {\mathbb {Q} }}}$ 위의 대수 곡선을 이룬다. 즉, 벨리 사상 ${\displaystyle \Sigma \to \mathbb {CP} ^{1}}$ 및 이에 대응되는 데생당팡이 존재한다.
• 모든 변의 길이가 같다.

성질

조합론적 성질

그래프 ${\displaystyle \Gamma }$ 위의 띠그래프 구조들의 수는 다음과 같다.

${\displaystyle \prod _{v\in \operatorname {V} (\Gamma )}(\deg _{\Gamma }v-1)!}$

여기서 ${\displaystyle \deg _{\Gamma }(-)}$는 꼭짓점의 차수(즉, 꼭짓점과 인접한 변의 수)이다. 특히, 모든 꼭짓점의 차수가 2 이하라면, 띠그래프 구조는 유일하다.

위상수학적 성질

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

띠그래프 ${\displaystyle (\Gamma ,\sigma )}$가 주어졌을 때, 전단사 함수

${\displaystyle i\colon \operatorname {\bar {E}} (\Gamma )\to \operatorname {\bar {E}} (\Gamma )}$

${\displaystyle i\colon (u,v)\mapsto (v,u)}$

를 생각하자. 그렇다면, ${\displaystyle f\circ i}$와 ${\displaystyle i\circ f}$의 순환들을 생각할 수 있다. 그렇다면, 다음 세 집합 사이에는 표준적인 일대일 대응이 존재한다.

• 순열 ${\displaystyle \sigma \circ i}$의 순환들의 집합
• 순열 ${\displaystyle i\circ \sigma }$의 순환들의 집합
• ${\displaystyle \Sigma _{\Gamma ,\sigma }}$의 구멍들의 집합

또한, ${\displaystyle \Gamma }$가 연결 유한 그래프이고, ${\displaystyle \Sigma _{\Gamma ,\sigma }}$의 구멍들의 수를 ${\displaystyle n}$이라고 하고, 그 종수를 ${\displaystyle g}$라고 할 때, 다음이 성립한다.

${\displaystyle g={\frac {1}{2}}\left(2-|\operatorname {V} (\Gamma )|+|\operatorname {E} (\Gamma )|-n\right)}$

예

나무

나무에 대응되는 곡면은 (띠그래프 구조에 상관 없이) 항상 ${\displaystyle \Sigma _{0,1}}$, 즉 하나의 구멍이 뚫린 구이다.

순환 그래프

꼭짓점 ${\displaystyle k}$개의 순환 그래프는 유일한 띠그래프 구조를 갖는다. 구체적으로, 꼭짓점들을 ${\displaystyle (v_{i})_{i\in \mathbb {Z} /(k)}}$라고 하면,

${\displaystyle \sigma \colon (v_{i},v_{i+1})\mapsto (v_{i},v_{i-1})}$

${\displaystyle \sigma \colon (v_{i},v_{i-1})\mapsto (v_{i},v_{i+1})}$

이다. 이에 대응하는 곡면은 ${\displaystyle \Sigma _{0,2}}$, 즉 두 개의 구멍이 뚫린 구이다. 순환 그래프 ${\displaystyle \Gamma }$의 경우

${\displaystyle |\operatorname {V} (\Gamma )|=|\operatorname {E} (\Gamma )|=k}$

이며, 순열

${\displaystyle \sigma \circ i\colon (v_{i},v_{i+1})\mapsto (v_{i+1},v_{i+2})}$

${\displaystyle \sigma \circ i\colon (v_{i},v_{i-1})\mapsto (v_{i-1},v_{i-2})}$

및

${\displaystyle i\circ \sigma \colon (v_{i},v_{i+1})\mapsto (v_{i-1},v_{i})}$

${\displaystyle i\circ \sigma \colon (v_{i},v_{i-1})\mapsto (v_{i+1},v_{i})}$

둘 다 각각 두 개의 순환을 갖는다. 이에 따라 종수가

${\displaystyle g={\frac {1}{2}}(2-k+k-2)=0}$

임을 알 수 있다.