共通マトロイド問題

出典: ORWiki

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

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


\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} \,


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

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E5%85%B1%E9%80%9A%E3%83%9E%E3%83%88%E3%83%AD%E3%82%A4%E3%83%89%E5%95%8F%E9%A1%8C" より作成