提供されたテキストに基づき、最小スパニングツリーは何を最適化するのか？
最小スパニングツリー（MST）または最小重量スパニングツリーとは、連結されたエッジ重み付き無向グラフのエッジの部分集合で、すべての頂点をサイクルなしで、可能な限り最小のエッジ重量の合計で連結するものなのだ。つまり、エッジの重みの合計が可能な限り小さいスパニングツリーなのだ。より一般的には、任意のエッジ重み付き無向グラフ（必ずしも連結されている必要はない）は、その連結成分の最小スパニングツリーの組合わせである最小スパニングフォレストを有する。

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