最小全域木

今回の記事ではグラフ理論のSpanning Tree(全域木)を扱います。 まずそもそもグラフとは？の人はこちらの記事から入られることをお勧めします。 astrostory.hatenablog.com また今回は分かりやすくするために無向グラフを使います。 全域木 全域木はかなり平たくいうと、全ての頂点が辺で結ばれている状態を満たすグラフのことを言います 全域木は元々のグラフの補グラフ(subgraph)になっています。 ちなみに、Theoremで全ての連結グラフは全域木を持つことが保証されています。 最小全域木 最小全域木は重り付グラフの時に、全域木のトータルの重りの和が最小になるグラフで…