# 定義 - [[連結グラフ]]$G$に対するスパニングツリーとは、ツリーとなる$G$の[[部分グラフ]]である。 - どの2点間にも枝が存在する$n$個の点からなるグラフ（[[完全グラフ]])に対して、スパニングツリーの数は$n^{n-2}$となることが知られている ## 関連 - [[最小スパニングツリー]] ## 参考 - https://orsj.org/wp-content/or-archives50/pdf/bul/Vol.25_12_780.pdf