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

2008年11月9日 (日) 17:55時点における最新版

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

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

$\sum _{i\in X,\,\,j\in V-X}\ w_{ij}$

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

@@ 2行目: / 2行目: @@
 無向グラフ<math>(V, E) \,</math>において, 各枝<math>e_{ij} \in E\ (i,j\in V,\ i\ne j) \,</math>に非負整数<math>w_{ij} \,</math>が重みとして付与されている. このとき
 <center>
 <math>
-\sum_{\begin{array}{c} i\in X \\ j\in V-X \end{array}} \ w_{ij}
+ \sum_{i \in X,\,\, j \in V-X}\ w_{ij}
-\,</math>
+</math>
-[[スタイル検討#最大カット問題 (a-f-02-04f)|スタイル検討]]
 </center>
 を最大にする<math>X\subset V \,</math>を求める問題. つまり, <math>V \,</math>を2つの部分集合に分割する組合せ(カット)のうち, それらの部分集合間の枝に付与された重みの総和が最大となる分割を求める.
+[[category:近似・知能・感覚的手法|さいだいかっともんだい]]