最小全域木電卓

最小全域木電卓へようこそ。このツールは、クラスカル法またはプリム法を使用して重み付きグラフのMSTを計算するインタラクティブなツールです。グラフ理論の学習、ネットワークインフラの設計、またはリソース配分の最適化など、この電卓は組合せ最適化における2つの基本的なアルゴリズムを視覚的かつステップバイステップで探索する手段を提供します。

最小全域木（MST）とは何ですか？

連結された無向重み付きグラフの最小全域木とは、以下の条件を満たすエッジの部分集合です：

• すべての頂点を接続している（全域）
• サイクルを含まない（木）
• 可能な限り最小の合計エッジ重みを持つ

V個の頂点を持つグラフの場合、MSTは常にちょうど V - 1 本のエッジを持ちます。グラフが非連結の場合、結果は各連結成分ごとのMSTの集合である最小全域森となります。

クラスカル法

クラスカル法は、エッジを重みの昇順で処理することでMSTを構築するエッジベースの貪欲アルゴリズムです。Union-Find（素集合データ構造）を使用して、効率的にサイクルを検出します。

クラスカル法の擬似コード

プリム法

プリム法は、開始頂点からMSTを成長させる頂点ベースの貪欲アルゴリズムです。各ステップで、木の中にある頂点と木の外にある頂点を結ぶ最も安価なエッジを追加します。

プリム法の擬似コード

クラスカル法 vs プリム法：どちらを使うべきか？

この電卓の使い方

1. グラフのエッジを定義： ノード1, ノード2, 重み の形式でエッジを1行に1つずつ入力します。MSTは無向グラフで動作するため、各エッジは双方向として機能します。
2. アルゴリズムを選択： 疎なグラフにはクラスカル法、密なグラフにはプリム法を選択します。どちらも最適なMSTを生成します。
3. 開始ノードを設定（プリム法のみ）： オプションでプリム法の開始地点を指定します。これはエッジの選択順序に影響しますが、MSTの合計重みには影響しません。
4. MSTを計算： 「MSTを見つける」をクリックしてアルゴリズムを実行します。インタラクティブな可視化、エッジテーブル、ステップバイステップの追跡を探索します。
5. ステップを進める： 「次へ」/「前へ」ボタンを使用して、キャンバス上のリアルタイムハイライトと共にアルゴリズムの実行をステップごとに確認します。

結果の理解

MSTエッジテーブル

MSTに選択されたすべてのエッジを、追加された順序、個別の重み、およびMSTの総重みと共に表示します。

グラフ可視化

インタラクティブなキャンバスに、カラーコード化された要素でグラフが表示されます：

• 緑色のノードとエッジ = MSTの一部
• オレンジ色のハイライト = 現在調査中
• グレーの要素 = まだMSTの一部ではない

ステップバイステップ追跡

アルゴリズムの各決定（どのエッジが調査されたか、採用または拒否されたか、その理由、およびMST構築の現在の状態）を表示します。

MSTの現実世界での応用

ネットワーク設計

最も古典的な応用例です。ノード（都市、サーバー、電気機器）を最小限の合計ケーブル、光ファイバー、またはパイプの長さで接続する場合、MSTが最適な解決策を提供します。通信会社はインフラコストを最小限に抑えるためにMSTベースのアルゴリズムを使用しています。

クラスタ分析

機械学習やデータサイエンスにおいて、MSTベースのクラスタリング（単連結法など）は、MSTから最も長いエッジを削除することでデータポイントをグループ化します。これにより、グループ数を事前に指定することなく、自然なクラスターを生成できます。

画像セグメンテーション

コンピュータビジョンのアルゴリズムは、画像を意味のある領域に分割するためにMSTを使用します。ピクセルをノード、エッジの重みを色や強度の差として扱い、MSTのエッジを切断することで異なるオブジェクトを分離します。

近似アルゴリズム

MSTは、距離空間における巡回セールスマン問題（TSP）の2倍近似を提供します。MSTの重みは最適なTSPツアーの下限であり、MSTのエッジを2倍にすることで最適解の2倍以内のツアーが得られます。

回路設計

VLSIチップ設計では、回路基板上のコンポーネントを接続する総配線長を最小化するために（シュタイナー木変種を介して）MSTが使用され、信号遅延と製造コストを削減します。

MSTの主な性質

• カットの性質： グラフの任意のカットにおいて、そのカットを横切る最小重みのエッジはMSTに含まれます。
• サイクルの性質： グラフ内の任意のサイクルにおいて、そのサイクル内で最大重みを持つエッジはMSTに含まれません（重みが一意であると仮定）。
• 一意性： すべてのエッジの重みが異なる場合、MSTは一意に決まります。重みが重複している場合、同じ合計重みを持つ複数の有効なMSTが存在する可能性があります。
• 部分グラフ： MSTは V-1 本のエッジを持ち、サイクルを持たない部分グラフです。

よくある質問

最小全域木（MST）とは何ですか？

最小全域木とは、連結された無向重み付きグラフにおいて、すべての頂点を最小の合計エッジ重みで、サイクルを作らずに接続するエッジの部分集合のことです。V個の頂点を持つグラフのMSTは、ちょうど V-1 本のエッジを持ちます。

クラスカル法とプリム法の違いは何ですか？

クラスカル法はエッジベースのアルゴリズムです。すべてのエッジを重み順にソートし、Union-Findデータ構造を使用してサイクルを作成しないエッジを貪欲に追加していきます。プリム法は頂点ベースのアルゴリズムです。優先度付きキューを使用して、常に既存の木と新しい頂点を結ぶ最も安価なエッジを追加することで、開始ノードからMSTを成長させます。どちらも最適なMSTを生成しますが、エッジの選択順序が異なる場合があります。

クラスカル法とプリム法のどちらを使うべきですか？

クラスカル法は一般的に疎なグラフ（ノードに対してエッジが少ないグラフ）に適しており、時間計算量は O(E log E) です。プリム法は、バイナリヒープを使用した場合、時間計算量 O(E log V) で密なグラフに適しています。非常に密なグラフの場合、プリム法にフィボナッチヒープを組み合わせることで O(E + V log V) を達成します。

1つのグラフに複数の有効なMSTが存在することはありますか？

はい、同じ重みのエッジが存在する場合、1つのグラフに複数の有効なMSTが存在することがあります。異なるMSTは合計重みは同じですが、含まれるエッジが異なる場合があります。クラスカル法とプリム法は同じグラフに対して異なるMSTを生成する可能性がありますが、どちらも同じ最小合計重みを持ちます。

MSTの現実世界での応用例は何ですか？

MSTは、ネットワーク設計（ケーブルや光ファイバーの長さの最小化）、回路基板のレイアウト、クラスタ分析、画像セグメンテーション、系統樹の構築、巡回セールスマン問題（TSP）の近似、および最小コストでの道路・パイプライン・電気ネットワークの構築に使用されます。

MSTは非連結グラフでも機能しますか？

真のMSTには連結グラフが必要です。グラフが非連結の場合、アルゴリズムは各連結成分ごとのMSTの集合である「最小全域森」を生成します。この電卓は、グラフが完全に連結されていない場合にその旨を表示します。

参考資料

• 最小全域木 - Wikipedia
• クラスカル法 - Wikipedia
• プリム法 - Wikipedia