共通マトロイド問題とは? わかりやすく解説

Weblio 辞書 > 学問 > 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}
\,


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




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

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

共通マトロイド問題のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



共通マトロイド問題のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2025 (社)日本オペレーションズ・リサーチ学会 All rights reserved.

©2025 GRAS Group, Inc.RSS