띠그래프

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

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

정의

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

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

$\overline{\mathrm{E}}(\mathrm{\Gamma })=\underset{v\in V}{⨆}{\overline{\mathrm{E}}}_v(\mathrm{\Gamma })$

${\overline{\mathrm{E}}}_v(\mathrm{\Gamma })=\{(v,u):(v,u)\in \overline{\mathrm{E}}(\mathrm{\Gamma }),u\in \mathrm{V}(\mathrm{\Gamma })\}$

띠그래프 $(\mathrm{\Gamma },\sigma )$는 다음과 같은 데이터로 구성된다.틀:Rp

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

  순열 $\sigma$에 따라, $\overline{\mathrm{E}}(\mathrm{\Gamma })$는 $\sigma$의 순환들로 분할되는데, 이 분할은 $\underset{v\in V}{⨆}{\overline{\mathrm{E}}}_v(\mathrm{\Gamma })$과 일치한다.

띠그래프에 대응되는 곡면

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

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

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

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

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

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

계량 띠그래프(틀:Llang) $(\mathrm{\Gamma },\sigma ,\ell )$는 다음과 같은 데이터로 구성된다.

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

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

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

• $r=\underset{(u,v)\in \mathrm{E}(\mathrm{\Gamma })}{\min }\ell (u,v)$. (사실 이는 이 값 이하의 임의의 양의 실수로 놓아도 된다.)
• 각 꼭짓점 $v\in \mathrm{V}(\mathrm{\Gamma })$에 대하여, 원 $U_v=\{z\in ℂ:|z|<r\}$.
• 각 유향변 $(u,v)\in \overline{\mathrm{E}}(\mathrm{\Gamma })$에 대하여, 복소평면의 부분 집합 $U_{(u,v)}=\{z\in ℂ:0<\mathrm{Re}(z)<\ell (u,v)\}$
• 각 경계 성분 $b=(v_1,v_2,\dots ,v_k)$에 대하여, 단위 원 $U_b=\{z\in ℂ:|z|<1\}$
• 각 유향변 $(u,v)\in \overline{\mathrm{E}}(\mathrm{\Gamma })$에 대하여, 함수

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

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

• 각 꼭짓점 $v$ 및 $k\in \{1,\dots ,\mathrm{deg}v\}$번째 유향변 $(v,u_i)\in {\overline{\mathrm{E}}}_v(\mathrm{\Gamma })$에 대하여, 함수

  $g_{(v,u_k)}:\{z\in U_{(v,u_k):|z|<r}\to U_v$

  $g_{(v,u_k)}:z\mapsto (\exp \frac{2\pi \mathrm{i}k}{\mathrm{deg}v})z^{2/\mathrm{deg}v}$

• 길이 $n$의 경계 성분 $b=(v_0,v_1,v_2,\dots ,v_{n-1},v_n=v_0)$ 및 $k\in \{0,\dots ,n-1\}$에 대하여, 함수

  $h_{b,k}:\{z\in U_{(v_k,v_{k+1})}:\mathrm{Im}z>0\}\to U_b$

  $h_{b,k}:z\mapsto \exp \left(2\pi \mathrm{i}\frac{(\ell (v_0,v_1)+\ell (v_1,v_2)+\cdots +\ell (v_{k-1},v_k)+z))}{\ell (v_0,v_1)+\ell (v_1,v_2)+\cdots +\ell (v_{n-1},v_n)}\right)$

그렇다면,

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

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

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

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

성질

조합론적 성질

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

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

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

위상수학적 성질

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

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

$i:\overline{\mathrm{E}}(\mathrm{\Gamma })\to \overline{\mathrm{E}}(\mathrm{\Gamma })$

$i:(u,v)\mapsto (v,u)$

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

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

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

$g=\frac{1}{2}(2-|\mathrm{V}(\mathrm{\Gamma })|+|\mathrm{E}(\mathrm{\Gamma })|-n)$

예

나무

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

순환 그래프

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

$\sigma :(v_i,v_{i+1})\mapsto (v_i,v_{i-1})$

$\sigma :(v_i,v_{i-1})\mapsto (v_i,v_{i+1})$

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

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

이며, 순열

$\sigma \circ i:(v_i,v_{i+1})\mapsto (v_{i+1},v_{i+2})$

$\sigma \circ i:(v_i,v_{i-1})\mapsto (v_{i-1},v_{i-2})$

및

$i\circ \sigma :(v_i,v_{i+1})\mapsto (v_{i-1},v_i)$

$i\circ \sigma :(v_i,v_{i-1})\mapsto (v_{i+1},v_i)$

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

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

임을 알 수 있다.

외부 링크

• 틀:Nlab
• 틀:웹 인용