A First Course in Combinatorial Optimization Chapter 3(前半)

Presentation on theme: "A First Course in Combinatorial Optimization Chapter 3(前半)"— Presentation transcript:

1 A First Course in Combinatorial Optimization Chapter 3(前半)
濱田 浩気

2 3 Matroid Intersection 3章ではマトロイドの交差を扱う 3.1 ではマトロイドの交差の用途
3.2 では交差を求めるアルゴリズム

3 マトロイドの定義の確認 例: グラフGのgraphic matroid M グラフGのgraphic matroid:
1 2 3 例: グラフGのgraphic matroid M グラフGのgraphic matroid: 台集合がGの枝集合E(G)={1,2,3} 独立集合がGの森

4 3.1 Applications マトロイドの交差の用途を紹介する 一般には独立公理をみたさない
最大サイズの独立集合を求めるための貪欲法は 必ずしもうまくいかない マトロイドの交差の用途を紹介する

5 例:マトロイドの交差は 必ずしもマトロイドではない
2 1 3 グラフGのgraphic matroid: 台集合がE(G) 独立集合がGの森の集合 2 1 3 貪欲法で最大サイズの要素が得られない

6 例:二部グラフのマッチング 1 2 3 4

7 例: 平面上のgeneric rigidity
(平面上の)骨組み (平面上の)運動

8 自明/非自明な運動 上の剛体運動を自明な運動， それ以外の運動を非自明な運動と呼ぶ
(平面)上の自明な運動(剛体運動): {水平方向への平行移動， 垂直方向への平行移動， 時計周りの回転}の線形結合 自明な運動(剛体運動) 非自明な運動

9 Infinitesimal rigidity
すべての運動が自明な骨組みは infinitesimally rigidであるという． 直感的には，骨組みがinfinitesimally rigid  骨組みが変形する運動がない Infinitesimally rigidでない骨組みと 非自明な運動 Infinitesimally rigidな骨組み

10 運動の次元 与えられた骨組みGの運動の次元を求めたい
- 平面ならば，運動の次元が3自明な運動のみinfinitesimally rigid 次元定理

11 運動の次元の計算例 骨組みGの運動が満たすべき条件は 実際，この骨組みは平面上の剛体運動(3つ)の他に 1つの非自明な運動をもつ． 骨組みG
階数は4 Gの非自明な運動 次元定理 実際，この骨組みは平面上の剛体運動(3つ)の他に 1つの非自明な運動をもつ．

12 グラフと骨組み Generic rigidity: グラフの特性
グラフGから以下の性質をみたす骨組みG’を作る(節点にd次元空間の点を割り当てる)ことができるとき，Gはgenerically rigid． G’はinfinitesimally rigidであり， G’の棒の長さは有理数上で代数的独立 与えられたグラフが generically rigidか否かを判定したい

13 Generic rigidity Generic rigidityは直感的には 次のように解釈できる:
グラフGから骨組みG’を作るとき， ほとんどの場合にG’がinfinitesimally rigid  グラフGはgenerically rigid Infinitesimally rigidな 骨組み Infinitesimally rigidでない 骨組み (generically rigidな)グラフG ほとんどの場合 ごく稀

14 定理3.1.6 2つの全域木の結合となっているかはマトロイドの交差で判定可能:

15 例3.1.7 有向ハミルトン閉路 3つのマトロイドを利用して有向ハミルトン閉路の集合を求める |Y|=4 |X|=3 この枝を追加できる
有向グラフG

16 uniformマトロイド・直和(1.1で定義)
uniform rank-k マトロイド:

17 例3.1.7 有向ハミルトン閉路(続き)

18 3.2 An Efficient Cardinality Matroid-Intersection Algorithm
3.1ではマトロイドの交差の用途を紹介した 3.2ではマトロイドの交差を得る方法を扱う

19 補題3.2.1(証明)

20 二部交換グラフ (bipartite exchange graph)
要するに， 5 7 1 2 3 4 5 6 7 8 9 6 4 3 9 2 1 8

21 補題3.2.2 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9

22 補題3.2.2(証明)

23 補題3.2.3 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9

24 二部増大有向グラフ 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

25 補題3.2.5 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 sink source

26 補題3.2.5(証明)