chap1

計算量理論
1. マトロイドと貪欲アルゴリズム
1. Matroids and the Greedy Algorithm
岩間研 D3 杉原堅也
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
マトロイドの定義

マトロイド M とは，有限集合 E(M) と，E(M) の部分集合の
族 I ( M )  2 E ( M ) のペア．
E(M) ：台集合 (ground set)，
I(M) の要素：独立集合(independence set)

本章ではマトロイドの基礎的な内容を扱う．
マトロイドの定義

マトロイド M とは，有限集合 E(M) と，E(M) の部分集合の
族 I ( M )  2 E ( M ) のペアで，下に示す Independence
Axioms をみたすもの．
Independence Axioms
I1.   I ( M )
I2. X  Y  I ( M )  X  I ( M )
I3. X , Y  I ( M ), Y  X
 X  e  I (M ) となる e Y \ X
I3 ： exchange axiom
が存在．
マトロイドの例

線形マトロイド (Linear matroid)
－体 F 上の行列 A に対し，
E(M) を A の列の集合（縦ベクトルの集合），
I(M) の要素を，線形独立なベクトル v ∈ E(M) の集合としたもの．
－行列 A を，マトロイド M の F 上の表現（representation）と呼ぶ．
 1 0 1 1


A   0 1 0 1
 0 0 1 1


 1   0   1  1
       
E (M )   0 ,  1 ,  0 , 1
 0   0   1  1
       
 1   0   1   0  1 
          
I (M )   0 ,  1 ,  0 ,  1 , 1,
 0   0   1   0  1 
          
I1, I2 は自明．
X, Y ∈ I(M) (|Y| > |X|) とすると，
(Y の次元) > (X の次元) なので
X のどのベクトルとも独立な v ∈ Y が
存在し，X + v ∈ I(M)．（I3 が成立）
マトロイドの例

定義
・グラフGの節点集合を V(G), 枝集合を E(G) とする．
・グラフの連結成分の数をκ(G) とする．
・ F ⊆ E(G) に対し，グラフ G.F を，節点集合 V(G.F) := V(G),
枝集合 F(G.F) := F のグラフとする．
・枝部分集合 F ⊆ E(G) が閉路を持たないとき，F を森（forest）と呼ぶ．
κ(G) = 4
G
森
マトロイドの例

グラフ的マトロイド (Graphic matroid)
－グラフ G に対し，E(M) := E(G), I(M) を G の森全体の集合としたもの．
e1
e3
e1, e2, e3 の全てを同時に含まない枝集合
が I(M) の要素．
e2
G
I1, I2 は自明．
X, Y ∈ I(M), |Y| > |X| に対し，
全ての e ∈ Y－X で X + e が閉路を持つとすると，
Y
|Y| ≦|X| となり矛盾．
( e ∈ Y－X の端点は，両方とも G.X の同一の連結成分に
含まれる ⇒ κ(G.Y) ≧κ(G.X) ⇒ |Y| ≦|X| ( ∵ |F| = |V|－κ(G.F) ).)
X
マトロイドの例

一様マトロイド (Uniform matroid)
－ E(M) を有限集合とし，r を 0 ≦ r ≦ E(M) となる整数として，
I ( M ) : { X  E ( M ) : | X |  r}
としたもの．
E ( M )  {1,2,3,4}
I ( M ) : { X  E ( M ) : | X |  3}
 {{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2},{1,3},}
I1, I2, I3 の成立は自明．
Y, X ∈ I(M), |Y| > |X| のとき，どの e ∈Y－X を X に加えても
X + e は I(M) に含まれる ( |X| < |Y| ≦r なので，| X + e | ≦r )．
諸定義
・直和 (Direct sum)
マトロイド M1 , M 2 ( E(M1 )  E(M 2 )   ) の直和 M とは，
E ( M ) : E ( M 1 )  E ( M 2 )
I ( M ) : { X 1  X 2 : X 1  I ( M 1 ), X 2  I ( M 2 )}
としたもの．このとき，M はマトロイドとなる．
諸定義
・独立性システム（Independent system）
E(M) と I(M) のペア M で，必ずしも公理 I3 を満たさないもの．
独立性システムで，マトロイドではないものの例（vertex packing on star）：
E(M) がグラフ G の節点集合で，
I(M) がvertex packing （どの節点間にも枝のない節点集合）の集合．
2
5
1
3
X = {1}，Y = {2, 3, 4, 5}
どの Y の要素を X に加えても vertex packing とならない．
4
1.2 Circuit Properties
 2E ( M ) \ I (M )

独立性システム M で， X
と呼ぶ．
を従属集合（dependent set）

従属集合のうち，真部分集合が I(M) の要素となるもの（極小な従属集
合）をサーキット（circuit）と呼ぶ．

サーキットの集合を C(M) とする．
C (M )  {X  E (M ) : X  I (M ), e  X , X  e  I (M )}

要素が1つのサーキットをループと呼ぶ．
例：グラフ的マトロイドでは，サーキットは閉路となる．
ループは自己ループ．
サーキットの性質


M がマトロイドなら，サーキットの集合 C(M) は下の C1, C2, C3 を満たす.
M が独立性システムで，C(M) が C1, C2 を満たすとき，
M をクラッター (clutter) と呼ぶ．
Circuit Properties
C1.   C ( M )
C2. X , Y  C ( M ), X  Y  X  Y
C3. X , Y  C ( M ), X  Y , e  X  Y
 Z  ( X  Y )  e となる Z  C (M ) が存在．
M がマトロイドなら C(M) が C3 （circuit-elimination property）
を満たすことを次の定理で示す.
クラッター

M が独立性システム（I(M) がI3を満たさないM）で，C(M) が C1, C2 を満
たすとき，M をクラッター (clutter) と呼ぶ．
I3. X , Y  I (M ), Y  X  X  e  I (M )
となる
e Y \ X
が存在．
C3. X , Y  C ( M ), X  Y , e  X  Y
 Z  ( X  Y )  e となる Z  C (M ) が存在．

クラッターの例（vertex packing on star）
E(M) がグラフ G の節点集合で，
I(M) がvertex packing （どの節点間にも枝のない節点集合）の集合．
2
5
1
3
4
異なるサーキット X = { 1, i }，Y = { 1, j } (i≠j，i, j ≧2) ，
1 = e ∈ X ∩Y に対し，
(X ∪Y) －e = {i, j} のどの部分集合もサーキットではない ( I(M) に含まれる)．
Theorem (Circuit elimination)
定理 (Circuit elimination)

M がマトロイド ⇒ C(M) は C3 を満たす.
( X  Y )  eが C(M) の要素を含まないと仮定．
Y
g
X
W f
f  Y  X  Y  f  I (M )
W  X  Y を， Y－f を含む
極大な独立集合とする．
Y ⊆W なので，f ∈W.
また，X ⊆W なので，g ∈ X－W を選べる．
| W |  | ( X  Y )  f  g |  | X  Y | 2  | ( X  Y )  e |
I3 を W と (X∪Y)－e に適用すると，
h  (( X  Y )  e)  W , W  h  I ( M ). Wの極大性に矛盾．
C3. X , Y  C ( M ), X  Y , e  X  Y
 Z  ( X  Y )  e となる Z  C (M ) が存在．
サーキットの性質

E(M) と C1, C2 を満たす C(M) が与えられたとき，
C(M) をサーキットと持ち， I1, I2 をみたすI(M) がただ1つ存
在し，
I ( M )  { X  E ( M ) : Y  X , Y  C (M )}.
1.3 Representations


本節では，ファノマトロイド（Fano matroid）について扱う．
ファノマトロイドとは，下の行列 F によって GF(2) 上で表現され
るマトロイド．
 1 0 0 0 1 1 1


F   0 1 0 1 0 1 1
 0 0 1 1 1 0 1


 1   0   0 
 1 
 
     
E ( M )   0 ,  1 ,  0 , , 1
 0   0   1 
 1 
 
     
 1   0   1   0  1  0  
            
I (M )   0 ,  1 ,  0 ,  1 , 1,  1 ,
 0   0   1   0  1  0  
            
線形マトロイド：
E(M) を F の列の集合（縦ベクトルの集合），
I(M) の要素を線形独立なベクトルからなる E(M) の部分集合としたもの．
諸定義

マトロイド M の極小表現 (Minimal representation)
M の表現で，行ベクトルが線形独立なもの．

A と A’ が射影同値（projective equivalence）
同じ体上の r×n 行列 A と A’ の行ベクトルが線形独立であり，かつ，
ある正則行列 B と正則な対角行列 D が存在して，A’ = BAD．
（射影同値は同値関係となる．）

行列 A と A’ が射影同値のとき，それらは同じマトロイドを表現
する．（逆は必ずしも成り立たない．）
Fano representation

定理（Fano representation）
・ファノマトロイドがある体上で表現可能
⇔ その体の標数は2.
・ファノマトロイドの標数2の体上の極小表現は，行列 F とその
射影同値な行列以外に存在しない．
体の標数： 1 (乗法の単位元) を n 回たしたときに 0 (加法の単位元) となるような
最小のn. このようなnが存在しないなら 0.
GF(2) なら 2. (1+1=0.)
Fano representation

定理（Fano representation）
・ファノマトロイドがある体上で表現可能
⇔ その体の標数は2.
・ファノマトロイドの標数2の体上の極小表現は，行列 F とその
射影同値な行列以外に存在しない．
証明の方針:
・ある体上の行列 A をファノマトロイドの表現とおき，
A に正則な行列（前々スライドの B, D）を掛けることで F が得られることを示す．
（A の要素を地道に 0 と 1 にしていく．）
 a11 a12

A   a21 a22
a
 31 a32
a13 a14
a23 a24
a15
a25
a16
a26
a33
a35
a36
a34
a17 

a27 
a37 
 1 0 0 0 1 1 1


F   0 1 0 1 0 1 1
 0 0 1 1 1 0 1


・最後に，その体の標数が 2 であることを示す．
（列 4, 5, 6 が一次従属であるためには，1+1=0 でなければならない．
1.4 Greedy Algorithm

諸定義
・ランク関数 rM : 2

独立性システム M に対し， rM ( X ) : max{| Y |
（X の部分集合で最も大きい Y ∈ I(M) の |Y|．）
E(M )
: Y  X , Y  I (M )}.
・ M のランク
rM ( E (M )). （ = 要素数最大の X ∈ I(M) の |X| ）
・基 (base)
| S | rM ( E(M )) となる S ∈ I(M).
（B(M) で基全体の集合をあらわす．）

貪欲アルゴリズム（greedy algorithm）
M がマトロイドのとき，基は貪欲アルゴリズムで見つけることができる．
貪欲アルゴリズム
Greedy Algorithm
1. S :  , U : E ( M )
2. While (U   )
i. 任意に e ∈ U を選び，U := U－e.
ii. S + e ∈ I(M) なら S := S + e.
ファノマトロイドでは，まだ選んでいない列ベクトルを任意に選び，
どの S の要素とも線形独立なら S に加える．
 1 0 0 0 1 1 1


F   0 1 0 1 0 1 1
 0 0 1 1 1 0 1


 1   0   0 
 1 
 
     
E ( M )   0 ,  1 ,  0 , , 1
 0   0   1 
 1 
 
     
 1   0   1   0  1  0  
            
I (M )   0 ,  1 ,  0 ,  1 , 1,  1 ,
 0   0   1   0  1  0  
            
貪欲アルゴリズム
Greedy Algorithm
1. S :  , U : E ( M )
2. While (U   )
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 は選ばれているはずなので矛盾．
貪欲アルゴリズム

M がマトロイドではない独立性システムの場合，貪欲アルゴリズムが失敗
することがある．

例(vertex packing on star):
E(M) がグラフ G の節点集合で，
I(M) がvertex packing （どの節点間にも枝のない節点集合）の集合．
2
5
1
3
節点 1 が最初に選ばれると，他の節点はもう選ばれない．
しかし明らかに基は {2,3,4,5}．
4
（基はグラフの最大独立集合）
重み付きの場合


重み付きでも貪欲アルゴリズムで最適解を求めることができる．
各 e ∈ E(M) は重み c(e) を持つこととし，与えられた k （ 0 ≦k ≦rM(E(M) ）
に対し，重み最大の S ∈I(M) （ |S| = k ）を求める．
Greedy Algorithm
1. S0 :  , k : 1, U : E ( M )
2. While (U   )
i. 重み最大の sk ∈ U を選び，U := U－sk.
ii. Sk-1 + sk ∈ I(M) なら Sk := Sk-1 + sk，k := k+1.
3. Sk を出力．
最適性は次の定理で証明．
貪欲アルゴリズムの最適性

定理（貪欲アルゴリズムの最適性）
貪欲アルゴリズムは，要素数 k の重み最大の独立集合をみつける．ただ
し， 0 ≦ k ≦ rM(E(M) ．
(証明) ・出力 Sk が最大重みでないと仮定する．
出力を
S k  {s1 , s2 ,, sk } c( s1 )  c( s2 )    c( sk )
最適解を Tk  {t1k , t 2k , , t kk } c(t1k )  c(t 2k )    c(t kk )
・仮定より c(Tk )  c( S k ).
ゆえに，ある p （1≦p ≦k ）が存在して
c(t kp )  c(s p ).
・アルゴリズムで s1 , s2 , , s p 1 まで選んだとき，
次は t k ，もしくはより重みの大きいものを選んでいたはず．
p
（∵ 2つの独立集合
S  {s1 , s2 ,, s p 1} を考えたとき，I3 から
T  {t1k , t 2k ,, t kp 1 , t kp }
tik  T  S (1  i  p, S  tik  I ( M )) が存在する．）
マトロイドの特徴づけ

定理（Greedy characterization of matroids）
M を独立性システムとする．
貪欲アルゴリズムが，全ての k と(非負の)重み関数 c で最大重み独立集
合 S ( |S| = k ) を見つけるとき，M はマトロイドである．
(証明) Y と X ( |Y| > |X| ) が I3 を満たさないとする．
(e  X )
1  

c(e) :  1
(e  Y \ X )
 0 ( E ( M ) \ ( X  Y ))

Y
1
X
1+ε
0
εが十分小さいなら，グリーディアルゴリズムは
E(M)
重み最大の独立集合を出力．
しかし，アルゴリズムの|X| ステップ目までは X の要素を選んでいるはず．
このとき出力される X’ の重みは (1+ε)|X|．ε< 1/E(M) とすれば，c(X’) < |X| + 1 ≦ c(Y)．
I3. X , Y  I (M ), Y  X  X  e  I (M )
となる
e Y \ X
が存在．
1.5 Rank Properties

M がマトロイドならR1～R3 を満たす． E := E(M), r := rM
rM ( X )  max{| Y | : Y  X , Y  I (M )}.
Rank Properties
R1. 0  r ( X ) | X |, X  E かつ，r(X) は整数．
R 2. X  Y  r ( X )  r (Y ), X , Y  E
R 3. r ( X  Y )  r ( X  Y )  r ( X )  r (Y ), X , Y  E
R3: 劣モジュラー性 (submodularity)．
M が独立性システムの場合は R3 を必ずしも満たさない．ただし次はみたす．
r ( X  Y )  r ( X )  r (Y ), X , Y  E
1.5 Rank Properties

定理 (Submodularity of matroid rank function)
M がマトロイドなら，rM は R3 を満たす．
(証明略)
ランク関数による特徴づけ

定理 (Rank characterization of matroids)
E: 有限集合．r: 2E → R が R1, R2, R3 を満たすとき，
I ( M ) : {Y  E ( M ) : | Y | r (Y )}.
とすれば， M はマトロイドとなる．ただし， E(M) := E, rM = r．
(証明略)
Rank Properties
R1. 0  r ( X ) | X |, X  E かつ，r(X) は整数．
R 2. X  Y  r ( X )  r (Y ), X , Y  E
R 3. r ( X  Y )  r ( X  Y )  r ( X )  r (Y ), X , Y  E
1.6 Duality

マトロイド M の双対 M* を以下のように定義する.
E ( M *) : E ( M )
I ( M *) : { X  E ( M ) : E ( M ) \ X が M の基を部分集合として含む }

定理 (Matroid duality)
M* はマトロイド．
例: 連結な平面グラフ G のグラフ的マトロイドの双対は，
双対平面グラフ G* のグラフ的マトロイド.
（Gの枝とG*の枝をクロスしているもので対応づける．）
G
双対平面グラフ G*
グラフ的マトロイド:
E(M) : 枝集合
I(M) : 森の集合
基は全域木
1.6 Duality

M* の基は M の基の補集合.
B( M *)  {E ( M ) \ B : B  B(M )}

M の（最大重みの基 B を見つける）グリーディアルゴリズムにより，
M* の最小重みの基 B* をみつけることができる．B = E(M) ＼ B*.
G の全域木(基)に対応する枝をG*から取り除くと全域木となる．
G
G*
1.7 The Matroid Polytope
マトロイド多面体 (Matroid polytope)
PI ( M ) : conv{x( S ) : S  I ( M )}.

マトロイドM の独立集合を端点とした多面体．
E(M) = {1, 2,.., n} に対して，S = {1,2,4} なら x(S) = (1, 1, 0, 1, 0,..., 0).

定理 (Matroid Polytope)
マトロイド M に対し，
PI ( M )  {x  RE ( M ) :  xe  rM (T ), T  E ( M )}.
eT
1.7 The Matroid Polytope

定理 (Greedy optimality for Polymatroids)
E = {1,2,..., n}, r: E → R を R2, R3 を満たし，r(Φ) = 0 となる関数，
c(1)  c(2)    c(n), k を c(e) が非負である最大の index，
x ∈ RE をグリーディ解として次のように定義すると，
r (Te )  r (Te1 ) (1  e  k )
xe : 
0
( k  e  n)

次の線形計画法の最適解となる．
 Te  {1,2,..., e}


T0  


max  c(e) xe
subject to:
x
eT
e
eE
 r (T ), T  E
xe  0, e  E.
さらに，k = n かつ，制約条件から xe ≧ 0 をなくすと，
r が R2 を満たすという仮定を省略できる．
（再褐）
rM ( X )  max{| Y | : Y  X , Y  I (M )}.
Rank Properties
R1. 0  r ( X ) | X |, X  E かつ，r(X) は整数．
R 2. X  Y  r ( X )  r (Y ), X , Y  E
R 3. r ( X  Y )  r ( X  Y )  r ( X )  r (Y ), X , Y  E
諸定義

次を満たすとき，T ⊆ E(M) は inseperable
rM (T )  rM (U )  rM (T \ U )  U  T and U  

ランク不等式は inseperable でないなら冗長．
x
jT
 rM (T )
j
inseperable でないなら，
x
jU
j
 rM (U )
と
x
jT \U
j
 rM (T \ U )
に分割できる．
諸定義

次を満たすとき，T ⊆ E(M) は closed
「どの e ⊆E(M) も rM (T  e)  rM (T ) とならない．」

M がマトロイドのとき，任意の T ⊆ E(M) に対し，
rM (T )  rM (cl (T )) となる極大な T ⊆ cl(T) が存在．
（cl(T) をTの closure とよぶ．）

ランク不等式は closed でないなら冗長．
x
jT
j
 rM (T )
closed でないなら，
x
jcl (T )
j
 rM (T ) と  x j  0, j  cl (T ) \ T に分割できる．
1.7 The Matroid Polytope

定理 (Facets of a matroid polytope)
M をマトロイドとし，全ての f ∈E(M) が { f } ∈ I(M) なら，
closed かつ inseparable な（空でない）集合に対するランク不等式は
PI(M) のminimal description となっている．
PI ( M )  {x  RE ( M ) :  xe  rM (T ), T  E ( M )}.
eT

Download Report