共通マトロイド問題とは？

用語解説|全文検索

Weblio 辞書 > 学問 > OR事典 > 共通マトロイド問題の意味・解説

OR事典

共通マトロイド問題

読み方：きょうつうまとろいどもんだい
【英】：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} \,$

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

「OR事典」の他の用語

グラフ･ネットワーク：

マトロイドユークリッド巡回セールスマン問題付値マトロイド共通マトロイド問題分枝カット法割当問題劣モジュラシステム

索引トップ用語の索引ランキングカテゴリー

>> 「共通マトロイド問題」を解説文に含む用語の一覧

>> 「共通マトロイド問題」を含む用語の索引

共通マトロイド問題のページへのリンク

「共通マトロイド問題」の関連用語

劣モジュラフロー問題

OR事典

74% |||||

マトロイド

OR事典

36% |||||

共通マトロイド問題のお隣キーワード

共通マトロイド問題

検索ランキング

▼TOP10

▼11～20

▼21～30

1		沓名環希
2		遡及
3		リーガル・ハイ
4		出不精
5		捗る
6		TPP
7		クルーゾン症候群
8		福利厚生
9		ピーター・カール・ファベルジェ
10		功罪