最大カット問題 - 版の履歴

2008年11月9日 (日) 08:55にAlbeit-Kunによる

2008-11-09T08:55:30Z

2007年9月7日 (金) 14:48にSakasegawaによる

2007-09-07T14:48:04Z

2007年8月6日 (月) 02:35にOrsjwikiによる

2007-08-06T02:35:23Z

Orsjwiki: "最大カット問題" を保護しました。 [edit=sysop:move=sysop]

2007-07-20T01:22:59Z

"最大カット問題" を保護しました。 [edit=sysop:move=sysop]

2007年7月18日 (水) 05:34に122.17.2.240による

2007-07-18T05:34:22Z

2007年7月17日 (火) 04:30に122.17.2.240による

2007-07-17T04:30:20Z

2007年7月12日 (木) 14:41に124.144.188.143による

2007-07-12T14:41:48Z

122.17.2.240: 新しいページ: ''''【さいだいかっともんだい (maximum cut problem)】''' 無向グラフ$(V,\: E)$において, 各枝$e_{ij}\in E\: (i,j\in V,\: i\ne j)$に非負整数$w_{ij}$が...'

2007-07-12T06:16:17Z

新しいページ: ''''【さいだいかっともんだい (maximum cut problem)】''' 無向グラフ$(V,\: E)$において, 各枝$e_{ij}\in E\: (i,j\in V,\: i\ne j)$に非負整数$w_{ij}$が...'

新規ページ

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

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

\[ \sum_{\tiny \begin{array}{c} i\in X\\ j\in V-X \end{array}}\: w_{ij} \]

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

← 古い版		2008年11月9日 (日) 08:55時点における版
11行目:		11行目:

	を最大にする<math>X\subset V \,</math>を求める問題. つまり, <math>V \,</math>を2つの部分集合に分割する組合せ(カット)のうち, それらの部分集合間の枝に付与された重みの総和が最大となる分割を求める.		を最大にする<math>X\subset V \,</math>を求める問題. つまり, <math>V \,</math>を2つの部分集合に分割する組合せ(カット)のうち, それらの部分集合間の枝に付与された重みの総和が最大となる分割を求める.
		+
		+	[[category:近似・知能・感覚的手法\|さいだいかっともんだい]]

@@ 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>
 </center>
 を最大にする<math>X\subset V \,</math>を求める問題. つまり, <math>V \,</math>を2つの部分集合に分割する組合せ(カット)のうち, それらの部分集合間の枝に付与された重みの総和が最大となる分割を求める.

@@ 14行目: / 14行目: @@
 \sum_{\begin{array}{c} i\in X \\ j\in V-X \end{array}} \ w_{ij}
 \,</math>
 </center>
 を最大にする<math>X\subset V \,</math>を求める問題. つまり, <math>V \,</math>を2つの部分集合に分割する組合せ(カット)のうち, それらの部分集合間の枝に付与された重みの総和が最大となる分割を求める.

← 古い版		2007年7月18日 (水) 05:34時点における版
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}
		+	\]
		+	-->

@@ 3行目: / 3行目: @@
 無向グラフ<math>(V, E) \,</math>において, 各枝<math>e_{ij} \in E\ (i,j\in V,\ i\ne j) \,</math>に非負整数<math>w_{ij} \,</math>が重みとして付与されている. このとき
 <math>
-\sum_{\tiny\begin{array}{c} i\in X\\ j\in V-X \end{array}}\ w_{ij}
+\sum_{\begin{array}{c} i\in X \\ j\in V-X \end{array}} \ w_{ij}
 \,</math>
 を最大にする<math>X\subset V \,</math>を求める問題. つまり, <math>V \,</math>を2つの部分集合に分割する組合せ(カット)のうち, それらの部分集合間の枝に付与された重みの総和が最大となる分割を求める.

← 古い版	2007年7月20日 (金) 01:22時点における版
(相違点なし)

@@ 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つの部分集合に分割する組合せ(カット)のうち, それらの部分集合間の枝に付与された重みの総和が最大となる分割を求める.
+<!-- 和の記号の下に改行した式を入力 -->