📂그래프이론

레이블 트리와 케일리 정리

정의

각 버텍스에 서로 다른 수가 부여된 트리를 레이블 트리라 한다.

설명

레이블은 버텍스의 집합과 같이 실제로 원소가 같은지 다른지 구분하는 것과는 다른 개념이다. 가령 다음의 두 그래프는 쓰여있기는 달라도 본질적으로 같은 레이블 트리로 볼 수 있다.

$$ 1-2-3 \\ a-b-c $$ 물론 그래프기 때문에 다음의 두 경우는 서로 같다. $$ 1-2-3 \\ 3-2-1 $$ 그러나 다음 두 그래프는 레이블이 부여된 상태에서 확실히 구분된다. $$ 1-2-3 \\ 2-3-1 $$ 이러한 레이블 트리의 수를 모두 카운트하는 것은 조합론의 순열보다 훨씬 많은 경우의 수가 있다. 순열은 서로 구분되는 원소들이 순서대로 이어지지만, 트리의 경우 가지가 뻗어나가면서 카운팅이 몹시 복잡해지기 때문이다. 다행스럽게도 이에 대해서는 다음의 정리가 알려져있다.

케일리 정리 ¹

버텍스가 $n$ 개인 레이블 트리는 $n^{n-2}$ 가지만큼 존재한다.

가령 $n=2$ 면 그냥 $1$ 과 $2$ 가 연결된 $2^{2-2} = 1$ 가지의 경우만 있다. $n=3$ 이면 다음과 같이 $3^{3-2} = 3$ 가지 경우가 있다. $$ 2-1-3 \\ 3-2-1 \\ 1-3-2 $$

의의

레이블 트리의 수를 세는 것은 화학과 같은 분야에서 아직 발견되지 않은 분자구조를 예측하고 발견하는 식으로 응용될 수 있다. 이렇듯 순수 그래프 이론은 조합론이 접목된 문제에 큰 관심을 보이며, 여전히 활발하게 연구되고 있다.