最大カット問題とは? わかりやすく解説

Weblio 辞書 > 学問 > OR事典 > 最大カット問題の意味・解説 

最大カット問題

読み方さいだいかっともんだい
【英】:maximum cut problem

無向グラフ(V, E) \,において, 各e_{ij} \in E\ (i,j\in V,\ i\ne j) \,非負整数w_{ij} \,重みとして付与されている. このとき


 \sum_{i \in X,\,\, j \in V-X}\ w_{ij}


最大にするX\subset V \,求め問題. つまり, V \,2つ部分集合分割する組合せ(カット)のうち, それらの部分集合間の付与され重み総和最大となる分割求める.




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

辞書ショートカット

すべての辞書の索引

「最大カット問題」の関連用語

最大カット問題のお隣キーワード
検索ランキング

   

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



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

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2025 (社)日本オペレーションズ・リサーチ学会 All rights reserved.

©2025 GRAS Group, Inc.RSS