計算量理論 1. マトロイドと貪欲アルゴリズム 1. Matroids and the Greedy Algorithm

Presentation on theme: "計算量理論 1. マトロイドと貪欲アルゴリズム 1. Matroids and the Greedy Algorithm"— Presentation transcript:

1 計算量理論 1. マトロイドと貪欲アルゴリズム 1. Matroids and the Greedy Algorithm

2 1. Matroids and the Greedy Algorithm
1.1 独立公理とマトロイドの例　　　　　　（Independence Axioms and Examples of Matroids） 1.2 サーキットの性質　（Circuit Properties） 1.3 表現　（Representations） 1.4 貪欲アルゴリズム　（The Greedy Algorithm） 1.5 ランクの性質　（Rank Properties） 1.6 双対性　（Duality） 1.7 マトロイド多面体　（The Matroid Polytope） 1.8 Further Study

3 マトロイドの定義 マトロイド M とは，有限集合 E(M) と，E(M) の部分集合の族 のペア．
本章ではマトロイドの基礎的な内容を扱う． E(M) ：台集合 (ground set)， I(M) の要素：独立集合(independence set)

4 マトロイドの定義 Independence Axioms
マトロイド M とは，有限集合 E(M) と，E(M) の部分集合の族 　　　　　　　　 　 のペアで，下に示す Independence Axioms をみたすもの． Independence Axioms となる が存在． I3 ： exchange axiom

5 マトロイドの例 線形マトロイド (Linear matroid) － 体 F 上の行列 A に対し，
　　　 E(M) を A の列の集合（縦ベクトルの集合）， 　　　 I(M) の要素を，線形独立なベクトル v ∈ E(M) の集合としたもの． 　－ 行列 A を，マトロイド M の F 上の表現（representation）と呼ぶ． I1, I2 は自明． X, Y ∈ I(M) (|Y| > |X|) とすると， (Y の次元) > (X の次元) なので X のどのベクトルとも独立な v ∈ Y が 存在し，X + v ∈ I(M)．（I3 が成立）

6 マトロイドの例 G κ(G) = 4 定義 ・ グラフGの節点集合を V(G), 枝集合を E(G) とする．
・ F ⊆ E(G) に対し，グラフ G.F を，節点集合 V(G.F) := V(G), 　 枝集合 F(G.F) := F のグラフとする． ・ 枝部分集合 F ⊆ E(G) が閉路を持たないとき，F を森（forest）と呼ぶ． κ(G) = 4 森 G

7 マトロイドの例 G グラフ的マトロイド (Graphic matroid) Y X
　 －グラフ G に対し，E(M) := E(G), I(M) を G の森全体の集合としたもの． e1, e2, e3 の全てを同時に含まない枝集合 が I(M) の要素． e1 e3 e2 G I1, I2 は自明． X, Y ∈ I(M), |Y| > |X| に対し， 全ての e ∈ Y－X で X + e が閉路を持つとすると， |Y| ≦|X| となり矛盾． ( e ∈ Y－X の端点は，両方とも G.X の同一の連結成分に 含まれる ⇒ κ(G.Y) ≧κ(G.X) ⇒ |Y| ≦|X| ( ∵ |F| = |V|－κ(G.F) ).) Y X

8 マトロイドの例 一様マトロイド (Uniform matroid)
　 － E(M) を有限集合とし，r を 0 ≦ r ≦ E(M) となる整数として， 　　　としたもの． I1, I2, I3 の成立は自明． Y, X ∈ I(M), |Y| > |X| のとき，どの e ∈Y－X を X に加えても X + e は I(M) に含まれる ( |X| < |Y| ≦r なので，| X + e | ≦r )．

9 諸定義 　・ 直和 (Direct sum) 　　 マトロイド 　　　　　　　　　　　　　　　　　　 の直和 M とは， 　　 としたもの．このとき，M はマトロイドとなる．

10 諸定義 ・ 独立性システム（Independent system）
　　E(M) と I(M) のペア M で，必ずしも公理 I3 を満たさないもの． 　　　独立性システムで，マトロイドではないものの例（vertex packing on star）： 　　　　 E(M) がグラフ G の節点集合で， 　　　　 I(M) がvertex packing （どの節点間にも枝のない節点集合）の集合． 2 3 X = {1}，Y = {2, 3, 4, 5} 1 どの Y の要素を X に加えても vertex packing とならない． 5 4

11 1.2 Circuit Properties 独立性システム M で， を従属集合（dependent set）と呼ぶ．
従属集合のうち，真部分集合が I(M) の要素となるもの（極小な従属集合）をサーキット（circuit）と呼ぶ． サーキットの集合を C(M) とする． 要素が1つのサーキットをループと呼ぶ． 例： グラフ的マトロイドでは，サーキットは閉路となる． 　　 ループは自己ループ．

12 サーキットの性質 Circuit Properties となる が存在．
M がマトロイドなら，サーキットの集合 C(M) は下の C1, C2, C3 を満たす. M が独立性システムで，C(M) が C1, C2 を満たすとき， 　　M をクラッター (clutter) と呼ぶ． Circuit Properties となる が存在． M がマトロイドなら C(M) が C3 （circuit-elimination property） を満たすことを次の定理で示す.

13 クラッター M が独立性システム（I(M) がI3を満たさないM）で，C(M) が C1, C2 を満たすとき，M をクラッター (clutter) と呼ぶ． となる が存在． となる が存在． クラッターの例 （vertex packing on star） E(M) がグラフ G の節点集合で， I(M) がvertex packing （どの節点間にも枝のない節点集合）の集合． 2 3 1 5 4 異なるサーキット X = { 1, i }，Y = { 1, j } (i≠j，i, j ≧2) ， 1 = e ∈ X ∩Y に対し， (X ∪Y) －e = {i, j} のどの部分集合もサーキットではない ( I(M) に含まれる)．

14 Theorem (Circuit elimination)
　 M がマトロイド ⇒ C(M) は C3 を満たす. が C(M) の要素を含まないと仮定． W Y g を， Y－f を含む 極大な独立集合とする． Y ⊆W なので，f ∈W. また，X ⊆W なので，g ∈ X－W を選べる． f X I3 を W と (X∪Y)－e に適用すると， Wの極大性に矛盾． となる が存在．

15 サーキットの性質 E(M) と C1, C2 を満たす C(M) が与えられたとき，
　 C(M) をサーキットと持ち， I1, I2 をみたすI(M) がただ1つ存在し，

16 1.3 Representations 本節では，ファノマトロイド（Fano matroid）について扱う．
ファノマトロイドとは，下の行列 F によって GF(2) 上で表現されるマトロイド． 線形マトロイド： E(M) を F の列の集合（縦ベクトルの集合）， I(M) の要素を線形独立なベクトルからなる E(M) の部分集合としたもの．

17 諸定義 マトロイド M の極小表現 (Minimal representation)
A と A’ が射影同値（projective equivalence） 　　同じ体上の r×n 行列 A と A’ の行ベクトルが線形独立であり，かつ， 　　ある正則行列 B と 正則な対角行列 D が存在して，A’ = BAD． 　　（射影同値は同値関係となる．） 行列 A と A’ が射影同値のとき，それらは同じマトロイドを表現する．（逆は必ずしも成り立たない．）

18 Fano representation 定理（Fano representation） ・ ファノマトロイドがある体上で表現可能
　　・ ファノマトロイドがある体上で表現可能 　　　 ⇔ その体の標数は2. 　　・ ファノマトロイドの標数2の体上の極小表現は，行列 F とその 　　　射影同値な行列以外に存在しない． 体の標数： 1 (乗法の単位元) を n 回たしたときに 0 (加法の単位元) となるような 　　　　　　　最小のn. このようなnが存在しないなら 0. 　　　　　　　GF(2) なら 2. (1+1=0.)

19 Fano representation 定理（Fano representation） ・ ファノマトロイドがある体上で表現可能
　　・ ファノマトロイドがある体上で表現可能 　　　 ⇔ その体の標数は2. 　　・ ファノマトロイドの標数2の体上の極小表現は，行列 F とその 　　　射影同値な行列以外に存在しない． 証明の方針: ・ ある体上の行列 A をファノマトロイドの表現とおき， 　A に正則な行列（前々スライドの B, D）を掛けることで F が得られることを示す． 　（A の要素を地道に 0 と 1 にしていく．） ・ 最後に，その体の標数が 2 であることを示す． 　 （列 4, 5, 6 が一次従属であるためには，1+1=0 でなければならない．

20 1.4 Greedy Algorithm 諸定義 貪欲アルゴリズム（greedy algorithm） ・ ランク関数
　・ ランク関数 　　 独立性システム M に対し， 　　 （X の部分集合で最も大きい Y ∈ I(M) の |Y|．） 　・ M のランク 　　　　　　　　　　　 　（ = 要素数最大の X ∈ I(M) の |X| ） 　・ 基 (base) 　　　　　　　　　　　　　　　　　となる S ∈ I(M). 　　　　　 （B(M) で基全体の集合をあらわす．） 貪欲アルゴリズム（greedy algorithm） 　　M がマトロイドのとき，基は貪欲アルゴリズムで見つけることができる．

21 貪欲アルゴリズム Greedy Algorithm i. 任意に e ∈ U を選び，U := U－e.
　ii. S + e ∈ I(M) なら S := S + e. ファノマトロイドでは，まだ選んでいない列ベクトルを任意に選び， どの S の要素とも線形独立なら S に加える．

22 貪欲アルゴリズム Greedy Algorithm i. 任意に e ∈ U を選び，U := U－e.
　ii. S + e ∈ I(M) なら S := S + e. 3. S を出力． 最適性の証明： もし S が基でない場合，基 B があって |S| < |B|. I3 より，e ∈ B－S が存在して S + e ∈ I(M). アルゴリズムでこの e は選ばれているはずなので矛盾．

23 貪欲アルゴリズム M がマトロイドではない独立性システムの場合，貪欲アルゴリズムが失敗 することがある．
例(vertex packing on star): 　　　 E(M) がグラフ G の節点集合で， 　 　　I(M) がvertex packing （どの節点間にも枝のない節点集合）の集合． 2 3 節点 1 が最初に選ばれると，他の節点はもう選ばれない． しかし明らかに基は {2,3,4,5}． 1 5 4 （基はグラフの最大独立集合）

24 重み付きの場合 Greedy Algorithm i. 重み最大の sk ∈ U を選び，U := U－sk.
重み付きでも貪欲アルゴリズムで最適解を求めることができる． 各 e ∈ E(M) は重み c(e) を持つこととし，与えられた k （ 0 ≦k ≦rM(E(M) ）に対し，重み最大の S ∈I(M) （ |S| = k ）を求める． Greedy Algorithm 　i. 重み最大の sk ∈ U を選び，U := U－sk. 　ii. Sk-1 + sk ∈ I(M) なら Sk := Sk-1 + sk，k := k+1. 3. Sk を出力． 最適性は次の定理で証明．

25 貪欲アルゴリズムの最適性 定理（貪欲アルゴリズムの最適性） が存在する．）
　　貪欲アルゴリズムは，要素数 k の重み最大の独立集合をみつける．ただし， 0 ≦ k ≦ rM(E(M) ． (証明) ・ 出力 Sk が最大重みでないと仮定する． 　出力を 　最適解を ・ 仮定より 　 ゆえに，ある p （1≦p ≦k ） が存在して ・ アルゴリズムで　　　　　　　　　　 まで選んだとき， 　次は　　，もしくはより重みの大きいものを選んでいたはず． 　（∵ 2つの独立集合　　　　　　　 　　　　 　　を考えたとき，I3 から が存在する．）

26 マトロイドの特徴づけ X Y 定理（Greedy characterization of matroids） E(M)
　　貪欲アルゴリズムが，全ての k と(非負の)重み関数 c で最大重み独立集合 S ( |S| = k ) を見つけるとき，M はマトロイドである． (証明) Y と X ( |Y| > |X| ) が I3 を満たさないとする． X Y 1 1 + ε εが十分小さいなら，グリーディアルゴリズムは 重み最大の独立集合を出力． しかし，アルゴリズムの|X| ステップ目までは X の要素を選んでいるはず． このとき出力される X’ の重みは (1+ε)|X|．ε< 1/E(M) とすれば，c(X’) < |X| + 1 ≦ c(Y)． E(M) となる が存在．

27 1.5 Rank Properties Rank Properties
M がマトロイドならR1～R3 を満たす． E := E(M), r := rM Rank Properties かつ，r(X) は整数． R3: 劣モジュラー性 (submodularity)． M が独立性システムの場合は R3 を必ずしも満たさない．ただし次はみたす．

28 1.5 Rank Properties 定理 (Submodularity of matroid rank function)
　　M がマトロイドなら，rM は R3 を満たす． (証明略)

29 ランク関数による特徴づけ Rank Properties 定理 (Rank characterization of matroids)
　　E: 有限集合．r: 2E → R が R1, R2, R3 を満たすとき， 　　とすれば， M はマトロイドとなる．ただし， E(M) := E, rM = r． (証明略) Rank Properties かつ，r(X) は整数．

30 1.6 Duality マトロイド M の双対 M* を以下のように定義する. 定理 (Matroid duality) G
　　（Gの枝とG*の枝をクロスしているもので対応づける．） グラフ的マトロイド: E(M) : 枝集合 I(M) : 森の集合 基は全域木 G 双対平面グラフ G*

31 1.6 Duality G G* M* の基は M の基の補集合.
M の（最大重みの基 B を見つける）グリーディアルゴリズムにより， 　 M* の最小重みの基 B* をみつけることができる．B = E(M) ＼ B*. G の全域木(基)に対応する枝をG*から取り除くと全域木となる． G G*

32 1.7 The Matroid Polytope マトロイド多面体 (Matroid polytope)
E(M) = {1, 2,.., n} に対して，S = {1,2,4} なら x(S) = (1, 1, 0, 1, 0,..., 0). 定理 (Matroid Polytope) 　　 マトロイド M に対し，

33 1.7 The Matroid Polytope 定理 (Greedy optimality for Polymatroids)
　　E = {1,2,..., n}, r: E → R を R2, R3 を満たし，r(Φ) = 0 となる関数， 　　　　　　　　　　　　　　　　　　 k を c(e) が非負である最大の index， 　　x ∈ RE をグリーディ解として次のように定義すると， 　 次の線形計画法の最適解となる． subject to: さらに，k = n かつ，制約条件から xe ≧ 0 をなくすと， r が R2 を満たすという仮定を省略できる．

34 （再褐） Rank Properties かつ，r(X) は整数．

35 諸定義 次を満たすとき，T ⊆ E(M) は inseperable ランク不等式は inseperable でないなら冗長．
に分割できる．

36 諸定義 次を満たすとき，T ⊆ E(M) は closed 「どの e ⊆E(M) も とならない．」
M がマトロイドのとき，任意の T ⊆ E(M) に対し， 　　　　　　　　　　　　　となる極大な T ⊆ cl(T) が存在． 　 （cl(T) をTの closure とよぶ．） ランク不等式は closed でないなら冗長． closed でないなら， と に分割できる．

37 1.7 The Matroid Polytope 定理 (Facets of a matroid polytope)
　　 M をマトロイドとし，全ての f ∈E(M) が { f } ∈ I(M) なら， 　　 closed かつ inseparable な（空でない）集合に対するランク不等式は 　　 PI(M) のminimal description となっている．