翻訳と辞書 Words near each other ・ マトリューシカ ・ マトリューシカ人形 ・ マトリョミン ・ マトリョーシカ ・ マトリョーシカ人形 ・ マトリリシン ・ マトリン ・ マトリーチェ ・ マトルーフ県 ・ マトル語 ・ マトロイド ・ マトロスカ ・ マトロックス ・ マトロック・タウンFC ・ マトワ ・ マトン ・ マトヴェイ ・ マトヴェイ・カザコフ ・ マトヴェイ・グセフ ・ マトヴェイ・ゲデンシュトロム Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク マトロイド ： ミニ英和和英辞書 マトロイド ===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 マトロイド ： ウィキペディア日本語版 マトロイド マトロイド(''matroid'')はある公理を満たす集合とそのべき集合の部分集合の組である。歴史的には、行列の一次独立・従属を一般化した概念であるが、多くの組合せ最適化問題をマトロイドあるいはより緩い独立性システムとコスト関数で定式化でき、特徴付けを行える等応用範囲は広い。特に組合せ最適化において、マトロイド上の最適化問題には単純な貪欲法によって多項式時間のアルゴリズムとは限らないものの最適解が得られることは非常に重要である。 ==定義== 有限集合 $E$ と部分集合 $F\; \backslash subseteq\; 2^E$ の組 $(E,\; F)$ について〔記号の意味については「冪集合」「空集合」「集合間の関係を表す記号」「濃度 (数学)」「和集合」「差集合」を参照のこと〕 *(A1) $\backslash emptyset\backslash in$ *(A2) $X\; \backslash subseteq\; Y\; \backslash in\; F$ ならば $X\; \backslash in\; F$ *(A3)X,Y∈F,|X|>|Y|ならば$Y\backslash cup\backslash \backslash in$となる$xX\backslash setminus$が存在する。 (A1), (A2), (A3)を満たすとき、マトロイドと呼ばれ、(A1) 及び (A2) のみを満たすとき独立性システム(''independence system'')と呼ばれる。さらに (A1) 及び (A3) を満たすときグリードイド(''greedoid'')と呼ばれる。 以下に本項で使う用語の定義を挙げる。 *独立集合 () - $F$ の要素 *従属集合 () - $2^E\; \backslash setminus\; F$ の要素 *サーキット () - 極小な従属集合 *基 () - 極大な独立集合 *Xの基 - $X\; \backslash subseteq\; E$ とする $X$ の部分集合の中で極大な独立集合 マトロイド及び独立性システムの定義を与えたが、ひどく抽象的で理解しづらいかもしれない。ここでは具体的なモデルとしてグラフで考えよう。Eを辺の集合とする。Fは辺の任意の組合せの中で(A2)の条件を満たすものでなくてはならない。そのために「Fは森集合」や「Fはハミルトン閉路の部分集合」という条件を与える。これらはいずれも(A2)を満たす。なぜならば、森から辺を取り去っても森であるし、ハミルトン閉路の部分集合から辺を取り去ってもハミルトン閉路の部分集合だからである。しかし「Fはハミルトン閉路の部分集合」という条件では図に示すように(A3)を満たさない。対して「Fは森集合」は(A3)を満たすから、Eをグラフの辺集合、Fを森集合とする組(E,F)はマトロイドであるということが言える。 Fを森集合とした場合、従属集合は閉路を持つグラフの集合であるから、サーキットとは単純閉路となっている辺集合である。また(Xの)基とは(Xの部分集合の中で)できうる最大の森のことで、明らかに(Xでカバーされる)点の数-1本の辺で作られる森が最大であり、この森の集合を言う。 Eをグラフの辺集合、Fを森集合とする(E,F)はマトロイドになることは上述したが、それも含めて次のような場合もマトロイドになって特別に名前が与えられている。 ;ベクトルマトロイド (vector matroid) :Eは体上の行列Cの列集合で、Fの元に含まれる列集合はその体上で線形独立である。 :体を理解しなくても、その部分を実数と読み替えれば線形代数でよく知られた事実よりマトロイドであることが分かる。本項ではベクトルマトロイドと捉えて解説することはないが、マトロイドという名前が行列(matrix)によるという事実を見ても分かるとおり、歴史上は行列の線形独立性から発展した概念である。 ;閉路マトロイド (cycle matroid) :Eは無向グラフGの辺集合であり、Fは閉路のない辺集合(森)の族。しばしばグラフGが閉路マトロイドであることをM(G)と書く。 ;グラフ的マトロイド (graphic matroid) :(E,F)はマトロイドであり、閉路マトロイドと同型であるときグラフ的マトロイドと呼ぶ。つまり、EとFの定義はどうであれ(たとえグラフと関係なさそうに見えても)、閉路マトロイドと同一視できるものを言う。例えば、E=,F=は3つの辺を持つグラフの閉路マトロイドと同一視できるからグラフ的マトロイドであると言える。なお、これは次に紹介する一様マトロイドの例でもある。 ;一様マトロイド (uniform matroid) :Eは有限集合とし、ある整数k以下の元数を持つ2Eの部分集合。明らかに基は元数がkであるようなEの部分集合である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「マトロイド」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.