マトロイド - 版の履歴

2008年8月6日 (水) 03:30にImahoriによる

2008-08-06T03:30:36Z

Imahori: 基礎編と用語編のマージ

2008-03-13T14:10:27Z

基礎編と用語編のマージ

2007年8月8日 (水) 12:01にKanda.kによる

2007-08-08T12:01:37Z

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

2007-07-20T01:58:02Z

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

2007年7月16日 (月) 10:24に122.17.2.240による

2007-07-16T10:24:45Z

122.17.2.240: 新しいページ: '【まとろいど (matroid)】マトロイドは, ベクトル集合の一次独立性・従属性といった概念を組合せ論的に抽象化することによって得...'

2007-07-13T03:09:26Z

新しいページ: '【まとろいど (matroid)】マトロイドは, ベクトル集合の一次独立性・従属性といった概念を組合せ論的に抽象化することによって得...'

新規ページ

【まとろいど (matroid)】

マトロイドは, ベクトル集合の一次独立性・従属性といった概念を組合せ論的に抽象化することによって得られる公理系を用いて, 1935年にホイットニー(H. Whitney)によって導入された. 1950年代までのタット(W.T. Tutte)らによるマトロイドの理論研究の後, 1960年代にエドモンズ(J. Edmonds)によって数理計画法における重要性が指摘されて以来, マトロイドは, 効率的に解くことのできる離散最適化問題を把握する枠組として中心的な役割を担っている.

@@ 2行目: / 2行目: @@
 === 概要 ===
-マトロイドは, ベクトル集合の一次独立性・従属性といった概念を組合せ論的に抽象化することによって得られる公理系を用いて, 1935年にホイットニー(H. Whitney)によって導入された. 1950年代までのタット(W.T. Tutte)らによるマトロイドの理論研究の後, 1960年代にエドモンズ(J. Edmonds)によって数理計画法における重要性が指摘されて以来, マトロイドは, 効率的に解くことのできる離散最適化問題を把握する枠組として中心的な役割を担っている.
+マトロイドとは, ベクトル集合の一次独立性・従属性といった概念を組合せ論的に抽象化することによって得られる公理系を満たすものである．
 === 詳説 ===
@@ 47行目: / 50行目: @@
 特に, (R3) は <math>\rho\, </math> が[[劣モジュラ関数]] (submodular function) であることを示している.
-　ここでは, (I0)-(I2) によってマトロイドを定義したが, (B0)-(B1) を満たす基族 <math>\mathcal{B}\, </math> からマトロイドを定義することもできる. この場合, 独立集合は基の部分集合として定義される. 同様に, (R0)-(R3) を満たす階数関数によってマトロイドを定義することもできる.  この場合, 独立集合族は <math>\mathcal I=\{I\mid \rho(I)=|I|\}\, </math> によって定められる.
+　ここでは, (I0)-(I2) によってマトロイドを定義したが, (B0)-(B1) を満たす基族 <math>\mathcal{B}\, </math> からマトロイドを定義することもできる. この場合, 独立集合は基の部分集合として定義される. 同様に, (R0)-(R3) を満たす階数関数によってマトロイドを定義することもできる.  この場合, 独立集合族は <math>\mathcal I=\{I\subseteq N \mid \rho(I)=|I|\}\, </math> によって定められる.
 　離散最適化に現れるマトロイドの代表的な例を以下に挙げる.
-'''グラフ的マトロイド'''　点集合 <math>V\, </math>, 枝集合 <math>E\, </math> を持つ無向グラフ <math>G=(V,E)\, </math> を考える. 枝集合の部分集合のうち, 閉路を含まないものの全体を <math>\mathcal I\, </math> とすると, <math>(E,\mathcal I)\, </math> は (I0)-(I2) を満たし, マトロイドになる. このようにして得られるマトロイドをグラフ的マトロイドと呼ぶ.
+'''グラフ的マトロイド'''　(graphic matroid) 点集合 <math>V\, </math>, 枝集合 <math>E\, </math> を持つ無向グラフ <math>G=(V,E)\, </math> を考える. 枝集合の部分集合のうち, 閉路を含まないものの全体を <math>\mathcal I\, </math> とすると, <math>(E,\mathcal I)\, </math> は (I0)-(I2) を満たし, マトロイドになる. このようにして得られるマトロイドをグラフ的マトロイドと呼ぶ.
-'''横断マトロイド'''　点集合 <math>U\, </math>, <math>V\, </math>, 枝集合 <math>E\, </math> からなる2部グラフ <math>H=(U,V;E)\, </math> を考える. 枝部分集合 <math>M\subseteq E\, </math> で端点を共有しないものを <math>H\, </math> のマッチングという. 点集合 <math>U\, </math> の部分集合で, <math>H\, </math> のマッチングの <math>U\, </math> における端点集合となり得るものの全体を <math>\mathcal I\, </math> とする. このとき, <math>(U,\mathcal I)\, </math> は (I0)-(I2) を満たし, マトロイドになる. このようにして得られるマトロイド <math>(U,\mathcal I)\, </math> を横断マトロイドと呼ぶ.
+'''横断マトロイド'''　(transversal matroid) 点集合 <math>U\, </math>, <math>V\, </math>, 枝集合 <math>E\, </math> からなる2部グラフ <math>H=(U,V;E)\, </math> を考える. 枝部分集合 <math>M\subseteq E\, </math> で端点を共有しないものを <math>H\, </math> のマッチングという. 点集合 <math>U\, </math> の部分集合で, <math>H\, </math> のマッチングの <math>U\, </math> における端点集合となり得るものの全体を <math>\mathcal I\, </math> とする. このとき, <math>(U,\mathcal I)\, </math> は (I0)-(I2) を満たし, マトロイドになる. このようにして得られるマトロイド <math>(U,\mathcal I)\, </math> を横断マトロイドと呼ぶ.
 　マトロイド <math>\mathbf{M}=(N,\mathcal I)\, </math> の各要素 <math>i \in  N\, </math> に重み <math>w(i)\, </math> が与えられたとき, 以下の様な[[貪欲アルゴリズム]]　(greedy algorithm)　を適用して最終的に得られる <math>I\, </math> が, 重み最小の基, すなわち, <math>\textstyle w(B)=\sum\{w(i)\mid i \in  B\}\, </math> を最小にする基 <math>B \in \mathcal{B}\, </math> となる.
@@ 65行目: / 68行目: @@
-全く同様のアルゴリズムによって, 重みの最大化も可能である.
+全く同様のアルゴリズムによって, 重み最大の基を求めることもできる．
 　離散最適化におけるマトロイドの重要性は, 貪欲アルゴリズムのみならず, [[共通マトロイド問題]] (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> を用いて,
@@ 71行目: / 74行目: @@
 <center>
-<math>\max\{|I|\mid I \in \mathcal I^+\cap\mathcal I^-\}=\min\{\rho^+(X)+\rho^-(N-X)\mid X\subseteq N\}\, </math>
+<math>\max\{|I|\mid I \in \mathcal I^+\cap\mathcal I^-\}=\min\{\rho^+(X)+\rho^-(N\setminus X)\mid X\subseteq N\}\, </math>
 </center>
@@ 77行目: / 80行目: @@
 と特徴付けられる [1] . 共通マトロイド問題は, 回路理論やシステム解析においても本質的な役割を果たしている [2, 3, 5] .
-　マトロイドが, 行列における一次独立性を抽象化して得られたのに対し, 対称行列や歪対称行列の正則主小行列の組合せ的な性質を抽象化した[[デルタマトロイド]] (delta-matroid) が提案された. デルタマトロイドは, マトロイドの一般化であり, 貪欲アルゴリズムが適用可能であると同時に, 一般グラフ上のマッチングの端点集合族をも包含する枠組として注目されている.
+　マトロイドが, 行列における一次独立性を抽象化して得られたのに対し, 対称行列や歪対称行列の正則主小行列の組合せ的な性質を抽象化した概念として，[[デルタマトロイド]] (delta-matroid) が提案された. デルタマトロイドは, マトロイドの一般化であり, 貪欲アルゴリズムが適用可能であると同時に, 一般グラフ上のマッチングの端点集合族をも包含する枠組として注目されている.
 　また, 多項式行列の小行列式の次数の抽象化として[[付値マトロイド]] (valuated matroid) が提案された. 付値マトロイドの研究は, 劣モジュラ関数の凸性に関する理論と結び付いて, 離散凸解析と呼ばれる分野に発展している.
@@ 90行目: / 93行目: @@
 [2] 室田一雄, 「マトロイドとシステム解析」, 藤重悟 編『離散構造とアルゴリズムⅠ』, 近代科学社, 第2章，57-109, 1992.
-[3] K. Murota, ''Matrices and Matroids for Systems Analysis'', Springer-Verlag, 1999.
+[3] K. Murota, ''Matrices and Matroids for Systems Analysis'', Springer-Verlag, 2000.
 [4] J. G. Oxley, ''Matroid Theory'', Oxford University Press, 1992.
@@ 100行目: / 103行目: @@
 [7] N.White (ed.) , ''Matroid Applications'', Cambridge University Press, 1992.
 [[Category:グラフ･ネットワーク|まとろいど]]

@@ 1行目: / 1行目: @@
 '''【まとろいど (matroid)】'''
 マトロイドは, ベクトル集合の一次独立性・従属性といった概念を組合せ論的に抽象化することによって得られる公理系を用いて, 1935年にホイットニー(H. Whitney)によって導入された. 1950年代までのタット(W.T. Tutte)らによるマトロイドの理論研究の後, 1960年代にエドモンズ(J. Edmonds)によって数理計画法における重要性が指摘されて以来, マトロイドは, 効率的に解くことのできる離散最適化問題を把握する枠組として中心的な役割を担っている.
-詳しくは[[《マトロイド》|基礎編：マトロイド]]を参照.

← 古い版		2007年8月8日 (水) 12:01時点における版
2行目:		2行目:

	マトロイドは, ベクトル集合の一次独立性・従属性といった概念を組合せ論的に抽象化することによって得られる公理系を用いて, 1935年にホイットニー(H. Whitney)によって導入された. 1950年代までのタット(W.T. Tutte)らによるマトロイドの理論研究の後, 1960年代にエドモンズ(J. Edmonds)によって数理計画法における重要性が指摘されて以来, マトロイドは, 効率的に解くことのできる離散最適化問題を把握する枠組として中心的な役割を担っている.		マトロイドは, ベクトル集合の一次独立性・従属性といった概念を組合せ論的に抽象化することによって得られる公理系を用いて, 1935年にホイットニー(H. Whitney)によって導入された. 1950年代までのタット(W.T. Tutte)らによるマトロイドの理論研究の後, 1960年代にエドモンズ(J. Edmonds)によって数理計画法における重要性が指摘されて以来, マトロイドは, 効率的に解くことのできる離散最適化問題を把握する枠組として中心的な役割を担っている.
		+
		+
		+	詳しくは[[《マトロイド》\|基礎編：マトロイド]]を参照.

← 古い版		2007年7月16日 (月) 10:24時点における版
1行目:		1行目:
−	【まとろいど (matroid)】	+	'''【まとろいど (matroid)】'''

	マトロイドは, ベクトル集合の一次独立性・従属性といった概念を組合せ論的に抽象化することによって得られる公理系を用いて, 1935年にホイットニー(H. Whitney)によって導入された. 1950年代までのタット(W.T. Tutte)らによるマトロイドの理論研究の後, 1960年代にエドモンズ(J. Edmonds)によって数理計画法における重要性が指摘されて以来, マトロイドは, 効率的に解くことのできる離散最適化問題を把握する枠組として中心的な役割を担っている.		マトロイドは, ベクトル集合の一次独立性・従属性といった概念を組合せ論的に抽象化することによって得られる公理系を用いて, 1935年にホイットニー(H. Whitney)によって導入された. 1950年代までのタット(W.T. Tutte)らによるマトロイドの理論研究の後, 1960年代にエドモンズ(J. Edmonds)によって数理計画法における重要性が指摘されて以来, マトロイドは, 効率的に解くことのできる離散最適化問題を把握する枠組として中心的な役割を担っている.

← 古い版	2007年7月20日 (金) 01:58時点における版
(相違点なし)