木と全域構造

木は連結で非巡回的なグラフであり、全域構造はより大きなグラフからそのような最小の連結骨格を抽出します。

Definition

木はサイクルを持たない連結グラフであり、連結グラフの全域木は、木であり、かつグラフのすべての頂点を含む部分グラフです。

Scope

このトピックでは、木の同値な特徴付け、根付き木とラベル付き木、全域木と全域森、およびケーリーの公式と行列木定理によるそれらの数え上げについて扱います。また、最適化問題としての最小全域木も導入し、グラフ理論とアルゴリズム設計および組み合わせ的数え上げを結びつけます。

Core questions

• グラフが木であるという同値な条件は何ですか？
• 与えられた数の頂点を持つラベル付き木はいくつありますか？
• 与えられたグラフにはいくつの全域木が含まれていますか？
• 最小総重みの全域木を効率的に見つけるにはどうすればよいですか？

Key concepts

• 非巡回連結グラフ
• 根付き木とラベル付き木
• 全域木と全域森
• プリューファー列
• ケーリーの公式
• 最小全域木

Key theories

ケーリーの公式

n個の頂点を持つ異なるラベル付き木は正確にn^(n-2)個存在します。これは、プリューファー列、行列木定理、またはいくつかの洗練された全単射によって証明可能な古典的な数え上げ結果です。

行列木定理

グラフの全域木の数は、そのラプラシアン行列の任意の余因子に等しく、全域木の組み合わせ的数え上げを線形代数と行列式に結びつけます。

Clinical relevance

全域木はネットワーク設計とブロードキャストルーティングの基礎となり、最小全域木は最小コスト接続問題を解決し、木構造はコンピュータサイエンス全体でデータと階層を整理します。

History

キルヒホフによる19世紀の電気回路の研究は行列木定理を生み出し、一方、ケーリーによる1889年のラベル付き木の数え上げは、数え上げグラフ理論において最も有名な公式の一つとなりました。

Key figures

• Arthur Cayley
• Gustav Kirchhoff
• Heinz Prufer

Seminal works

• diestel2017
• stanley2011

Frequently asked questions

n個の頂点を持つ木が正確にn-1個の辺を持つのはなぜですか？

木は連結であるため、少なくともn-1個の辺が必要であり、非巡回であるため、それ以上の辺は許されません。この2つの条件が合わさって、辺の数が正確にn-1個に固定されます。

全域木は何のために使われますか？

全域木は、ネットワークを連結に保つための最小限の接続セットを提供し、これは効率的なブロードキャストと最小コストのネットワーク設計の基礎となります。