「共通マトロイド問題」の版間の差分
ナビゲーションに移動
検索に移動
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> | ||
+ | |||
によって特徴付けられる. | によって特徴付けられる. |
2007年7月17日 (火) 10:43時点における版
【きょうつうまとろいどもんだい (matroid intersection problem)】
マトロイド と における共通独立集合のうちで, 要素数最大のものを求める問題を共通マトロイド問題という. この問題の最適値は, の階数関数 と の階数関数 とを用いたエドモンズ(J. Edmonds)の最大最小定理
によって特徴付けられる.