minimum spanning tree problemとは? わかりやすく解説

Weblio 辞書 > 学問 > OR事典 > minimum spanning tree problemの意味・解説 

最小木問題

読み方さいしょうきもんだい
【英】:minimum spanning tree problem

概要

重み与えられた(無向)グラフにおいて, そのグラフ上に存在する張木(全域木)の中で重み総和最小になるものを見出す組合せ最適化問題. それ自身多く応用例をもつが, より複雑な問題の子問題として利用されることも多い. クラスカル法プリム法といった貪欲アルゴリズムにより多項式時間で解くことが可能である.

詳説

 無向グラフG=(V,E)\, の各e\in E\, 実数重みw(e)\, 与えられているとする. グラフG\, 上において全点V\, 点集合とし木になっている部分グラフを全張木あるいは全域木(spanning tree)と呼ぶ. グラフG\, 上の張木T=(V,E_T)\, 重みは, T\, 上の重み総和\textstyle {\sum}_{e\in E_T}w(e)\, 定める. グラフG\, 上において重み最小の全張木最小木 (minimum spaninng tree) といい, 最小木を求め問題最小木問題 (minimum spaninng tree problem) という.

 最小木問題は, クラスター分析ネットワーク・デザインなどの分野利用されているが, より複雑な問題の子問題として活用されることの多い基本的な問題である([2]).

 グラフ上の問題として基本的である最小木問題がいつ頃から考えられたのかは明らかではない. 分かっている範囲では, 1926年{Bor\breve{u}vka}\, が,またそれとは独立に, 1930年にJarníkがそれぞれ最小木問題を定式化しそのアルゴリズム発表している(最小木問題に関する歴史は [4] が詳しい). その後,最小木問題に対す基本的なアルゴリズムとしてクラスカル法(Kruskal's algorithm) とプリム法(Prim's algorithm) などが提案された. 現在までに提案されている主な効率的なアルゴリズムはこれらの二つアルゴリズムどちらかを基にデータ構造工夫することによって構築されている([1, 8]).

 クラスカル法は, 1956年に J. B. Kruskal [6] により, またそれとは独立1957年H. LobermanとA. Weinbergerにより提案され多項式時間アルゴリズムである. アルゴリズムの概要以下のとおりである. クラスカル法では,まず, のない点集合V\, のみからなるF=(V,\emptyset\, )を考え次に, 閉路発生しない限り重み小さい順に一本ずつF\, 加えるという操作繰り返す. F\, が全張木になった時点繰り返し終了し, 得られF\, 一つ最小木である.

 一方, プリム法は, 1957年, R. C. Prim [7] によって提案され多項式時間アルゴリズムである(Jarník法と同様). プリム法では, まず, 任意の1点v\, のみからなるT=(\{v\},\emptyset)\, 考え, 次に, グラフG\, において現在のT\, 点集合と木以外の点集合接続する集合の中から重みが最も小さとその端点新たにT\, 加えるという操作繰り返す. 木T\, グラフG\, の全張木になった時点繰り返し終了し, 得られT\, 一つ最小木である.

 どちらのアルゴリズム候補集合から最小重み選びながら最小木を構成していくという点から貪欲アルゴリズム (greedy algorithm) という種類分類されるアルゴリズムである. クラスカル法プリム法違い候補集合構成法にある. プリム法与えられグラフの点と接続関係強く依存したアルゴリズムであって, そのアルゴリズム構造最短路問題ダイクストラ法と全く同じである.一方, クラスカル法は,グラフマトロイド構造にのみ依存したアルゴリズムであって, マトロイド最小問題対す貪欲アルゴリズムへと一般化されている.逆に, このような貪欲アルゴリズム最適解見出す問題マトロイド構造を持つことも知られている.

 クラスカル法プリム法のような貪欲アルゴリズム考え方用いたアルゴリズム組合せ最適化分野において数多く見受けられる. この貪欲アルゴリズム考え方解ける抽象的な組合せ最適化問題クラスマトロイド最適化問題呼ばれ, そのクラスが持つ性質マトロイド理論として組合せ最適化における多く有用な知見提供している[8].

 最小木問題は無向グラフ上において定義され問題であるが, 向き依存した有向グラフ上の問題考えられる. 有向グラフ上での全張木は,根と呼ばれる1点から他の点への有向道がその全張木上に存在するとき有向木 (directed tree) あるいは根つき木 (rooted tree) と呼ばれる. 重み総和最小となる有向木求め問題無向グラフ上の最小木を求めるほど簡単ではないが, 多項式時間アルゴリズム存在する[8].

 最小木問題は重み最小の全張木求め問題であるが, 「全張木」を「ある与えられ点集合S \subseteq V\, 連結化する木」と変更してみる. この変更され問題シュタイナー最小木問題 (または, シュタイナー木問題) と呼び, その最適解シュタイナー最小木と呼ぶ. 与えられ無向グラフG\, の各重みがすべて正である時, シュタイナー木点集合S\, 属する点となり, 内点点集合S\, 属さない点(シュタイナー点呼ばれる)をいくつか含む.

 シュタイナー最小木問題は, S=V\, 時に最小木問題と同一になり, また, |S|=2\, かつw(e)>0\, の時は最短路問題同一になるので, これらの基本的な問題一般化として捉えることができる. 最小木問題や最短路問題には多項式時間アルゴリズム存在するが, シュタイナー木問題NP困難であることが示され, 多項式時間アルゴリズム存在絶望視されている. 問題を解く困難性平面グラフ限定した場合でも, また各重み等し場合でも変わらない [3].

 問題を解く困難性はあるが, シュタイナー最小木問題通信ネットワーク, 電力供給網において顧客を結ぶネットワーク上の問題施設配置問題などの子問題として多く応用例を有する. その必要性からシュタイナー最小木問題に対して多く近似解法提案されてきている [5].



参考文献

[1] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, New Jersey, 1993.

[2] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, "Applications of Network Optimization," in Network Models, M. O. Ball, T. L. Magnanti, C. L. Monma and G. L. Nemhauser, eds., North-Holland, 1995.

[3] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco,1979.

[4] R. L. Graham and P. Hell, "On the history of minimum spanning tree problem," Annals of the History of Computing, 7 (1985), 43-57.

[5] F. W. Hwang, D. S. Richards and P. Winter, The Steiner Tree problem, Annals of Discrete Mathematics 53, North-Holland, Amsterdam,1992.

[6] J. B. Kruskal, "On the shortest spanning tree of a graph and the traveling salesman problem," Proceedings of the American Mathematical Society, 7 (1956), 48-50.

[7] R. C. Prim, "Shortest connection networks and some generalizations," Bell System Technical Journal, 36 (1957), 1389-1401.

[8] 久保田村松井 (編) 『応用数理計画ハンドブック』,朝倉書店,2002.


「minimum spanning tree problem」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「minimum spanning tree problem」の関連用語

minimum spanning tree problemのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



minimum spanning tree problemのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2025 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS