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

提供: 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)】

無向グラフにおいて, 各枝に非負整数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle w_{ij} \,} が重みとして付与されている. このとき


スタイル検討


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

「https://orsj-ml.org/orwiki/wiki/index.php?title=最大カット問題&oldid=5606」から取得