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

2007年7月12日 (木) 23:41時点における版

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

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

構文解析に失敗 (不明な関数「\tiny」): {\displaystyle \sum_{\tiny\begin{array}{c} i\in X\\ j\in V-X \end{array}}\ w_{ij} \,}

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

@@ 1行目: / 1行目: @@
 '''【さいだいかっともんだい (maximum cut problem)】'''
-無向グラフ$(V,\: E)$において, 各枝$e_{ij}\in E\: (i,j\in V,\: i\ne j)$に非負整数$w_{ij}$が重みとして付与されている. このとき
+無向グラフ<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} \]
+[[スタイル検討]]
-を最大にする$X\subset V$を求める問題. つまり, $V$を2つの部分集合に分割する組合せ(カット)のうち, それらの部分集合間の枝に付与された重みの総和が最大となる分割を求める.
+<!-- 和の記号の下に改行した式を入力 -->
+<math>
+\sum_{\tiny\begin{array}{c} i\in X\\ j\in V-X \end{array}}\ w_{ij}
+\,</math>
+を最大にする<math>X\subset V \,</math>を求める問題. つまり, <math>V \,</math>を2つの部分集合に分割する組合せ(カット)のうち, それらの部分集合間の枝に付与された重みの総和が最大となる分割を求める.