全域木がマトロイドの基になるやつ

こんにちは。理情に入ってからフラフラと生きてきましたがやっとこさ希望研究室を決めたのでグラフ理論についてヒーコラ言いながら勉強しているぶるーまんです。

マトロイドの各種公理系が色々あり全域木は基の性質を満たしていることは有名なやつだと思いますがその証明を考えていたときに一次従属でえいやっとするやつを思い浮かんだのでどっかしら100%既出だとは思いますが書いてみます。こういう感じで色々勉強したこと書けたら良いね。とりあえず図は気分が載ったときに付け加えたいと思います。

既存の証明としては基本閉路/カットを使ったけんちょんさんの↓

drken1215.hatenablog.comが分かりやすかったので貼っておきます。

 

定義

マトロイドの基とは有限集合E上の集合族 \mathcal{B}で以下の2条件を満たすもの

(i) \mathcal{B}の要素はお互いの真部分集合ではない。

(ii) B_1,B_2\in \mathcal{B}

 \forall e\in B_1\setminus B_2 ,\exists f \in B_2\setminus B_1 :(B_1 \setminus \{e\})\cup \{f\} \in \mathcal{B}

以下グラフGは連結とします(非連結の場合はまあそれぞれでやればいいでしょ多分)

 

証明

(i)はそう。(ii)について背理法を使う。つまり T_1,T_2をグラフ Gの全域木として

 

 \exists e \in T_1\setminus T_2, \forall f \in T_2\setminus T_1

 (T_1\setminus \{e\})\cup \{f\}は全域木ではない

 

ということを仮定します。

 

面倒なので以降 T'_1 = T_1\setminus\{e\}と書きます。

全域木の辺数は全て |G|-1なので |T'_1| = |T_2| - 1

よって共通部分だけ削っても1個少ないことに変わりなく |T'_1 \setminus T_2| = |T_2 \setminus T'_1| - 1以降 k=|T_2 \setminus T'_1|とします。

この \forall f\in T_2\setminus T'_1に対して T'_1\cup \{f\}は全域木ではないので閉路Cを含む。Cはもともと T_1が木だった事からせいぜい1つのはずなので一意になる。またこのCが T_2の元だけからなると T_2が木だったことに矛盾するので T'_1 \setminus T_2の元を少なくとも1つ含むはず。それを C_f = C \cap T'_1\setminus T_2と表記するとして各 f\in T_2\setminus T'_1に対し非空の C_f \subset T'_1 \setminus T_2が定まっている。

この時fの候補は k個でC_fに含まれる元の個数は k-1個以下なので対称和により T'_1 \setminus T_2 F_2のベクトル空間とみなすと \{C_f | f\in T_2\setminus T'_1\}k-1次元ベクトル空間上での k個非零ベクトルを考えていることになるので \{f_1, f_2...f_n\}が存在して f_1 + ... + f_n = 0となる。

閉路の対称和は0個以上の素な閉路の和となるので今とったn個の閉路の対称和は0個以上の閉路の和であり f_1 + ... f_n = 0より T'_1\setminus T_2の要素を含まない。またf_iC_fにのみ含まれるので相殺されることはなくよって出来上がった閉路の和は空ではない。つまりT_2内に1つ以上の閉路を含むことになるがこれは矛盾。