「共通マトロイド問題」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
(新しいページ: ''''【きょうつうまとろいどもんだい (matroid intersection problem)】''' マトロイド ${\bf M}^+=(N,{\cal I}^+)$ と ${\bf M}^-=(N,{\cal I}^-)$ における共...')
 
 
(3人の利用者による、間の4版が非表示)
1行目: 1行目:
 
'''【きょうつうまとろいどもんだい (matroid intersection problem)】'''
 
'''【きょうつうまとろいどもんだい (matroid intersection problem)】'''
  
−
マトロイド ${\bf M}^+=(N,{\cal I}^+)$ と ${\bf M}^-=(N,{\cal I}^-)$ における共通独立集合のうちで, 要素数最大のものを求める問題を共通マトロイド問題という. この問題の最適値は, ${\bf M}^+$ の階数関数 $\rho^+$ と ${\bf M}^-$ の階数関数 $\rho^-$ とを用いたエドモンズ(J. Edmonds)の最大最小定理
+
マトロイド <math>\mathbf{M}^+=(N,\mathcal{I}^+) \,</math> と <math>\mathbf{M}^-=(N,\mathcal{I}^-) \,</math> における共通独立集合のうちで, 要素数最大のものを求める問題を共通マトロイド問題という. この問題の最適値は, <math>\mathbf{M}^+ \,</math> の階数関数 <math>\rho^+ \,</math> と <math>\mathbf{M}^- \,</math> の階数関数 <math>\rho^- \,</math> とを用いたエドモンズ(J. Edmonds)の最大最小定理
  
−
\[
+
 
 +
<center>
 +
<math>
 
\begin{array}{l}
 
\begin{array}{l}
−
  \max\{|I|\mid I\in{\cal I}^+\cap{\cal I}^-\}= \\
+
  \max\{|I|\mid I\in \mathcal{I}^+\cap \mathcal{I}^-\}= \\
−
\hspace*{5mm} \min\{\rho^+(X)+\rho^-(N\backslash X)\mid X\subseteq N\}
+
\ \ \  \min\{\rho^+(X)+\rho^-(N\backslash X)\mid X\subseteq N\}
 
\end{array}
 
\end{array}
−
\]
+
\,</math>
 +
</center>
 +
 
  
 
によって特徴付けられる.
 
によって特徴付けられる.
 +
 +
[[Category:グラフ･ネットワーク|きょうつうまとろいどもんだい]]

2008年11月7日 (金) 16:11時点における最新版

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

マトロイド と における共通独立集合のうちで, 要素数最大のものを求める問題を共通マトロイド問題という. この問題の最適値は, の階数関数 と の階数関数 とを用いたエドモンズ(J. Edmonds)の最大最小定理



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

「https://orsj-ml.org/orwiki/wiki/index.php?title=共通マトロイド問題&oldid=10292」から取得