나무 그래프

그래프 이론에서 나무 그래프(영어: tree graph 트리 그래프^[*]) 또는 단순히 나무(영어: tree 트리^[*])는 순환을 갖지 않는 연결 그래프이다.

정의

그래프 $T$ 에 대하여 다음 조건들이 서로 동치이며, 이 조건을 만족시키는 그래프 $T$ 를 숲 그래프(영어: forest graph 포리스트 그래프^[*])이라고 한다.

$T$ 는 (길이 3 이상의) 순환을 갖지 않는다.
임의의 두 꼭짓점 $v_{1}, v_{2} \in V (T)$ 에 대하여, $v_{1}$ 과 $v_{2}$ 사이의 경로의 수는 1 이하이다.
$T$ 는 완전 그래프 $K_{3}$ 를 마이너로 갖지 않는다.
$T$ 는 단일 연결 공간이다. (즉, 임의의 밑점 $v \in V (T)$ 에 대하여, 1차 세포 호몰로지 $H_{1} (T, v)$ 가 자명군이다. 그러나 연결 공간이 아닐 수 있다.)

그래프 $T$ 에 대하여 다음 조건들이 서로 동치이며, 이 조건을 만족시키는 그래프 $T$ 를 나무 그래프라고 한다.

$T$ 는 숲 그래프이며, 연결 그래프이다 (즉, 정확히 1개의 연결 성분을 갖는다).
임의의 두 꼭짓점 $v_{1}, v_{2} \in V (T)$ 에 대하여, $v_{1}$ 과 $v_{2}$ 사이의 경로가 정확히 하나 존재한다.
$T$ 는 (1차원 세포 복합체로서) 연결 단일 연결 공간이다. (특히, 공집합이 아니다.)
하나 이상의 꼭짓점을 가지며, 임의의 변 $e \in E (T)$ 을 지운 그래프 $T - e$ 는 연결 그래프가 아니다.

나무 그래프 $T$ 의 잎 꼭짓점(영어: leaf vertex 리프 버텍스^[*])은 차수가 1인 꼭짓점이며, 내부 꼭짓점(영어: internal vertex)은 차수가 2 이상인 꼭짓점이다.

성질

숲 그래프 $T$ 에 대하여 다음이 성립한다.

$| V (T) | = | E (T) | + | Conn (T) |$

여기서

$| V (T) |$ 는 $T$ 의 꼭짓점의 수이다.
$| E (T) |$ 는 $T$ 의 변의 수이다.
$| Conn (T) |$ 는 $T$ 의 연결 성분의 수이다.

특히, 나무 그래프의 경우 하나의 연결 성분을 가지므로, $| V (T) | = | E (T) | + 1$ 이다. 반대로 $| V (T) | = | E (T) | + 1$ 인 유한 연결 그래프는 항상 나무 그래프이다.

모든 숲 그래프는 이분 그래프이자 평면 그래프이다.

나무 그래프의 수

$n$ 개의 꼭짓점을 갖는 나무 그래프의 동형류의 수는 다음과 같다 ( $n = 0, 1, 2, \dots$ ).

1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … (OEIS의 수열 A000055)

$n$ 개의 꼭짓점을 갖는 숲 그래프의 동형류의 수는 다음과 같다 ( $n = 0, 1, 2, \dots$ ).

1, 1, 2, 3, 6, 10, 20, 37, 76, 153, 329, 710, 1601, 3658, … (OEIS의 수열 A005195)

프뤼퍼 열

유한 나무 그래프 $T$ 의 꼭짓점 집합

V (T)

에 임의의 정렬 순서를 주고, 그 순서형을 $n \in Ord$ 이라고 하자.

$T$ 에 대하여, 꼭짓점 열

x_{0}, x_{1}, \dots

을 다음과 같이 재귀적으로 정의하자.

x_{i} = \min {v \in V (T) ∖ {x_{j}}_{j < i} : \deg_{T ∖ {x_{j}}_{j < i}} v = 1}

즉, 다음과 같다.

임의의 순서수 $i < | V (T) |$ 에 대하여, $x_{i} \in V (T)$ 은 $T ∖ {x_{j}}_{j < i}$ 의 잎 꼭짓점 가운데, 정렬 순서에 대하여 최소 원소이다.

유한 나무 그래프의 경우, 이 열은 $T$ 의 모든 꼭짓점을 한 번씩 포함한다. 즉, $T$ 의 꼭짓점 집합 $V (T)$ 위의 또다른 정렬 순서를 정의한다. (반면, 무한 나무 그래프의 경우 이는 그렇지 못할 수 있다.)

또한, 다음과 같은 꼭짓점 열

y_{0}, y_{1}, \dots

을 $(x_{i})_{i < | V (T) |}$ 로부터 정의할 수 있다.

(x_{i}, y_{i}) \in E (T ∖ {x_{j}}_{j < i})

즉,

$y_{i}$ 는 $T ∖ {v_{j}}_{j < i}$ 에서 $x_{i}$ 와 인접한 유일한 내부 꼭짓점이다. (만약 이러한 꼭짓점이 존재하지 않는다면, 이 열은 끝나게 된다.)

유한 나무 그래프의 경우, 꼭짓점 열 $y_{i}$ 의 길이는 $n - 1$ 인데, 이는 맨 “마지막”의 경우 꼭짓점이 하나 밖에 남지 않기 때문이다.

$(y_{i})$ 를 $T$ 의 프뤼퍼 열(Prüfer列, 영어: Prüfer sequence)이라고 한다.

또한, 프뤼퍼 열에 대하여 다음이 성립한다.

유한 나무 그래프	프뤼퍼 열
꼭짓점의 수	프뤼퍼 열의 길이 + 2
변의 수	프뤼퍼 열의 길이 + 1
잎 꼭짓점	프뤼퍼 열에 등장하지 않는 꼭짓점
내부 꼭짓점	프뤼퍼 열에 등장하는 꼭짓점
꼭짓점의 차수	프뤼퍼 열에 등장하는 수 + 1

모든 유한 나무 그래프는 그 프뤼퍼 열로부터 재구성될 수 있다. 이 알고리즘은 대략 다음과 같다.

우선, 각 꼭짓점 $v$ 에 대하여 양의 정수 값의 변수 $𝚍_{v}$ 를, $v_{i}$ 가 프뤼퍼 열에 등장하는 수 + 1로 놓는다.
프뤼퍼 열의 첫째 꼭짓점 y0에 대하여, 𝖽v=1인 최소의 꼭짓점을 v라고 하면,
1. 변 $(v, a_{v})$ 를 그래프에 추가하며,
2. $𝚍_{y_{0}}$ 과 $𝚍_{v}$ 를 각각 1만큼 감소시킨다.
위 단계를 프뤼퍼 열의 둘째, 셋째 등등 꼭짓점에 대하여 반복한다.
이 과정이 끝나면, $𝚍_{v} = 1$ 인 꼭짓점이 두 개 남는다. 이들 사이에 변을 추가한다.
알고리즘 종료.

(반면, 무한 나무 그래프의 경우 이는 일반적으로 불가능하다. 예를 들어, 양쪽 무한 경로 그래프는 나무 그래프이지만, 잎 꼭짓점을 갖지 않아, 프뤼퍼 열이 자명하다.)

케일리 공식

임의의 크기 $n$ 의 유한 집합 $V$ 가 주어졌다고 하자. 그렇다면, $V$ 를 꼭짓점으로 하는 나무 그래프의 수를 $T_{n}$ 이라고 하자. (이 경우, 꼭짓점들이 서로 구별되므로, 이는 나무 그래프의 동형류의 수와 다르다.) 케일리 공식(영어: Cayley’s formula)에 따르면, 이는 다음과 같다.^[1]

T_{n} = n^{n - 2}

증명:

꼭짓점 집합 $V$ 에 임의의 정렬 순서를 주자. 그렇다면, $V$ 위의 임의의 나무 그래프는 프뤼퍼 열에 유일하게 대응하며, 반대로 모든 프뤼퍼 열은 나무 그래프에 유일하게 대응된다. 프뤼퍼 열의 수는

n^{n - 2}

이다.

크기 $n$ 의 유한 집합 위의 숲 그래프의 수는 다음과 같다. ( $n = 0, 1, 2, \dots$ )

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}

라고 표기하면, 그 생성 함수는

\sum_{i = 0}^{\infty} \frac{1}{i!} c_{i} x^{i} = \exp (\sum_{n = 1}^{\infty} n^{n - 2} \frac{1}{n!} x^{n}) = 1 + x + \frac{1}{2} (2 x^{2}) + \frac{1}{6} (7 x^{3}) + \dots

이다.

증명:

크기 $N$ 의 집합의 분할에서, 크기 $n$ 의 성분의 수가 $k_{n}$ 이라고 하자. 즉,

\sum_{n = 1}^{\infty} n k_{n} = N

이다.

이 경우, 주어진 분할을 연결 성분 분할로 갖는 숲 그래프의 수는

\prod_{n = 1}^{\infty} (T_{n})^{k_{n}}

이다.

크기 $N$ 의 집합의 경우, 이러한 분할의 수는

(\binom{N!}{\prod_{n = 1}^{\infty} (n!)^{k_{n}} k_{n}!})

이다.

따라서, 생성 함수 $f (x)$ 는 다음과 같은 유한 중복집합에 대한 합으로 나타내어진다.

\begin{matrix} f (x) & = \sum_{k \in M} \frac{x^{| k |}}{| k |!} \frac{| k |!}{\prod_{n = 1}^{\infty} (n!)^{k_{n}} k_{n}!} \prod_{n = 1}^{\infty} (T_{n})^{k_{n}} \\ = \sum_{k \in M} \prod_{n = 1}^{\infty} {(\frac{T_{n} x_{n}}{n!})}^{k_{n}} \frac{1}{k_{n}!} \\ = \prod_{n = 1}^{\infty} \sum_{k_{n} = 0}^{\infty} {(\frac{T_{n} x_{n}}{n!})}^{k_{n}} \frac{1}{k_{n}!} \\ = \prod_{n = 1}^{\infty} \exp (T_{n} x^{n} / n!) \\ = \exp (\sum_{n = 1}^{\infty} T_{n} x^{n} / n!) \end{matrix}

여기서 $M$ 는 유한 중복집합들, 즉 함수

k : ℤ^{+} \to ℕ

k : n \mapsto k_{n}

가운데

\sum_{n = 1}^{\infty} n k_{n} < \infty

인 것들의 족이며,

| k | = \sum_{n = 1}^{\infty} n k_{n}

이다.

예

정의에 따라, 모든 무변 그래프는 숲 그래프이며, 특히 한원소 그래프 $K_{1}$ 은 나무 그래프이다.

임의의 양의 정수 $n$ 에 대하여, 경로 그래프 $P_{n}$ 은 나무 그래프이다. 또한, 양쪽 무한 경로 그래프

P_{\infty}

및 한쪽 무한 경로 그래프

P_{\infty}^{+}

역시 둘 다 나무 그래프이다.

프뤼퍼 열의 예

다음과 같은 유한 나무 그래프 $T$ 를 생각하자.

섬네일을 만드는 중 오류 발생:

이 경우,

잎 꼭짓점들은 ${1, 2, 3, 6}$ 이며, 이 가운데 최솟값은 1이다. 이는 꼭짓점 4에 연결되어 있다. 즉, $x_{0} = 1$ 이며 $y_{0} = 4$ 이다. 이제, 꼭짓점 1을 제거하자.
$T ∖ {1}$ 에서, 잎 꼭짓점들은 ${2, 3, 6}$ 이며, 이 가운데 최솟값은 2이다. 이는 꼭짓점 4에 연결되어 있다. 즉, $x_{1} = 2$ 이며 $y_{1} = 4$ 이다. 이제, 꼭짓점 2를 제거하자.
$T ∖ {1, 2}$ 에서, 잎 꼭짓점들은 ${3, 6}$ 이며, 이 가운데 최솟값은 3이다. 이는 꼭짓점 4에 연결되어 있다. 즉, $x_{2} = 3$ 이며 $y_{2} = 4$ 이다. 이제, 꼭짓점 3을 제거하자.
$T ∖ {1, 2, 3}$ 에서, 잎 꼭짓점들은 ${4, 6}$ 이며, 이 가운데 최솟값은 4이다. 이는 꼭짓점 5에 연결되어 있다. 즉, $x_{3} = 4$ 이며 $y_{2} = 5$ 이다. 이제, 꼭짓점 4를 제거하자.
$T ∖ {1, 2, 3, 4}$ 에서, 잎 꼭짓점들은 ${5, 6}$ 이며, 이 가운데 최솟값은 5이다. 즉, $x_{4} = 5$ 이다. 이는 꼭짓점 6에 연결되어 있으나, 이 역시 잎 꼭짓점이므로, 프뤼퍼 열은 끝난다.

즉,

(y_{0}, \dots, y_{4}) = (4, 4, 4, 5)

이다.

역사

케일리 공식은 1860년에 카를 빌헬름 보르하르트(독일어: Carl Wilhelm Borchardt, 1817~1880)가 최초로 증명하였다.^[2] 이후 1889년에 아서 케일리가 같은 정리의 새 증명을 발표하였다.^[3] 케일리는 보르하르트의 논문을 인용하였지만, 이 공식은 더 유명한 케일리의 이름을 따 불리게 되었다.

에른스트 파울 하인츠 프뤼퍼(독일어: Ernst Paul Heinz Prüfer, 1896~1934)는 1918년에 프뤼퍼 열을 도입하였으며, 이를 사용하여 이에 대한 다른 증명을 제시하였다.^[4]

같이 보기

각주

↑ 서승현; 권석일; 홍진곤 (2008년 8월). “케일리 공식의 네 가지 증명”. 《한국수학사학회지》 21 (3): 127–142. 2021년 3월 8일에 원본 문서에서 보존된 문서. 2017년 7월 10일에 확인함.
↑ Borchardt, Carl Wilhelm (1860). “Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung” (독일어). 《Abhandlungen der Königlichen Akademie der Wissenschaften zu Berlin. Mathematische Klasse》: 1–20.
↑ Cayley, Arthur (1889). “A theorem on trees” (영어). 《The Quarterly Journal of Pure and Applied Mathematics》 23: 376–378. JFM 21.0687.01.
↑ Prüfer, Heinz (1918). “Neuer Beweis eines Satzes über Permutationen” (영어). 《Archiv der Mathematik und Physik》 27: 742–744. JFM 46.0106.04.

외부 링크

“Tree” (영어). 《Encyclopedia of Mathematics》. Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
Weisstein, Eric Wolfgang. “Tree” (영어). 《Wolfram MathWorld》. Wolfram Research.
Weisstein, Eric Wolfgang. “Forest” (영어). 《Wolfram MathWorld》. Wolfram Research.
Weisstein, Eric Wolfgang. “Prüfer code” (영어). 《Wolfram MathWorld》. Wolfram Research.

모듈:Authority_control 159번째 줄에서 Lua 오류: attempt to index field 'wikibase' (a nil value).

[1] 서승현; 권석일; 홍진곤 (2008년 8월). “케일리 공식의 네 가지 증명”. 《한국수학사학회지》 21 (3): 127–142. 2021년 3월 8일에 원본 문서에서 보존된 문서. 2017년 7월 10일에 확인함.

[2] Borchardt, Carl Wilhelm (1860). “Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung” (독일어). 《Abhandlungen der Königlichen Akademie der Wissenschaften zu Berlin. Mathematische Klasse》: 1–20.

[3] Cayley, Arthur (1889). “A theorem on trees” (영어). 《The Quarterly Journal of Pure and Applied Mathematics》 23: 376–378. JFM 21.0687.01.

[4] Prüfer, Heinz (1918). “Neuer Beweis eines Satzes über Permutationen” (영어). 《Archiv der Mathematik und Physik》 27: 742–744. JFM 46.0106.04.

[1]

[2]

[3]

[4]