全域木

グラフ理論において、グラフの全域木（ぜんいきぎ、英: Spanning tree）、極大木（きょくだいき）、スパニング木、スパニングツリーとは、全域部分グラフ（そのグラフの全頂点を含む部分グラフ）のうち、木（連結で閉路を持たないグラフ）であるものをいう。全域木は連結グラフに必ず存在し、連結でないグラフには存在しない。