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

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

マトロイド ${\bf M}^+=(N,{\cal I}^+)$ と ${\bf M}^-=(N,{\cal I}^-)$ における共通独立集合のうちで, 要素数最大のものを求める問題を共通マトロイド問題という. この問題の最適値は, ${\bf M}^+$ の階数関数 $\rho^+$ と ${\bf M}^-$ の階数関数 $\rho^-$ とを用いたエドモンズ(J. Edmonds)の最大最小定理

\[
\begin{array}{l}
 \max\{|I|\mid I\in{\cal I}^+\cap{\cal I}^-\}= \\
\hspace*{5mm} \min\{\rho^+(X)+\rho^-(N\backslash X)\mid X\subseteq N\}
\end{array}
\]

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