与えられた文章に基づいて、最小スパニングツリーは何を最適化するのか？
最小スパニングツリー(MST)または最小重量スパニングツリーとは、連結されたエッジ重み付き無向グラフのエッジの部分集合であり、すべての頂点をサイクルなしで、可能な限り最小のエッジ重みの合計で連結する。つまり、辺の重みの合計が可能な限り小さいスパニングツリーである。より一般的には、どんなエッジ重み付き無向グラフ（必ずしも連結でなくてもよい）も、その連結成分の最小スパニング木の和である最小スパニング林を持つ。

最小スパニングツリーには多くの使用例がある。例えば、電気通信会社が新しい地域にケーブルを敷設しようとする場合である。ある経路（道路など）に沿ってしかケーブルを敷設できないという制約がある場合、その経路で結ばれた点（家など）を含むグラフが存在することになる。いくつかの経路は、より長く、より深くケーブルを埋設する必要があるため、より高価であるかもしれない。エッジの長さは、三角形の不等式のような通常の幾何学のルールに従う必要はない。そのグラフのスパニングツリーは、サイクルを持たず、すべての家をつなぐパスの部分集合である。可能なスパニングツリーはいくつかあるかもしれない。最小スパニングツリーとは、総コストが最小のもので、ケーブルを敷設するための最もコストのかからない経路を表す。
最小スパニングツリーは、エッジのすべての重みの和を最小にする方法でグラフを最適化する。