📂グラフ理論

ラベルツリーとケイリーの定理

定義

各ベルテックスに異なる数が割り当てられたツリーをラベルツリーと言う。

説明

ラベルはベルテックスの集合において、実際に要素が同じか異なるかを区別することとはまた別の概念だ。例えば、次の二つのグラフは書かれているラベルが異なっていても、本質的には同じラベルツリーと見ることができる。

$$1-2-3 \\ a-b-c$$ もちろんグラフであるからには次の二つも同じとされる。 $$1-2-3 \\ 3-2-1$$ しかし、次の二つのグラフはラベルがついている状態で明確に区別される。 $$1-2-3 \\ 2-3-1$$ このようなラベルツリーの数を数えることは、順列よりもずっと多い場合の数があるということを意味している。順列は区別される要素が順番に並ぶが、ツリーの場合は枝が伸びて行くにつれてカウントが非常に複雑になる。幸いなことに、これに関しては次の定理が知られている。

ケイリーの定理 ¹

ベルテックスが$n$個のラベルツリーは、$n^{n-2}$通り存在する。

例えば、$n=2$ならば、ただ$2^{2-2} = 1$通りの$1$と$2$が繋がった場合のみ存在する。$n=3$ならば、以下のように$3^{3-2} = 3$通りの場合がある。 $$2-1-3 \\ 3-2-1 \\ 1-3-2$$

意義

ラベルツリーの数を数えることは、化学のような分野でまだ発見されていない分子構造を予測し発見するような形で応用されることができる。このように純粋なグラフ理論は組合せ論が織り込まれた問題に大きな関心を示し、依然として活発に研究されている。