共通マトロイド問題 - 版の履歴

2008年11月7日 (金) 07:11にAlbeit-Kunによる

2008-11-07T07:11:00Z

Orsjwiki: "共通マトロイド問題" を保護しました。 [edit=sysop:move=sysop]

2007-07-19T23:54:53Z

"共通マトロイド問題" を保護しました。 [edit=sysop:move=sysop]

2007年7月17日 (火) 01:43に122.17.2.240による

2007-07-17T01:43:40Z

2007年7月16日 (月) 06:04に122.17.2.240による

2007-07-16T06:04:46Z

2007年7月11日 (水) 15:23に124.144.188.143による

2007-07-11T15:23:05Z

122.17.2.240: 新しいページ: ''''【きょうつうまとろいどもんだい (matroid intersection problem)】''' マトロイド ${\bf M}^+=(N,{\cal I}^+)$ と ${\bf M}^-=(N,{\cal I}^-)$ における共...'

2007-07-11T05:34:15Z

新しいページ: ''''【きょうつうまとろいどもんだい (matroid intersection problem)】''' マトロイド ${\bf M}^+=(N,{\cal I}^+)$ と ${\bf M}^-=(N,{\cal I}^-)$ における共...'

新規ページ

'''【きょうつうまとろいどもんだい (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}
\]

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

← 古い版		2008年11月7日 (金) 07:11時点における版
15行目:		15行目:

	によって特徴付けられる.		によって特徴付けられる.
		+
		+	[[Category:グラフ･ネットワーク\|きょうつうまとろいどもんだい]]

@@ 3行目: / 3行目: @@
 マトロイド <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)の最大最小定理
 <math>
 \begin{array}{l}
@@ 9行目: / 11行目: @@
 \end{array}
 \,</math>
 によって特徴付けられる.

← 古い版		2007年7月16日 (月) 06:04時点における版
1行目:		1行目:
	'''【きょうつうまとろいどもんだい (matroid intersection problem)】'''		'''【きょうつうまとろいどもんだい (matroid intersection problem)】'''
−

	マトロイド <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)の最大最小定理		マトロイド <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)の最大最小定理

← 古い版	2007年7月19日 (木) 23:54時点における版
(相違点なし)

@@ 1行目: / 1行目: @@
 '''【きょうつうまとろいどもんだい (matroid intersection problem)】'''
-\[
+マトロイド <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)の最大最小定理
 \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}
-\]
+\,</math>
 によって特徴付けられる.