共通マトロイド問題
2007年7月11日 (水) 14:34時点における122.17.2.240 (トーク)による版 (新しいページ: ''''【きょうつうまとろいどもんだい (matroid intersection problem)】''' マトロイド ${\bf M}^+=(N,{\cal I}^+)$ と ${\bf M}^-=(N,{\cal I}^-)$ における共...')
【きょうつうまとろいどもんだい (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} \]
によって特徴付けられる.