「最大カット問題」の版間の差分
(新しいページ: ''''【さいだいかっともんだい (maximum cut problem)】''' 無向グラフ$(V,\: E)$において, 各枝$e_{ij}\in E\: (i,j\in V,\: i\ne j)$に非負整数$w_{ij}$が...') |
Albeit-Kun (トーク | 投稿記録) |
||
| (4人の利用者による、間の6版が非表示) | |||
| 1行目: | 1行目: | ||
'''【さいだいかっともんだい (maximum cut problem)】''' | '''【さいだいかっともんだい (maximum cut problem)】''' | ||
| − | 無向グラフ | + | 無向グラフ<math>(V, E) \,</math>において, 各枝<math>e_{ij} \in E\ (i,j\in V,\ i\ne j) \,</math>に非負整数<math>w_{ij} \,</math>が重みとして付与されている. このとき |
| − | + | <center> | |
| + | <math> | ||
| + | \sum_{i \in X,\,\, j \in V-X}\ w_{ij} | ||
| + | </math> | ||
| + | </center> | ||
| − | を最大にする | + | |
| + | を最大にする<math>X\subset V \,</math>を求める問題. つまり, <math>V \,</math>を2つの部分集合に分割する組合せ(カット)のうち, それらの部分集合間の枝に付与された重みの総和が最大となる分割を求める. | ||
| + | |||
| + | [[category:近似・知能・感覚的手法|さいだいかっともんだい]] | ||
2008年11月9日 (日) 17:55時点における最新版
【さいだいかっともんだい (maximum cut problem)】
無向グラフにおいて, 各枝構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle e_{ij} \in E\ (i,j\in V,\ i\ne j) \,} に非負整数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle w_{ij} \,} が重みとして付与されている. このとき
構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \sum_{i \in X,\,\, j \in V-X}\ w_{ij} }
を最大にする構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X\subset V \,}
を求める問題. つまり, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V \,}
を2つの部分集合に分割する組合せ(カット)のうち, それらの部分集合間の枝に付与された重みの総和が最大となる分割を求める.