그래프 이론 과 위상수학 에서, 띠그래프 (영어 : ribbon graph 리본 그래프[* ] ) 또는 뚱뚱한 그래프 (영어 : fat graph )는 주어진 꼭짓점에 인접한 변들에 대한 순환 순열 이 주어진 그래프 이다. 주어진 띠그래프로부터, 이에 대응하는 곡면 을 구성할 수 있다.
띠그래프의 예. 각 꼭짓점에 인접한 변들의 집합 위에는 순환 순열이 주어지며, 이 순환은 원형 점선 화살표로 표시되었다.
그래프
Γ
{\displaystyle \Gamma }
반변 (半邊, 영어 : half-edge ) 또는 유향변 (有向邊, 영어 : oriented edge )는 꼭짓점
v
∈
V
(
Γ
)
{\displaystyle v\in \operatorname {V} (\Gamma )}
e
=
{
v
,
u
}
∈
E
(
Γ
)
{\displaystyle e=\{v,u\}\in \operatorname {E} (\Gamma )}
순서쌍 이다. (이는 변
(
v
,
u
)
{\displaystyle (v,u)}
v
{\displaystyle v}
(
v
,
[
u
+
v
]
/
2
)
{\displaystyle (v,[u+v]/2)}
E
¯
(
Γ
)
⊆
V
(
Γ
)
×
V
(
Γ
)
{\displaystyle \operatorname {\bar {E}} (\Gamma )\subseteq \operatorname {V} (\Gamma )\times \operatorname {V} (\Gamma )}
V
(
Γ
)
×
V
(
Γ
)
{\displaystyle \operatorname {V} (\Gamma )\times \operatorname {V} (\Gamma )}
반변의 집합
E
¯
(
Γ
)
{\displaystyle \operatorname {\bar {E}} (\Gamma )}
집합의 분할 이 존재한다.
E
¯
(
Γ
)
=
⨆
v
∈
V
E
¯
v
(
Γ
)
{\displaystyle \operatorname {\bar {E}} (\Gamma )=\bigsqcup _{v\in V}\operatorname {\bar {E}} _{v}(\Gamma )}
E
¯
v
(
Γ
)
=
{
(
v
,
u
)
:
(
v
,
u
)
∈
E
¯
(
Γ
)
,
u
∈
V
(
Γ
)
}
{\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 }
그래프 이며, 모든 꼭짓점의 차수는 유한하다. 즉, 임의의
v
∈
V
(
Γ
)
{\displaystyle v\in \operatorname {V} (\Gamma )}
E
¯
v
(
Γ
)
{\displaystyle \operatorname {\bar {E}} _{v}(\Gamma )}
σ
:
E
¯
(
Γ
)
→
E
¯
(
Γ
)
{\displaystyle \sigma \colon \operatorname {\bar {E}} (\Gamma )\to \operatorname {\bar {E}} (\Gamma )}
전단사 함수 (즉, 순열 )이며, 다음 조건을 만족시킨다.
순열
σ
{\displaystyle \sigma }
E
¯
(
Γ
)
{\displaystyle \operatorname {\bar {E}} (\Gamma )}
σ
{\displaystyle \sigma }
분할 되는데, 이 분할은
⨆
v
∈
V
E
¯
v
(
Γ
)
{\displaystyle \textstyle \bigsqcup _{v\in V}\operatorname {\bar {E}} _{v}(\Gamma )}
띠그래프에 대응되는 곡면
편집
띠그래프
(
Γ
,
σ
)
{\displaystyle (\Gamma ,\sigma )}
각 꼭짓점
v
∈
V
(
Γ
)
{\displaystyle v\in \operatorname {V} (\Gamma )}
deg
v
=
k
{\displaystyle \deg v=k}
k
{\displaystyle k}
정다각형
e
v
{\displaystyle e_{v}}
v
{\displaystyle v}
(
v
,
u
1
)
,
…
,
(
v
,
u
k
)
{\displaystyle (v,u_{1}),\dotsc ,(v,u_{k})}
σ
{\displaystyle \sigma }
그렇다면, 이 정다각형의 족
(
e
v
)
v
∈
V
(
Γ
)
{\displaystyle (e_{v})_{v\in \operatorname {V} (\Gamma )}}
각 변
(
u
,
v
)
∈
E
(
Γ
)
{\displaystyle (u,v)\in \operatorname {E} (\Gamma )}
e
u
{\displaystyle e_{u}}
v
{\displaystyle v}
e
v
{\displaystyle e_{v}}
u
{\displaystyle u}
방향 을 보존하며) 짜깁기한다. 그렇다면, 어떤 유향 곡면(2차원 다양체 )
Σ
Γ
,
σ
{\displaystyle \Sigma _{\Gamma ,\sigma }}
(
Γ
,
σ
)
{\displaystyle (\Gamma ,\sigma )}
기하학적 실현 (영어 : geometric realization )이라고 한다.
띠그래프에 대응되는 리만 곡면
편집
계량 띠그래프 (영어 : metric ribbon graph )
(
Γ
,
σ
,
ℓ
)
{\displaystyle (\Gamma ,\sigma ,\ell )}
(
Γ
,
σ
)
{\displaystyle (\Gamma ,\sigma )}
ℓ
:
E
(
Γ
)
→
R
+
{\displaystyle \ell \colon \operatorname {E} (\Gamma )\to \mathbb {R} ^{+}}
함수 이다. 이를 변의 길이 (영어 : length )라고 한다.그렇다면, 각 계량 띠그래프에 표준적으로 어떤 연결 콤팩트 리만 곡면
Σ
{\displaystyle \Sigma }
{
z
1
,
…
,
z
n
}
{\displaystyle \{z_{1},\dotsc ,z_{n}\}}
슈트레벨 미분 을 대응시킬 수 있다.[1] :§5
Σ
∖
{
z
1
,
…
,
z
n
}
{\displaystyle \Sigma \setminus \{z_{1},\dotsc ,z_{n}\}}
(
Γ
,
σ
)
{\displaystyle (\Gamma ,\sigma )}
위상 동형 이다.
구체적으로, 계량 띠그래프
(
Γ
,
σ
,
ℓ
)
{\displaystyle (\Gamma ,\sigma ,\ell )}
r
=
min
(
u
,
v
)
∈
E
(
Γ
)
ℓ
(
u
,
v
)
{\displaystyle \textstyle r=\min _{(u,v)\in \operatorname {E} (\Gamma )}\ell (u,v)}
각 꼭짓점
v
∈
V
(
Γ
)
{\displaystyle v\in \operatorname {V} (\Gamma )}
U
v
=
{
z
∈
C
:
|
z
|
<
r
}
{\displaystyle U_{v}=\{z\in \mathbb {C} \colon |z|<r\}}
각 유향변
(
u
,
v
)
∈
E
¯
(
Γ
)
{\displaystyle (u,v)\in \operatorname {\bar {E}} (\Gamma )}
복소평면 의 부분 집합
U
(
u
,
v
)
=
{
z
∈
C
:
0
<
Re
(
z
)
<
ℓ
(
u
,
v
)
}
{\displaystyle U_{(u,v)}=\{z\in \mathbb {C} \colon 0<\operatorname {Re} (z)<\ell (u,v)\}}
각 경계 성분
b
=
(
v
1
,
v
2
,
…
,
v
k
)
{\displaystyle b=(v_{1},v_{2},\dotsc ,v_{k})}
U
b
=
{
z
∈
C
:
|
z
|
<
1
}
{\displaystyle U_{b}=\{z\in \mathbb {C} \colon |z|<1\}}
각 유향변
(
u
,
v
)
∈
E
¯
(
Γ
)
{\displaystyle (u,v)\in \operatorname {\bar {E}} (\Gamma )}
f
(
u
,
v
)
:
U
(
u
,
v
)
→
U
(
v
,
u
)
{\displaystyle f_{(u,v)}\colon U_{(u,v)}\to U_{(v,u)}}
f
(
u
,
v
)
:
z
↦
ℓ
(
u
,
v
)
−
z
{\displaystyle f_{(u,v)}\colon z\mapsto \ell (u,v)-z}
각 꼭짓점
v
{\displaystyle v}
k
∈
{
1
,
…
,
deg
v
}
{\displaystyle k\in \{1,\dotsc ,\deg v\}}
(
v
,
u
i
)
∈
E
¯
v
(
Γ
)
{\displaystyle (v,u_{i})\in \operatorname {\bar {E}} _{v}(\Gamma )}
g
(
v
,
u
k
)
:
{
z
∈
U
(
v
,
u
k
)
:
|
z
|
<
r
→
U
v
{\displaystyle g_{(v,u_{k})}\colon \{z\in U_{(v,u_{k})\colon |z|<r}\to U_{v}}
g
(
v
,
u
k
)
:
z
↦
(
exp
2
π
i
k
deg
v
)
z
2
/
deg
v
{\displaystyle g_{(v,u_{k})}\colon z\mapsto \left(\exp {\frac {2\pi \mathrm {i} k}{\deg v}}\right)z^{2/\deg v}}
길이
n
{\displaystyle n}
b
=
(
v
0
,
v
1
,
v
2
,
…
,
v
n
−
1
,
v
n
=
v
0
)
{\displaystyle b=(v_{0},v_{1},v_{2},\dotsc ,v_{n-1},v_{n}=v_{0})}
k
∈
{
0
,
…
,
n
−
1
}
{\displaystyle k\in \{0,\dotsc ,n-1\}}
h
b
,
k
:
{
z
∈
U
(
v
k
,
v
k
+
1
)
:
Im
z
>
0
}
→
U
b
{\displaystyle h_{b,k}\colon \{z\in U_{(v_{k},v_{k+1})}\colon \operatorname {Im} z>0\}\to U_{b}}
h
b
,
k
:
z
↦
exp
(
2
π
i
(
ℓ
(
v
0
,
v
1
)
+
ℓ
(
v
1
,
v
2
)
+
⋯
+
ℓ
(
v
k
−
1
,
v
k
)
+
z
)
)
ℓ
(
v
0
,
v
1
)
+
ℓ
(
v
1
,
v
2
)
+
⋯
+
ℓ
(
v
n
−
1
,
v
n
)
)
{\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)}
그렇다면,
모든
U
v
{\displaystyle U_{v}}
U
(
u
,
v
)
{\displaystyle U_{(u,v)}}
U
b
{\displaystyle U_{b}}
f
,
g
,
h
{\displaystyle f,g,h}
리만 곡면
Σ
{\displaystyle \Sigma }
U
(
u
,
v
)
{\displaystyle U_{(u,v)}}
U
v
{\displaystyle U_{v}}
U
b
{\displaystyle U_{b}}
콤팩트 리만 곡면 이다.
또한,
U
b
{\displaystyle U_{b}}
유한 집합
{
z
1
,
…
,
z
n
}
⊊
Σ
{\displaystyle \{z_{1},\dotsc ,z_{n}\}\subsetneq \Sigma }
U
(
u
,
v
)
{\displaystyle U_{(u,v)}}
정칙 이차 미분 들은 짜깁기를 통해
Σ
∖
{
z
1
,
…
,
z
n
}
{\displaystyle \Sigma \setminus \{z_{1},\dotsc ,z_{n}\}}
정칙 이차 미분 을 구성한다. 이는 각
z
i
{\displaystyle z_{i}}
극 을 가져,
Σ
∖
{
z
1
,
…
,
z
n
}
{\displaystyle \Sigma \setminus \{z_{1},\dotsc ,z_{n}\}}
슈트레벨 미분 을 이룬다. 이 경우, 경계 성분
b
{\displaystyle b}
b
{\displaystyle b}
띠그래프에 대응되는 벨리 사상
편집
(
Γ
,
σ
,
ℓ
)
{\displaystyle (\Gamma ,\sigma ,\ell )}
동치 이다.[1] :Theorem 6.5
(
Γ
,
σ
,
ℓ
)
{\displaystyle (\Gamma ,\sigma ,\ell )}
리만 곡면
Σ
{\displaystyle \Sigma }
대수적 수 의 체
Q
¯
{\displaystyle {\bar {\mathbb {Q} }}}
대수 곡선 을 이룬다. 즉, 벨리 사상
Σ
→
C
P
1
{\displaystyle \Sigma \to \mathbb {CP} ^{1}}
데생당팡 이 존재한다.모든 변의 길이가 같다.
조합론적 성질
편집
그래프
Γ
{\displaystyle \Gamma }
∏
v
∈
V
(
Γ
)
(
deg
Γ
v
−
1
)
!
{\displaystyle \prod _{v\in \operatorname {V} (\Gamma )}(\deg _{\Gamma }v-1)!}
여기서
deg
Γ
(
−
)
{\displaystyle \deg _{\Gamma }(-)}
위상수학적 성질
편집
띠그래프는 (CW 복합체 로 여겼을 때) 그 기하학적 실현과 항상 호모토피 동치 이지만, 보통 위상 동형 이 아니다.
띠그래프
(
Γ
,
σ
)
{\displaystyle (\Gamma ,\sigma )}
전단사 함수
i
:
E
¯
(
Γ
)
→
E
¯
(
Γ
)
{\displaystyle i\colon \operatorname {\bar {E}} (\Gamma )\to \operatorname {\bar {E}} (\Gamma )}
i
:
(
u
,
v
)
↦
(
v
,
u
)
{\displaystyle i\colon (u,v)\mapsto (v,u)}
를 생각하자. 그렇다면,
f
∘
i
{\displaystyle f\circ i}
i
∘
f
{\displaystyle i\circ f}
일대일 대응 이 존재한다.
순열
σ
∘
i
{\displaystyle \sigma \circ i}
순열
i
∘
σ
{\displaystyle i\circ \sigma }
Σ
Γ
,
σ
{\displaystyle \Sigma _{\Gamma ,\sigma }}
또한,
Γ
{\displaystyle \Gamma }
Σ
Γ
,
σ
{\displaystyle \Sigma _{\Gamma ,\sigma }}
n
{\displaystyle n}
g
{\displaystyle g}
g
=
1
2
(
2
−
|
V
(
Γ
)
|
+
|
E
(
Γ
)
|
−
n
)
{\displaystyle g={\frac {1}{2}}\left(2-|\operatorname {V} (\Gamma )|+|\operatorname {E} (\Gamma )|-n\right)}
나무 에 대응되는 곡면은 (띠그래프 구조에 상관 없이) 항상
Σ
0
,
1
{\displaystyle \Sigma _{0,1}}
구 이다.
순환 그래프
편집
꼭짓점
k
{\displaystyle k}
순환 그래프 는 유일한 띠그래프 구조를 갖는다. 구체적으로, 꼭짓점들을
(
v
i
)
i
∈
Z
/
(
k
)
{\displaystyle (v_{i})_{i\in \mathbb {Z} /(k)}}
σ
:
(
v
i
,
v
i
+
1
)
↦
(
v
i
,
v
i
−
1
)
{\displaystyle \sigma \colon (v_{i},v_{i+1})\mapsto (v_{i},v_{i-1})}
σ
:
(
v
i
,
v
i
−
1
)
↦
(
v
i
,
v
i
+
1
)
{\displaystyle \sigma \colon (v_{i},v_{i-1})\mapsto (v_{i},v_{i+1})}
이다. 이에 대응하는 곡면은
Σ
0
,
2
{\displaystyle \Sigma _{0,2}}
구 이다. 순환 그래프
Γ
{\displaystyle \Gamma }
|
V
(
Γ
)
|
=
|
E
(
Γ
)
|
=
k
{\displaystyle |\operatorname {V} (\Gamma )|=|\operatorname {E} (\Gamma )|=k}
이며, 순열
σ
∘
i
:
(
v
i
,
v
i
+
1
)
↦
(
v
i
+
1
,
v
i
+
2
)
{\displaystyle \sigma \circ i\colon (v_{i},v_{i+1})\mapsto (v_{i+1},v_{i+2})}
σ
∘
i
:
(
v
i
,
v
i
−
1
)
↦
(
v
i
−
1
,
v
i
−
2
)
{\displaystyle \sigma \circ i\colon (v_{i},v_{i-1})\mapsto (v_{i-1},v_{i-2})}
및
i
∘
σ
:
(
v
i
,
v
i
+
1
)
↦
(
v
i
−
1
,
v
i
)
{\displaystyle i\circ \sigma \colon (v_{i},v_{i+1})\mapsto (v_{i-1},v_{i})}
i
∘
σ
:
(
v
i
,
v
i
−
1
)
↦
(
v
i
+
1
,
v
i
)
{\displaystyle i\circ \sigma \colon (v_{i},v_{i-1})\mapsto (v_{i+1},v_{i})}
둘 다 각각 두 개의 순환을 갖는다. 이에 따라 종수가
g
=
1
2
(
2
−
k
+
k
−
2
)
=
0
{\displaystyle g={\frac {1}{2}}(2-k+k-2)=0}
임을 알 수 있다.
참고 문헌
편집
↑ 가 나 다 Mulase, Motohico; Penkava, Michael (1998). “Ribbon graphs, quadratic differentials on Riemann surfaces, and algebraic curves defined over ℚ̄”. 《The Asian Journal of Mathematics》 (영어) 2 (4): 875–920. arXiv :math-ph/9811024 . Bibcode :1998math.ph..11024M .
외부 링크
편집
![{\displaystyle (v,[u+v]/2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/921aebb14fdb22aba5437208d4179a45130f33a6)
