共通マトロイド問題

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

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