最小全域木問題とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 最小全域木問題の意味・解説 

全域木

(最小全域木問題 から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/03/10 01:42 UTC 版)

4×4のグリッドグラフにおける全域木の一例
8x8 グリッド グラフ上の 3 つの例

グラフ理論において、グラフ全域木(ぜんいきぎ、: Spanning tree)、極大木(きょくだいき)、スパニング木スパニングツリーとは、全域部分グラフ(そのグラフの全頂点を含む部分グラフ)のうち、木(連結閉路を持たないグラフ)であるものをいう。全域木は連結グラフに必ず存在し、連結でないグラフには存在しない。

最小全域木

各辺に重み(コスト)がある場合、最小の総和コストで構成される全域木を最小全域木という。




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

辞書ショートカット

すべての辞書の索引

「最小全域木問題」の関連用語






6
10% |||||


8
6% |||||



最小全域木問題のお隣キーワード
検索ランキング

   

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



最小全域木問題のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの全域木 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS