グラフ理論におけるマトロイド
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/07 04:53 UTC 版)
「マトロイド」の記事における「グラフ理論におけるマトロイド」の解説
Eを無向グラフGの辺集合、Fを森の集合とするとき、(E,F)はマトロイドとなり、グラフ的マトロイド（英語版） (graphic matroid) または 閉路マトロイド (cycle matroid)と呼ぶ。しばしばグラフGがグラフ的マトロイドであることをM(G)と書く。グラフ的マトロイドにおける従属集合は、閉路を持つグラフの集合であるから、サーキットとは単純閉路となる辺集合である。また(Xの)基とは(Xの部分集合の中で)できうる最大の森のことで、明らかに(Xでカバーされる)点の数-1本の辺で作られる森が最大であり、この森の集合を言う。よって、階数関数はr(X)=(Xがカバーする点数)-1と書ける。 他にも、グラフにおけるマトロイドはいくつか知られている。 Eを無向グラフGの辺集合、Fを(G, X)がpseudoforest（英語版）となるようなXの集合とするとき(E,F)はマトロイドとなる。これを、bicircularマトロイド（英語版）(bicircular matroid)と呼ぶ。 点集合U,V、辺集合Xとする2部グラフ G = ( U , V , X ) {\displaystyle G=(U,V,X)} において、マッチングの端点となる点集合 S ⊆ U {\displaystyle S\subseteq U} を要素とする集合をFとするとき、(U,F)はマトロイドとなる。これを、横断マトロイド(transversal matroid)と呼ぶ。完全2部グラフ K n , r {\displaystyle K_{n,r}} の横断マトロイドは、一様マトロイド U n r {\displaystyle U_{n}^{r}} である。 点集合をVとするグラフにおいて、点の部分集合を V ′ , U ⊆ V {\displaystyle V',U\subseteq V} とする。Uへの点素な|U|本の道が存在するV'の部分集合をFの要素とすると、(V', F)はマトロイドとなる。これを、ガンモイド（英語版） (gammoid)と呼ぶ。特に、(V, F)を狭義ガンモイド(strict gammoid)と呼ぶ。
※この「グラフ理論におけるマトロイド」の解説は、「マトロイド」の解説の一部です。
「グラフ理論におけるマトロイド」を含む「マトロイド」の記事については、「マトロイド」の概要を参照ください。
- グラフ理論におけるマトロイドのページへのリンク
