「共通マトロイド問題」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【きょうつうまとろいどもんだい (matroid intersection problem)】''' マトロイド ${\bf M}^+=(N,{\cal I}^+)$ と ${\bf M}^-=(N,{\cal I}^-)$ における共...') |
(相違点なし)
|
2007年7月11日 (水) 14:34時点における版
【きょうつうまとろいどもんだい (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} \]
によって特徴付けられる.