重み付きグラフ

最小全域木(MST)に入る前に、重み付きグラフとは何かを理解しましょう。

  • 重み付きグラフとは、各辺に重み(またはコスト)を関連付けたグラフモデルです。つまり、各辺 e には数値ラベルが関連付けられており、これを w(e) と表記します。

ここでは、重み付きグラフに関する3つの一般的な問題を解くためのアルゴリズムを見ていきます。

  1. MST
  2. 最短経路
  3. ネットワークフロー

最小全域木

  • MSTの入力:頂点(またはノード)𝑉 と辺 𝐸 からなり、辺に重みを持つ、重み付き連結グラフ 𝐺 = (𝑉, 𝐸)。
  • 出力:𝐺 の最小全域木(MST)𝑇 = (𝑉, 𝐸𝑇)。すなわち、𝑇 は 𝐺 の連結な全域部分グラフ(𝐸𝑇 ⊆ 𝐸)であり、𝑇 は閉路を持たず、𝑇 の総重みが最小化されます。

MSTの実生活における応用例には、以下が含まれます。

  1. クラスター分析。

  2. 最大ボトルネック経路。

  3. リアルタイムの顔認証。

  4. 誤り訂正のためのLDPC符号。

  5. Rényiエントロピーを用いた画像レジストレーション。

  6. 衛星画像や航空画像における道路網の検出。

  7. タンパク質中のアミノ酸配列決定におけるデータストレージの削減。

  8. 乱流中の粒子相互作用の局所性のモデル化。

  9. ネットワーク内の閉路を避けるためのイーサネットブリッジングの自動設定プロトコル。

  10. NP困難問題(例:TSP、シュタイナー木)に対する近似アルゴリズム。

  11. ネットワーク設計(通信、電気、水力、コンピュータ、道路)。

    参考文献:http://www.ics.uci.edu/~eppstein/gina/mst.html

グラフ G のMSTをどのように見つけるのでしょうか。

それには2つの方法があります。

  1. 総当たり法を用いてすべての可能な全域木を生成し、最も軽い W(G) を見つけることもできますが、総当たり法のビッグOは非常に大きくなり得るため、この方法は現実的ではありません。
  2. 代わりに、Prim法やKruskal法のような貪欲アルゴリズムを使用できます。

Prim法:

  • 選択した単一の頂点で木を初期化します。
  • まだ木に含まれていない最も軽い隣接辺を見つけて木に接続することで木を成長させ、すべての頂点が木に含まれるまで繰り返します。

Kruskal法:

  • すべてのノードからなる森を初期化します。
  • (未選択の)最小重みの辺を選び、それが森の2つの異なる木を接続する場合は選択し、そうでなければ破棄します。これを繰り返します。

(続く…)