共通マトロイド問題

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

マトロイド 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathbf{M}^+=(N,\mathcal{I}^+) \,} と $\mathbf {M} ^{-}=(N,{\mathcal {I}}^{-})\,$ における共通独立集合のうちで, 要素数最大のものを求める問題を共通マトロイド問題という. この問題の最適値は, $\mathbf {M} ^{+}\,$ の階数関数 $\rho ^{+}\,$ と 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathbf{M}^- \,} の階数関数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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}}\,$

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