「共通マトロイド問題」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
 
(2人の利用者による、間の2版が非表示)
3行目: 3行目:
 
マトロイド <math>\mathbf{M}^+=(N,\mathcal{I}^+) \,</math> と <math>\mathbf{M}^-=(N,\mathcal{I}^-) \,</math> における共通独立集合のうちで, 要素数最大のものを求める問題を共通マトロイド問題という. この問題の最適値は, <math>\mathbf{M}^+ \,</math> の階数関数 <math>\rho^+ \,</math> と <math>\mathbf{M}^- \,</math> の階数関数 <math>\rho^- \,</math> とを用いたエドモンズ(J. Edmonds)の最大最小定理
 
マトロイド <math>\mathbf{M}^+=(N,\mathcal{I}^+) \,</math> と <math>\mathbf{M}^-=(N,\mathcal{I}^-) \,</math> における共通独立集合のうちで, 要素数最大のものを求める問題を共通マトロイド問題という. この問題の最適値は, <math>\mathbf{M}^+ \,</math> の階数関数 <math>\rho^+ \,</math> と <math>\mathbf{M}^- \,</math> の階数関数 <math>\rho^- \,</math> とを用いたエドモンズ(J. Edmonds)の最大最小定理
  
 +
 +
<center>
 
<math>
 
<math>
 
\begin{array}{l}
 
\begin{array}{l}
9行目: 11行目:
 
\end{array}
 
\end{array}
 
\,</math>
 
\,</math>
 +
</center>
 +
  
 
によって特徴付けられる.
 
によって特徴付けられる.
 +
 +
[[Category:グラフ・ネットワーク|きょうつうまとろいどもんだい]]

2008年11月7日 (金) 16:11時点における最新版

【きょうつうまとろいどもんだい (matroid intersection problem)】

マトロイド における共通独立集合のうちで, 要素数最大のものを求める問題を共通マトロイド問題という. この問題の最適値は, の階数関数 の階数関数 とを用いたエドモンズ(J. Edmonds)の最大最小定理



によって特徴付けられる.