マトロイドめも

マトロイドについてすこし学んだので,大学で学んだ線形代数とのつながりを含めてメモ.

マトロイドの定義と具体例

マトロイドというのは行列(matrix)のようなもの(-oid)に由来してる.定義はこれ.1番と2番の性質だけだと独立システム(independence system)という.

マトロイドの具体例としては行列マトロイドがある.行列Aがあって,Aの列ベクトルの集合を台集合E,Aの1次独立な列ベクトルの集合全体の集合を集合族Fとする(ただし空集合を含む)と(E,F)はマトロイド.

n個のベクトルv_1,...,v_nが1次独立ならv_1,...,v_k (k≦n)も1次独立だから性質2.を満たす.

n個のベクトルu_1,...,u_nとm個のベクトルv_1,...,v_m (n<m)があって,どのv_kをu_1,...,u_nに加えても1次従属になるとすると任意のv_kはu_1,...,u_nの1次結合で書けることになって,n<mとあわせてv_1,...,v_mが1次従属であることがわかる.これは仮定に反するから性質3.を満たす.

ここでマトロイドの基というものを定義する.基とは極大な独立集合(Fの要素を独立集合と呼ぶ)のこと.つまりこれ以上別の要素を加えると独立集合でなくなってしまうような独立集合のことである.基はいくつか存在し得るが,全ての基の要素数は等しいことがわかる(もし要素数の異なる基があると性質3.から独立集合のまま要素を追加できて基であることに反する).よって基の要素数というのは一意に定まるのでこれをマトロイドの階数という.用語から明らかだろうが,行列マトロイドの場合は行列の階数と同じ.1次独立の概念を一般化した「行列っぽいもの」なので行列についてはそのまんま.

別のマトロイドの例として,競プロer的に関心の高いグラフ的マトロイド(閉路マトロイド)を挙げる.

グラフG(V,E)がある.Eの閉路を含まない部分集合(つまり森)全体の集合を集合族Fとすると(E,F)はマトロイド.グラフの接続行列をかんがえると,「辺の集合が閉路を含む⇔接続行列の対応する列ベクトルたちがZ/2Z上で1次従属」であることがわかる.何故ならループに含まれる列ベクトルたちをv_1,...,v_nとするとv_1+...+v_n=0であって,c_1*v_1+...+c_n*v_n=0を満たすc_1=...=c_n=0でないcが存在するから.という訳で辺の集合が閉路を含まないことを接続行列の列ベクトルの1次独立性と対応できたので,マトロイドであることがたしかめられる.ちなみにここには行列を挟まずに証明する方法が載ってる.X,Y∈Fかつ|X|<|Y|とすると,(Xに含まれる木の数)>(Yに含まれる木の数)なのでYには2つの頂点がXの異なる木に含まれるような木Tが存在する(鳩ノ巣原理).この頂点をu,vとするとu-vを結んでもXに閉路は出来ないので増加公理(マトロイドの性質3.)を満たす.

マトロイドと貪欲法

ここなどに資料がある.

マトロイド上の最大独立集合問題には重みの大きい要素から順に見ていって加えても独立集合のままなら加えるという貪欲法が適用できることが証明できる.詳しい証明は資料を見てほしいが,簡単に言えば貪欲な選び方は他の任意の選び方に対し大きいものからi個目まで見ている時点で採用している要素数がすくなくない,ということが重要.このことから何が言えるかというと,任意の選び方においてi番目の要素を採用するとき,貪欲な選び方でもi番目の要素を採用しているか,またはそれより前(つまりi番目の要素以上)の要素を採用していることになるから貪欲な選び方が負けることはない.

蟻本p.45の区間スケジューリングの証明にも似たようなことが書いてある→「他の任意の選び方に対し,このアルゴリズムの選び方は,開始時間が早いものから同じ個数のところで,終了時間が遅くない」

(「同時に選べる仕事の集合全ての集合」を集合族Fとしてしまうと,増加公理を満たさないのでこれ自体はマトロイドではないはず.これはどういう理屈で上手くいくんだろう.)

貪欲法のイメージ

前章にも出てきたように貪欲法で上手くいくことの証明にはしばしば「任意の時点で他の選び方に負けていない」という事実が用いられる気がする.マトロイドの場合,良い方から取れるだけ取ったときに取れる個数がちょうどそこまでに取れる最大個数と同じなので他にどんな取り方をしても得はできない.こういう風に評価がよくなかった奴がのちのちよくなるみたいな凸凹がないのが貪欲に共通するイメージなのだろう.逆に,ナップサック問題のように今の価値の和は小さくても重量の和も小さいからのちのち良くなる,とかさまざまな状況があるような問題は凸凹しててDPしないと無理かなあ,というイメージになる.

まとめ

マトロイドを知っているからといってすぐ競プロに活かせるかはわからないが,けんちょんの記事にあるように,問題の雰囲気をつかめるようになるかもしれない.けど,そういう実益的なことはさておき,どういう問題なら上手くとけるのか,というような構造を知ることは楽しいので,もっと学びたくなった.