「最大カット問題」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
2行目: 2行目:
  
 
無向グラフ<math>(V, E) \,</math>において, 各枝<math>e_{ij} \in E\ (i,j\in V,\ i\ne j) \,</math>に非負整数<math>w_{ij} \,</math>が重みとして付与されている. このとき
 
無向グラフ<math>(V, E) \,</math>において, 各枝<math>e_{ij} \in E\ (i,j\in V,\ i\ne j) \,</math>に非負整数<math>w_{ij} \,</math>が重みとして付与されている. このとき
 +
 +
<!--
 +
\[
 +
\sum_{\tiny \begin{array}{c} i\in X\\ j\in V-X \end{array}}\: w_{ij}
 +
\]
 +
-->
  
  

2007年7月18日 (水) 14:34時点における版

【さいだいかっともんだい (maximum cut problem)】

無向グラフにおいて, 各枝に非負整数が重みとして付与されている. このとき


スタイル検討


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