그래프
T
{\displaystyle T}
동치 이며, 이 조건을 만족시키는 그래프
T
{\displaystyle T}
숲 그래프 (영어 : forest graph 포리스트 그래프[* ] )이라고 한다.
T
{\displaystyle T}
순환 을 갖지 않는다.임의의 두 꼭짓점
v
1
,
v
2
∈
V
(
T
)
{\displaystyle v_{1},v_{2}\in \operatorname {V} (T)}
v
1
{\displaystyle v_{1}}
v
2
{\displaystyle v_{2}}
경로 의 수는 1 이하이다.
T
{\displaystyle T}
완전 그래프
K
3
{\displaystyle K_{3}}
마이너 로 갖지 않는다.
T
{\displaystyle T}
단일 연결 공간 이다. (즉, 임의의 밑점
v
∈
V
(
T
)
{\displaystyle v\in \operatorname {V} (T)}
세포 호몰로지
H
1
(
T
,
v
)
{\displaystyle \operatorname {H} _{1}(T,v)}
자명군 이다. 그러나 연결 공간 이 아닐 수 있다.)그래프
T
{\displaystyle T}
동치 이며, 이 조건을 만족시키는 그래프
T
{\displaystyle T}
나무 그래프 라고 한다.
T
{\displaystyle T}
연결 그래프 이다 (즉, 정확히 1개의 연결 성분 을 갖는다).임의의 두 꼭짓점
v
1
,
v
2
∈
V
(
T
)
{\displaystyle v_{1},v_{2}\in V(T)}
v
1
{\displaystyle v_{1}}
v
2
{\displaystyle v_{2}}
경로 가 정확히 하나 존재한다.
T
{\displaystyle T}
세포 복합체 로서) 연결 단일 연결 공간 이다. (특히, 공집합 이 아니다.)하나 이상의 꼭짓점을 가지며, 임의의 변
e
∈
E
(
T
)
{\displaystyle e\in \operatorname {E} (T)}
T
−
e
{\displaystyle T-e}
연결 그래프 가 아니다. 나무 그래프
T
{\displaystyle T}
잎 꼭짓점 (영어 : leaf vertex 리프 버텍스[* ] )은 차수가 1인 꼭짓점이며, 내부 꼭짓점 (영어 : internal vertex )은 차수가 2 이상인 꼭짓점이다.
숲 그래프
T
{\displaystyle T}
|
V
(
T
)
|
=
|
E
(
T
)
|
+
|
Conn
(
T
)
|
{\displaystyle |\operatorname {V} (T)|=|\operatorname {E} (T)|+|\operatorname {Conn} (T)|}
여기서
|
V
(
T
)
|
{\displaystyle |\operatorname {V} (T)|}
T
{\displaystyle T}
|
E
(
T
)
|
{\displaystyle |\operatorname {E} (T)|}
T
{\displaystyle T}
|
C
o
n
n
(
T
)
|
{\displaystyle |\operatorname {C} onn(T)|}
T
{\displaystyle T}
특히, 나무 그래프의 경우 하나의 연결 성분을 가지므로,
|
V
(
T
)
|
=
|
E
(
T
)
|
+
1
{\displaystyle |\operatorname {V} (T)|=|\operatorname {E} (T)|+1}
모든 숲 그래프는 이분 그래프 이자 평면 그래프 이다.
n
{\displaystyle n}
동형류 의 수는 다음과 같다 (
n
=
0
,
1
,
2
,
…
{\displaystyle n=0,1,2,\dots }
1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … (OEIS 의 수열 A000055 )
n
{\displaystyle n}
동형류 의 수는 다음과 같다 (
n
=
0
,
1
,
2
,
…
{\displaystyle n=0,1,2,\dots }
1, 1, 2, 3, 6, 10, 20, 37, 76, 153, 329, 710, 1601, 3658, … (OEIS 의 수열 A005195 ) 유한 나무 그래프
T
{\displaystyle T}
V
(
T
)
{\displaystyle \operatorname {V} (T)}
에 임의의 정렬 순서 를 주고, 그 순서형 을
n
∈
Ord
{\displaystyle n\in \operatorname {Ord} }
T
{\displaystyle T}
열
x
0
,
x
1
,
…
{\displaystyle x_{0},x_{1},\dotsc }
을 다음과 같이 재귀적으로 정의하자.
x
i
=
min
{
v
∈
V
(
T
)
∖
{
x
j
}
j
<
i
:
deg
T
∖
{
x
j
}
j
<
i
v
=
1
}
{\displaystyle x_{i}=\min\{v\in \operatorname {V} (T)\setminus \{x_{j}\}_{j<i}\colon \deg _{T\setminus \{x_{j}\}_{j<i}}v=1\}}
즉, 다음과 같다.
임의의 순서수
i
<
|
V
(
T
)
|
{\displaystyle i<|\operatorname {V} (T)|}
x
i
∈
V
(
T
)
{\displaystyle x_{i}\in \operatorname {V} (T)}
T
∖
{
x
j
}
j
<
i
{\displaystyle T\setminus \{x_{j}\}_{j<i}}
정렬 순서 에 대하여 최소 원소 이다. 유한 나무 그래프의 경우, 이 열은
T
{\displaystyle T}
T
{\displaystyle T}
V
(
T
)
{\displaystyle \operatorname {V} (T)}
정렬 순서 를 정의한다. (반면, 무한 나무 그래프의 경우 이는 그렇지 못할 수 있다.)
또한, 다음과 같은 꼭짓점 열
y
0
,
y
1
,
…
{\displaystyle y_{0},y_{1},\dotsc }
을
(
x
i
)
i
<
|
V
(
T
)
|
{\displaystyle (x_{i})_{i<|\operatorname {V} (T)|}}
(
x
i
,
y
i
)
∈
E
(
T
∖
{
x
j
}
j
<
i
)
{\displaystyle (x_{i},y_{i})\in \operatorname {E} (T\setminus \{x_{j}\}_{j<i})}
즉,
y
i
{\displaystyle y_{i}}
T
∖
{
v
j
}
j
<
i
{\displaystyle T\setminus \{v_{j}\}_{j<i}}
x
i
{\displaystyle x_{i}}
유한 나무 그래프의 경우, 꼭짓점 열
y
i
{\displaystyle y_{i}}
n
−
1
{\displaystyle n-1}
(
y
i
)
{\displaystyle (y_{i})}
T
{\displaystyle T}
프뤼퍼 열 (Prüfer列, 영어 : Prüfer sequence )이라고 한다.
또한, 프뤼퍼 열에 대하여 다음이 성립한다.
유한 나무 그래프
프뤼퍼 열
꼭짓점의 수
프뤼퍼 열의 길이 + 2
변의 수
프뤼퍼 열의 길이 + 1
잎 꼭짓점
프뤼퍼 열에 등장하지 않는 꼭짓점
내부 꼭짓점
프뤼퍼 열에 등장하는 꼭짓점
꼭짓점의 차수
프뤼퍼 열에 등장하는 수 + 1
모든 유한 나무 그래프는 그 프뤼퍼 열로부터 재구성될 수 있다. 이 알고리즘은 대략 다음과 같다.
우선, 각 꼭짓점
v
{\displaystyle v}
d
v
{\displaystyle {\mathtt {d}}_{v}}
v
i
{\displaystyle v_{i}}
프뤼퍼 열의 첫째 꼭짓점
y
0
{\displaystyle y_{0}}
d
v
=
1
{\displaystyle {\mathsf {d}}_{v}=1}
v
{\displaystyle v}
변
(
v
,
a
v
)
{\displaystyle (v,a_{v})}
그래프 에 추가하며,
d
y
0
{\displaystyle {\mathtt {d}}_{y_{0}}}
d
v
{\displaystyle {\mathtt {d}}_{v}}
위 단계를 프뤼퍼 열의 둘째, 셋째 등등 꼭짓점에 대하여 반복한다.
이 과정이 끝나면,
d
v
=
1
{\displaystyle {\mathtt {d}}_{v}=1}
알고리즘 종료. (반면, 무한 나무 그래프의 경우 이는 일반적으로 불가능하다. 예를 들어, 양쪽 무한 경로 그래프 는 나무 그래프이지만, 잎 꼭짓점을 갖지 않아, 프뤼퍼 열이 자명하다.)
임의의 크기
n
{\displaystyle n}
유한 집합
V
{\displaystyle V}
V
{\displaystyle V}
T
n
{\displaystyle T_{n}}
케일리 공식 (영어 : Cayley’s formula )에 따르면, 이는 다음과 같다.[ 1]
T
n
=
n
n
−
2
{\displaystyle T_{n}=n^{n-2}}
증명 :
꼭짓점 집합
V
{\displaystyle V}
정렬 순서 를 주자. 그렇다면,
V
{\displaystyle V}
n
n
−
2
{\displaystyle n^{n-2}}
이다.
크기
n
{\displaystyle n}
유한 집합 위의 숲 그래프의 수는 다음과 같다. (
n
=
0
,
1
,
2
,
…
{\displaystyle n=0,1,2,\dotsc }
1, 1, 2, 7, 38, 291, 2932, 36961, 561948, 10026505, 205608536, 4767440679, 123373203208, 3525630110107, 110284283006640, 3748357699560961, 137557910094840848, 5421179050350334929, 228359487335194570528, 10239206473040881277575, 486909744862576654283616, … (OEIS 의 수열 A1858 ) 이 자연수열을
c
i
{\displaystyle c_{i}}
라고 표기하면, 그 생성 함수 는
∑
i
=
0
∞
1
i
!
c
i
x
i
=
exp
(
∑
n
=
1
∞
n
n
−
2
1
n
!
x
n
)
=
1
+
x
+
1
2
(
2
x
2
)
+
1
6
(
7
x
3
)
+
⋯
{\displaystyle \sum _{i=0}^{\infty }{\frac {1}{i!}}c_{i}x^{i}=\exp \left(\sum _{n=1}^{\infty }n^{n-2}{\frac {1}{n!}}x^{n}\right)=1+x+{\frac {1}{2}}(2x^{2})+{\frac {1}{6}}(7x^{3})+\dotsb }
이다.
증명 :
크기
N
{\displaystyle N}
분할 에서, 크기
n
{\displaystyle n}
k
n
{\displaystyle k_{n}}
∑
n
=
1
∞
n
k
n
=
N
{\displaystyle \sum _{n=1}^{\infty }nk_{n}=N}
이다.
이 경우, 주어진 분할을 연결 성분 분할로 갖는 숲 그래프의 수는
∏
n
=
1
∞
(
T
n
)
k
n
{\displaystyle \prod _{n=1}^{\infty }(T_{n})^{k_{n}}}
이다.
크기
N
{\displaystyle N}
분할 의 수는
(
N
!
∏
n
=
1
∞
(
n
!
)
k
n
k
n
!
)
{\displaystyle {\binom {N!}{\prod _{n=1}^{\infty }(n!)^{k_{n}}k_{n}!}}}
이다.
따라서, 생성 함수
f
(
x
)
{\displaystyle f(x)}
중복집합 에 대한 합으로 나타내어진다.
f
(
x
)
=
∑
k
∈
M
x
|
k
|
|
k
|
!
|
k
|
!
∏
n
=
1
∞
(
n
!
)
k
n
k
n
!
∏
n
=
1
∞
(
T
n
)
k
n
=
∑
k
∈
M
|
k
|
!
|
k
|
!
x
|
k
|
∏
n
=
1
∞
(
T
n
)
k
n
∏
n
=
1
∞
(
n
!
)
k
n
k
n
!
=
∑
k
∈
M
x
|
k
|
∏
n
=
1
∞
(
T
n
n
!
)
k
n
1
k
n
!
=
∑
k
∈
M
x
∑
n
=
1
∞
n
k
n
∏
n
=
1
∞
(
T
n
n
!
)
k
n
1
k
n
!
=
∑
k
∈
M
∏
n
=
1
∞
x
n
k
n
∏
n
=
1
∞
(
T
n
n
!
)
k
n
1
k
n
!
=
∑
k
∈
M
∏
n
=
1
∞
(
T
n
x
n
n
!
)
k
n
1
k
n
!
=
∏
n
=
1
∞
∑
k
n
=
0
∞
(
T
n
x
n
n
!
)
k
n
1
k
n
!
=
∏
n
=
1
∞
exp
(
T
n
x
n
n
!
)
=
exp
(
∑
n
=
1
∞
T
n
x
n
n
!
)
=
exp
(
∑
n
=
1
∞
T
n
1
n
!
x
n
)
{\displaystyle {\begin{aligned}f(x)&=\sum _{k\in M}{{x^{|k|}} \over {|k|!}}{{|k|!} \over {\prod _{n=1}^{\infty }(n!)^{k_{n}}k_{n}!}}\prod _{n=1}^{\infty }(T_{n})^{k_{n}}\\&=\sum _{k\in M}{{|k|!} \over {|k|!}}{{x^{|k|}{\prod _{n=1}^{\infty }(T_{n})^{k_{n}}}} \over {\prod _{n=1}^{\infty }(n!)^{k_{n}}{k_{n}!}}}\\&=\sum _{k\in M}{x^{|k|}}\prod _{n=1}^{\infty }\left({{T_{n}} \over {n!}}\right)^{k_{n}}{{1} \over {k_{n}!}}\\&=\sum _{k\in M}{x^{\sum _{n=1}^{\infty }nk_{n}}}\prod _{n=1}^{\infty }\left({{T_{n}} \over {n!}}\right)^{k_{n}}{{1} \over {k_{n}!}}\\&=\sum _{k\in M}\prod _{n=1}^{\infty }{x_{n}^{k_{n}}}\prod _{n=1}^{\infty }\left({{T_{n}} \over {n!}}\right)^{k_{n}}{{1} \over {k_{n}!}}\\&=\sum _{k\in M}\prod _{n=1}^{\infty }\left({{T_{n}x_{n}} \over {n!}}\right)^{k_{n}}{{1} \over {k_{n}!}}\\&=\prod _{n=1}^{\infty }\sum _{k_{n}=0}^{\infty }\left({{T_{n}x_{n}} \over {n!}}\right)^{k_{n}}{{1} \over {k_{n}!}}\\&=\prod _{n=1}^{\infty }\exp \left({{T_{n}x^{n}} \over {n!}}\right)\\&=\exp \left(\sum _{n=1}^{\infty }{{T_{n}x^{n}} \over {n!}}\right)\\&=\exp \left(\sum _{n=1}^{\infty }T_{n}{{1} \over {n!}}x^{n}\right)\end{aligned}}}
여기서
M
{\displaystyle M}
중복집합 들, 즉 함수
k
:
Z
+
→
N
{\displaystyle k\colon \mathbb {Z} ^{+}\to \mathbb {N} }
k
:
n
↦
k
n
{\displaystyle k\colon n\mapsto k_{n}}
가운데
∑
n
=
1
∞
n
k
n
<
∞
{\displaystyle \sum _{n=1}^{\infty }nk_{n}<\infty }
인 것들의 족이며,
|
k
|
=
∑
n
=
1
∞
n
k
n
{\displaystyle |k|=\sum _{n=1}^{\infty }nk_{n}}
이고,
T
n
=
n
n
−
2
{\displaystyle T_{n}=n^{n-2}}
정의에 따라, 모든 무변 그래프 는 숲 그래프이며, 특히 한원소 그래프
K
1
{\displaystyle K_{1}}
임의의 양의 정수
n
{\displaystyle n}
경로 그래프
P
n
{\displaystyle P_{n}}
경로 그래프
P
∞
{\displaystyle P_{\infty }}
및 한쪽 무한 경로 그래프
P
∞
+
{\displaystyle P_{\infty }^{+}}
역시 둘 다 나무 그래프이다.
다음과 같은 유한 나무 그래프
T
{\displaystyle T}
이 경우,
잎 꼭짓점들은
{
1
,
2
,
3
,
6
}
{\displaystyle \{1,2,3,6\}}
x
0
=
1
{\displaystyle x_{0}=1}
y
0
=
4
{\displaystyle y_{0}=4}
T
∖
{
1
}
{\displaystyle T\setminus \{1\}}
{
2
,
3
,
6
}
{\displaystyle \{2,3,6\}}
x
1
=
2
{\displaystyle x_{1}=2}
y
1
=
4
{\displaystyle y_{1}=4}
T
∖
{
1
,
2
}
{\displaystyle T\setminus \{1,2\}}
{
3
,
6
}
{\displaystyle \{3,6\}}
x
2
=
3
{\displaystyle x_{2}=3}
y
2
=
4
{\displaystyle y_{2}=4}
T
∖
{
1
,
2
,
3
}
{\displaystyle T\setminus \{1,2,3\}}
{
4
,
6
}
{\displaystyle \{4,6\}}
x
3
=
4
{\displaystyle x_{3}=4}
y
2
=
5
{\displaystyle y_{2}=5}
T
∖
{
1
,
2
,
3
,
4
}
{\displaystyle T\setminus \{1,2,3,4\}}
{
5
,
6
}
{\displaystyle \{5,6\}}
x
4
=
5
{\displaystyle x_{4}=5}
즉,
(
y
0
,
…
,
y
4
)
=
(
4
,
4
,
4
,
5
)
{\displaystyle (y_{0},\dotsc ,y_{4})=(4,4,4,5)}
이다.
케일리 공식은 1860년에 카를 빌헬름 보르하르트(독일어 : Carl Wilhelm Borchardt , 1817~1880)가 최초로 증명하였다.[ 2] 아서 케일리 가 같은 정리의 새 증명을 발표하였다.[ 3]
에른스트 파울 하인츠 프뤼퍼(독일어 : Ernst Paul Heinz Prüfer , 1896~1934)는 1918년에 프뤼퍼 열을 도입하였으며, 이를 사용하여 이에 대한 다른 증명을 제시하였다.[ 4]
