A First Course in Combinatorial Optimization Chapter 3(前半) 濱田 浩気
3 Matroid Intersection 3章ではマトロイドの交差を扱う 3.1 ではマトロイドの交差の用途 3.2 では交差を求めるアルゴリズム
マトロイドの定義の確認 例: グラフGのgraphic matroid M グラフGのgraphic matroid: 1 2 3 例: グラフGのgraphic matroid M グラフGのgraphic matroid: 台集合がGの枝集合E(G)={1,2,3} 独立集合がGの森
3.1 Applications マトロイドの交差の用途を紹介する 一般には独立公理をみたさない 最大サイズの独立集合を求めるための貪欲法は 必ずしもうまくいかない マトロイドの交差の用途を紹介する
例:マトロイドの交差は 必ずしもマトロイドではない 2 1 3 グラフGのgraphic matroid: 台集合がE(G) 独立集合がGの森の集合 2 1 3 貪欲法で最大サイズの要素が得られない
例:二部グラフのマッチング 1 2 3 4
例: 平面上のgeneric rigidity (平面上の)骨組み (平面上の)運動
自明/非自明な運動 上の剛体運動を自明な運動， それ以外の運動を非自明な運動と呼ぶ (平面)上の自明な運動(剛体運動): {水平方向への平行移動， 垂直方向への平行移動， 時計周りの回転}の線形結合 自明な運動(剛体運動) 非自明な運動
Infinitesimal rigidity すべての運動が自明な骨組みは infinitesimally rigidであるという． 直感的には，骨組みがinfinitesimally rigid 骨組みが変形する運動がない Infinitesimally rigidでない骨組みと 非自明な運動 Infinitesimally rigidな骨組み
運動の次元 与えられた骨組みGの運動の次元を求めたい - 平面ならば，運動の次元が3自明な運動のみinfinitesimally rigid 次元定理
運動の次元の計算例 骨組みGの運動が満たすべき条件は 実際，この骨組みは平面上の剛体運動(3つ)の他に 1つの非自明な運動をもつ． 骨組みG 階数は4 Gの非自明な運動 次元定理 実際，この骨組みは平面上の剛体運動(3つ)の他に 1つの非自明な運動をもつ．
グラフと骨組み Generic rigidity: グラフの特性 グラフGから以下の性質をみたす骨組みG’を作る(節点にd次元空間の点を割り当てる)ことができるとき，Gはgenerically rigid． G’はinfinitesimally rigidであり， G’の棒の長さは有理数上で代数的独立 与えられたグラフが generically rigidか否かを判定したい
Generic rigidity Generic rigidityは直感的には 次のように解釈できる: グラフGから骨組みG’を作るとき， ほとんどの場合にG’がinfinitesimally rigid グラフGはgenerically rigid Infinitesimally rigidな 骨組み Infinitesimally rigidでない 骨組み (generically rigidな)グラフG ほとんどの場合 ごく稀
定理3.1.6 2つの全域木の結合となっているかはマトロイドの交差で判定可能:
例3.1.7 有向ハミルトン閉路 3つのマトロイドを利用して有向ハミルトン閉路の集合を求める |Y|=4 |X|=3 この枝を追加できる 有向グラフG
uniformマトロイド・直和(1.1で定義) uniform rank-k マトロイド:
例3.1.7 有向ハミルトン閉路(続き)
3.2 An Efficient Cardinality Matroid-Intersection Algorithm 3.1ではマトロイドの交差の用途を紹介した 3.2ではマトロイドの交差を得る方法を扱う
補題3.2.1(証明)
二部交換グラフ (bipartite exchange graph) 要するに， 5 7 1 2 3 4 5 6 7 8 9 6 4 3 9 2 1 8
補題3.2.2 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
補題3.2.2(証明)
補題3.2.3 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
二部増大有向グラフ 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 sink source
補題3.2.5 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 sink source
補題3.2.5(証明)