共通マトロイド問題のソースを表示

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


マトロイド <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>
\begin{array}{l}
 \max\{|I|\mid I\in \mathcal{I}^+\cap \mathcal{I}^-\}= \\
\ \ \  \min\{\rho^+(X)+\rho^-(N\backslash X)\mid X\subseteq N\}
\end{array}
\,</math>

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