1. 高校数学の美しい物語
  2. デルタマトロイド

デルタマトロイド

更新日時 2021/03/07

以前,マトロイドというものについて紹介しました。→マトロイドの定義と具体例

この記事では,マトロイドの一般化であるデルタマトロイドについて紹介します。

目次
  • デルタマトロイドの定義

  • デルタマトロイドの例

  • 上記の定理の証明

デルタマトロイドの定義

有限集合 EE とその部分集合族 F\mathcal{F} について,以下の2つの条件が成立するとき (E,F)(E,\mathcal{F}) のペアをデルタマトロイドと言う。

1.F\mathcal{F} は空でない。

2.任意の X,YFX,Y\in \mathcal{F} と任意の iXΔYi\in X\mathbin{\Delta}Y に対して,ある jXΔYj\in X\mathbin{\Delta}Y が存在して,XΔ{i,j}FX\mathbin{\Delta}\{i,j\}\in\mathcal{F}

対称差

ただし,2つの集合 X,YX,Y に対して XΔYX\mathbin{\Delta}Y は対称差(どちらか片方のみに属する要素を集めた集合)を表します。→集合の記号の意味まとめ

上記の定義には大文字のデルタ「Δ\Delta」が3つも登場しています。

デルタマトロイドはマトロイドの一般化になっています。つまり,任意のマトロイド(独立集合族ではなく基族で考える)は,特殊な(F\mathcal{F} に属する集合の要素数が全て等しい)デルタマトロイドです。

デルタマトロイドの例

デルタマトロイドなんて使う機会あるのか?と思われるかもしれませんが,実は意外と身近な存在かもしれません。

定理

EE:(枝を1本以上持つ)無向グラフの頂点集合。

F\mathcal{F}:マッチングの端点集合を集めたもの。

とすると,(E,F)(E,\mathcal{F}) はデルタマトロイド。

デルタマトロイドの例

例えば,図のようなグラフについては,

E={1,2,3,4,5}E=\{1,2,3,4,5\}

F={,{1,2},{2,3},{2,4},{4,5}{1,2,4,5},{2,3,4,5}}\mathcal{F}=\{\emptyset,\{1,2\},\{2,3\},\{2,4\},\{4,5\}\\ \{1,2,4,5\},\{2,3,4,5\}\}

となります。

{{1,2},{4,5}}\{\{1,2\},\{4,5\}\} はマッチングなので,{1,2,4,5}\{1,2,4,5\}F\mathcal{F} に属している,という感じです。 →二部グラフの最大マッチングと増加道

上記の定理の証明

証明

デルタマトロイドの定義の2を確認すればよい。そこで,

X,YFX,Y\in\mathcal{F}iXΔYi\in X\mathbin{\Delta}Y が与えられた状況を考える。

F\mathcal{F} の定義より,XX を端点集合とするマッチング MXM_XYY を端点集合とするマッチング MYM_Y をとってこれる。

ii に対応する頂点は MXM_XMYM_Y の片方にのみ属するので「交互路」の端点である。

デルタマトロイドとマッチング

そこで,この交互路のもう片方の端点に対応する要素を jj とすると,XΔ{i,j}X\mathbin{\Delta}\{i,j\} も,とあるマッチングの端点集合になっていることが分かる(交互路の端が MXM_X の枝なのか MYM_Y の枝なのかによって4パターンあるが,それぞれ赤を青に「切り替える」ことで XΔ{i,j}X\mathbin{\Delta}\{i,j\} を端点集合とするマッチングを構成できる)。

つまり,XΔ{i,j}FX\mathbin{\Delta}\{i,j\}\in\mathcal{F}

デルタマトロイドが好きな友人にそそのかされて,マニアックな記事を書いてしまいました。

人気記事
  1. 高校数学の美しい物語
  2. デルタマトロイド