組合せ最適化　第1,2章 M2 　酒井　隆行.

Presentation on theme: "組合せ最適化　第1,2章 M2 　酒井　隆行."— Presentation transcript:

1 組合せ最適化　第1,2章 M2 　酒井　隆行

2 第1章　はじめに 様々な実際的な問題 抽象的な最適化問題

3 第1章　はじめに 様々な実際的な問題 抽象的な最適化問題 例えば…

4 なるべく早く、ドリルで板の複数個の位置に穴をあけたい
第1章　はじめに 最適化問題の例1 なるべく早く、ドリルで板の複数個の位置に穴をあけたい （移動は等速） 問題1.1 ドリル穴あけ問題(Drilling Problem) インスタンス: 平面上のn個の点　 𝑝 1 ,…, 𝑝 𝑛 ∈ 𝑅 𝑛 タスク: 𝑛=1 𝑛−1 𝑑 𝑝 𝜋 𝑖 , 𝑝 𝜋 𝑖+1 が最小となるような順列 𝜋: 1,…,𝑛 → 1,…,𝑛

5 第1章 はじめに 最適化問題の例1 各従業員にジョブを割り振る 担当可能なジョブは従業員ごとに異なる 処理能力の差はない
第1章　はじめに 最適化問題の例1 各従業員にジョブを割り振る 担当可能なジョブは従業員ごとに異なる 処理能力の差はない 同一のジョブに対して、同時に複数の従業員が担当可 従業員は複数のジョブを担当可(同時には不可) 早く終わらせたい 問題1.2　ジョブ割当問題(Job Assignment Probrem) インスタンス: 　n個の非負実数 𝑡 1 ,…, 𝑡 𝑛 ∈ 𝑅 + (ジョブの処理時間) 　　　 m人の従業員と各ジョブ𝑖∈ 1,…,𝑛 に対する担当可な従業員 の部分集合 𝑆 𝑖 ∈ 1,…,𝑚 タスク: 　各𝑖=1,…,𝑛で 𝑗∈ 𝑆 𝑖 𝑥 𝑖,𝑗 = 𝑡 𝑖 を満たす 𝑥 𝑖𝑗 ∈ 𝑅 + 𝑖=1,…,𝑛, 𝑗∈ 𝑆 𝑖 の うちで、 max 𝑗∈ 1,…,𝑚 𝑖:𝑗∈ 𝑆 𝑖 𝑥 𝑖𝑗 が最小となるような 𝑥 𝑖𝑗 ∈ 𝑅 + を求める

6 1.1 列挙 問題1.1 ドリル穴あけ問題(Drilling Problem)
タスク: 𝑛=1 𝑛−1 𝑑 𝑝 𝜋 𝑖 , 𝑝 𝜋 𝑖+1 が最小となるような順列 𝜋: 1,…,𝑛 → 1,…,𝑛 最適解を計算するアルゴリズムは…? 順列を全列挙すると最適解は見つかる

7 1.1 列挙 アルゴリズム1.1 パス列挙アルゴリズム (Path Enumeration Algorithm)
出力: 　パスの長さ 𝑐𝑜𝑠𝑡 𝜋 ∗ ≔ 𝑖=1 𝑛−1 𝑑 𝑝 𝜋 ∗ 𝑖 , 𝑝 𝜋 ∗ 𝑖 が最小とな る順列 𝜋 ∗ : 1,…,𝑛 → 1,…,𝑛 (疑似コード略) 順列を、辞書式順に小さいものから順に調べて、 costの最も小さいものを保存 O 𝑛 2 𝑛! （解析は甘い）　　　もっと高速なアルゴリズムは…?

8 1.2 アルゴリズムの計算時間 アルゴリズムの入力 = 数のリスト 数がすべて整数ならば、2進数表現でコード化可能
有理数は分母と分子を別々にコード化 有理数データからなるインスタンスxに対して、 入力サイズ𝑠𝑖𝑧𝑒 𝑥 = すべての数の2進数表現に必要なビット数

9 1.2 アルゴリズムの計算時間 定義1.3 A： 集合Xの要素を入力として受け取るアルゴリズム 𝑓: 𝑁→ 𝑅 +
𝑓: 𝑁→ 𝑅 + ある定数𝛼>0が存在して、任意の入力𝑥∈𝑋に対して Aがその計算を高々𝛼𝑓 𝑠𝑖𝑧𝑒 𝑥 回の初等的操作で終了するならば Aは𝑶 𝒇 時間で走る or Aの計算時間は𝑶 𝒇 である　という

10 1.2 アルゴリズムの計算時間 定義1.4 有理数入力に対するアルゴリズム
ある整数kが存在して、入力サイズnのどの入力に対しても、𝑂 𝑛 𝑘 時間で走り、計算の途中で生じる数もすべて𝑂 𝑛 𝑘 ビットで記憶で きるとき、多項式時間で走るという 任意の入力に対するアルゴリズム ある整数kが存在して、n個の数のどの入力に対しても𝑂 𝑛 𝑘 時間 で走り、有理数入力に対しても多項式時間で走るとき、強多項式 時間で走るという k=1のときは線形時間アルゴリズムという

11 1.3 線形の最適化問題 問題1.2 ジョブ割当問題(Job Assignment Probrem)
1.3　線形の最適化問題 問題1.2　ジョブ割当問題(Job Assignment Probrem) インスタンス: 　n個の非負実数 𝑡 1 ,…, 𝑡 𝑛 ∈ 𝑅 + (ジョブの処理時間) 　　　 m人の従業員と各ジョブ𝑖∈ 1,…,𝑛 に対する担当可な従業員 の部分集合 𝑆 𝑖 ∈ 1,…,𝑚 タスク: 　各𝑖=1,…,𝑛で 𝑗∈ 𝑆 𝑖 𝑥 𝑖,𝑗 = 𝑡 𝑖 を満たす 𝑥 𝑖𝑗 ∈ 𝑅 + 𝑖=1,…,𝑛, 𝑗∈ 𝑆 𝑖 の うちで、 max 𝑗∈ 1,…,𝑚 𝑖:𝑗∈ 𝑆 𝑖 𝑥 𝑖𝑗 が最小となるような 𝑥 𝑖𝑗 ∈ 𝑅 + を求める ジョブが完了する時刻Tを用いて、線形計画問題として定式化可能 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑇 𝑠.𝑡 𝑗∈ 𝑆 𝑖 𝑥 𝑖𝑗 =𝑡 (𝑖∈ 1,…,𝑛 ) 𝑥 𝑖𝑗 ≥ (𝑖∈ 1,…,𝑛 ,𝑗∈ 𝑆 𝑖 ) 𝑖:𝑗∈ 𝑆 𝑖 𝑥 𝑖𝑗 ≤𝑇 (𝑖∈ 1,…,𝑛 )

12 1.3 線形の最適化問題 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑇 𝑠.𝑡 𝑗∈ 𝑆 𝑖 𝑥 𝑖𝑗 =𝑡 (𝑖∈ 1,…,𝑛 )
1.3　線形の最適化問題 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑇 𝑠.𝑡 𝑗∈ 𝑆 𝑖 𝑥 𝑖𝑗 =𝑡 (𝑖∈ 1,…,𝑛 ) 𝑥 𝑖𝑗 ≥ (𝑖∈ 1,…,𝑛 ,𝑗∈ 𝑆 𝑖 ) 𝑖:𝑗∈ 𝑆 𝑖 𝑥 𝑖𝑗 ≤𝑇 (𝑖∈ 1,…,𝑛 ) すべての実行可能解の集合は多面体と呼ばれ、凸であることがわかる。 最適解が存在するならば、必ず多面体の頂点のいずれかが最適解となる 列挙よりもいい方法がある(後の章で) 集合 𝑆 𝑖 をグラフでモデル化すると… 各ジョブiと各従業員jに対して頂点を考える ジョブと、そのジョブを担当できる従業員を結ぶ 多くの組合せ最適化問題はグラフ理論を用いて定式化される

13 1.3 線形の最適化問題 便宜上、 どのジョブも処理時間は1時間 1時間でジョブを全部完了できるか という問題を考えると…
1.3　線形の最適化問題 便宜上、 どのジョブも処理時間は1時間 1時間でジョブを全部完了できるか という問題を考えると… すべてのiとjに対して　0≤ 𝑥 𝑖𝑗 ≤1 各𝑖=1,…,𝑛に対して　 𝑗∈ 𝑆 𝑖 𝑥 𝑖𝑗 =1 各j=1,…,𝑚 に対して　 𝑖:𝑗∈ 𝑆 𝑖 𝑥 𝑖𝑗 ≤1 となるような 𝑥 𝑖𝑗 を求める問題になる 解が存在するならば整数解も存在 （すべてのiとjに対して𝑥 𝑖𝑗 =0 𝑜𝑟 1） よって 各ジョブを1人の従業員に割り当て、かつどの従業員も2個以上ジョブが割り当てられないように割り当てることと等価 グラフ的には、すべてのジョブをカバーするマッチングを求めればよい ジョブ 従業員

14 1.4 ソーティング 問題1.1 ドリル穴あけ問題(Drilling Problem)
1.4　ソーティング 問題1.1 ドリル穴あけ問題(Drilling Problem) インスタンス: 平面上のn個の点　 𝑝 1 ,…, 𝑝 𝑛 ∈ 𝑅 𝑛 タスク: 𝑛=1 𝑛−1 𝑑 𝑝 𝜋 𝑖 , 𝑝 𝜋 𝑖+1 が最小となるような順列 𝜋: 1,…,𝑛 → 1,…,𝑛 もし、直線上にn個の点があったら…　　　端から順に穴をあければよい つまり… 与えられたn個の点を座標順に並び替えればよい

15 1.4 ソーティング マージソートアルゴリズム アルゴリズム1.2 マージソートアルゴリズム (Merge-Sort Algorithm)
1.4　ソーティング マージソートアルゴリズム アルゴリズム1.2　マージソートアルゴリズム (Merge-Sort Algorithm) 入力: 　　n個の実数のリスト 𝑎 1 ,…, 𝑎 𝑛 出力: 　　すべての𝑖=1,…,𝑛−1で 𝑎 𝜋 𝑖 ≤ 𝑎 𝜋 𝑖+1 を満たす 置換𝜋: 1,…,𝑛 → 1,…,𝑛 8,2,1,5,6,4,3,7 8,2,1,5 6,4,3,7 分割 8,2 1,5 6,4 3,7 8 2 1 5 6 4 3 7

16 1.4 ソーティング マージソートアルゴリズム アルゴリズム1.2 マージソートアルゴリズム (Merge-Sort Algorithm)
1.4　ソーティング マージソートアルゴリズム アルゴリズム1.2　マージソートアルゴリズム (Merge-Sort Algorithm) 入力: 　　n個の実数のリスト 𝑎 1 ,…, 𝑎 𝑛 出力: 　　すべての𝑖=1,…,𝑛−1で 𝑎 𝜋 𝑖 ≤ 𝑎 𝜋 𝑖+1 を満たす 置換𝜋: 1,…,𝑛 → 1,…,𝑛 8,2,1,5,6,4,3,7 6,4,3,7 2,8 1,5 4,6 3,7 統治 8 2 1 5 6 4 3 7

17 1.4 ソーティング マージソートアルゴリズム アルゴリズム1.2 マージソートアルゴリズム (Merge-Sort Algorithm)
1.4　ソーティング マージソートアルゴリズム アルゴリズム1.2　マージソートアルゴリズム (Merge-Sort Algorithm) 入力: 　　n個の実数のリスト 𝑎 1 ,…, 𝑎 𝑛 出力: 　　すべての𝑖=1,…,𝑛−1で 𝑎 𝜋 𝑖 ≤ 𝑎 𝜋 𝑖+1 を満たす 置換𝜋: 1,…,𝑛 → 1,…,𝑛 8,2,1,5,6,4,3,7 1 6,4,3,7 2,8 5 4,6 3,7 統治 8 2 1 5 6 4 3 7

18 1.4 ソーティング マージソートアルゴリズム アルゴリズム1.2 マージソートアルゴリズム (Merge-Sort Algorithm)
1.4　ソーティング マージソートアルゴリズム アルゴリズム1.2　マージソートアルゴリズム (Merge-Sort Algorithm) 入力: 　　n個の実数のリスト 𝑎 1 ,…, 𝑎 𝑛 出力: 　　すべての𝑖=1,…,𝑛−1で 𝑎 𝜋 𝑖 ≤ 𝑎 𝜋 𝑖+1 を満たす 置換𝜋: 1,…,𝑛 → 1,…,𝑛 8,2,1,5,6,4,3,7 1,2 6,4,3,7 8 5 4,6 3,7 統治 8 2 1 5 6 4 3 7

19 1.4 ソーティング マージソートアルゴリズム アルゴリズム1.2 マージソートアルゴリズム (Merge-Sort Algorithm)
1.4　ソーティング マージソートアルゴリズム アルゴリズム1.2　マージソートアルゴリズム (Merge-Sort Algorithm) 入力: 　　n個の実数のリスト 𝑎 1 ,…, 𝑎 𝑛 出力: 　　すべての𝑖=1,…,𝑛−1で 𝑎 𝜋 𝑖 ≤ 𝑎 𝜋 𝑖+1 を満たす 置換𝜋: 1,…,𝑛 → 1,…,𝑛 8,2,1,5,6,4,3,7 1,2,5 6,4,3,7 8 4,6 3,7 統治 8 2 1 5 6 4 3 7

20 1.4 ソーティング マージソートアルゴリズム アルゴリズム1.2 マージソートアルゴリズム (Merge-Sort Algorithm)
1.4　ソーティング マージソートアルゴリズム アルゴリズム1.2　マージソートアルゴリズム (Merge-Sort Algorithm) 入力: 　　n個の実数のリスト 𝑎 1 ,…, 𝑎 𝑛 出力: 　　すべての𝑖=1,…,𝑛−1で 𝑎 𝜋 𝑖 ≤ 𝑎 𝜋 𝑖+1 を満たす 置換𝜋: 1,…,𝑛 → 1,…,𝑛 8,2,1,5,6,4,3,7 1,2,5,8 6,4,3,7 計算時間は𝑂 𝑛𝑙𝑜𝑔𝑛 4,6 3,7 統治 8 2 1 5 6 4 3 7

21 第2章　グラフ 2.1 基礎的な定義 2.2 木、閉路、カット 2.3 連結性 2.4 オイラーグラフと2部グラフ 2.5 平面性 2.6 平面的双対性

22 2.1 基礎的な定義 無向グラフ 𝐺= 𝑉,𝐸,Ψ 有向グラフ 𝐺= 𝑉,𝐸,Ψ Ψ:𝐸→ 𝑋⊆𝑉: 𝑋 =2
2.1 基礎的な定義 無向グラフ　𝐺= 𝑉,𝐸,Ψ Ψ:𝐸→ 𝑋⊆𝑉: 𝑋 =2 有向グラフ　𝐺= 𝑉,𝐸,Ψ Ψ:𝐸→ 𝑣,𝑤 ∈𝑉×𝑉:𝑣≠𝑤 Vの要素: 頂点 Eの要素: 辺

23 2.1 基礎的な定義 無向グラフ 𝐺= 𝑉,𝐸,Ψ 有向グラフ 𝐺= 𝑉,𝐸,Ψ Ψ:𝐸→ 𝑋⊆𝑉: 𝑋 =2
2.1 基礎的な定義 無向グラフ　𝐺= 𝑉,𝐸,Ψ Ψ:𝐸→ 𝑋⊆𝑉: 𝑋 =2 有向グラフ　𝐺= 𝑉,𝐸,Ψ Ψ:𝐸→ 𝑣,𝑤 ∈𝑉×𝑉:𝑣≠𝑤 Ψ 𝑒 = Ψ 𝑒′ となる2つの辺は並列である 並列辺をもたないグラフは単純である

24 2.1 基礎的な定義 無向グラフ 𝐺= 𝑉,𝐸,Ψ 有向グラフ 𝐺= 𝑉,𝐸,Ψ Ψ:𝐸→ 𝑋⊆𝑉: 𝑋 =2
2.1 基礎的な定義 無向グラフ　𝐺= 𝑉,𝐸,Ψ Ψ:𝐸→ 𝑋⊆𝑉: 𝑋 =2 有向グラフ　𝐺= 𝑉,𝐸,Ψ Ψ:𝐸→ 𝑣,𝑤 ∈𝑉×𝑉:𝑣≠𝑤 単純グラフについては𝐺= 𝑉 𝐺 ,𝐸 𝐺

25 2.1 基礎的な定義 有向グラフGに対する無向基礎グラフG’ 辺の向きをなくす G G’

26 2.1 基礎的な定義 𝐺= 𝑉 𝐺 ,𝐸 𝐺 に対する部分グラフ𝐻= 𝑉 𝐻 ,𝐸 𝐻 𝑉 𝐻 ⊆𝑉 𝐺 かつ𝐸 𝐻 ⊆𝐸 𝐺
𝐺= 𝑉 𝐺 ,𝐸 𝐺 に対する部分グラフ𝐻= 𝑉 𝐻 ,𝐸 𝐻 𝑉 𝐻 ⊆𝑉 𝐺 かつ𝐸 𝐻 ⊆𝐸 𝐺 𝐸 𝐻 = 𝑥,𝑦 ∈𝐸 𝐺 :𝑥,𝑦∈𝑉 𝐻 を満たすときHはGの誘導部分グラフ(𝐻=𝐺 𝑉 𝐻 と書くこともある) 上のHは誘導部分グラフではない 1 1 2 2 4 4 3 G H

27 2.1 基礎的な定義 𝑉 𝐻 =𝑉 𝐺 のとき、Hは全点であるという
𝑣∈𝑉 𝐺 のとき、 𝑉 𝐺 ∖ 𝑣 で誘導されるGの部分グラフを 𝐺 −𝑣 と表記する 𝑒∈𝐸 𝐺 のとき、 𝐺 −𝑒 を 𝐺 −𝑒 ≔ 𝑉 𝐺 ,𝐸 𝐺 ∖ 𝑒 と表記する 1 1 2 2 4 4 3 3 G H

28 2.1 基礎的な定義 2つのグラフG,Hに対して、G+Hは = + 𝑉 𝐺+𝐻 =𝑉 𝐺 ∪𝑉 𝐻 𝐸 𝐺+𝐻 は𝐸 𝐺 と𝐸 𝐻 の直和
4 4 5 3 5 3

29 2.1 基礎的な定義 2つの無向グラフGとHに対して、（有向も同様） 全単射 Φ 𝑉 :𝑉 𝐺 →𝑉 𝐻 と Φ 𝐸 :𝐸 𝐺 →𝐸 𝐻 が
2.1 基礎的な定義 2つの無向グラフGとHに対して、（有向も同様） 全単射 Φ 𝑉 :𝑉 𝐺 →𝑉 𝐻 と Φ 𝐸 :𝐸 𝐺 →𝐸 𝐻 が 　存在して、すべての 𝑣,𝑤 ∈𝐸 𝐺 で Φ 𝐸 𝑣,𝑤 = Φ 𝑉 𝑣,𝑤 , Φ 𝑉 𝑣,𝑤 　となるとき、GとHは同形であるという 1 2 a b 1→a 2→b 3→f 4→d 5→e 6→c 6 3 f c e d 5 4

30 2.1 基礎的な定義 無向グラフGと𝑋⊆𝑉 𝐺 に対して、Xを縮約するとは… Xのすべての点とG[X]のすべての辺を削除 新しい点xを追加
2.1　基礎的な定義 無向グラフGと𝑋⊆𝑉 𝐺 に対して、Xを縮約するとは… Xのすべての点とG[X]のすべての辺を削除 新しい点xを追加 𝑣∈𝑋,𝑤∉𝑋となる各辺 𝑣,𝑤 を辺 𝑥,𝑤 で置き換え 1 x 2 2 4 3 3 G/Xと書くことも X={1,4}

31 2.1 基礎的な定義 グラフGと𝑋,𝑌⊆𝑉 𝐺 に対して、
2.1　基礎的な定義 グラフGと𝑋,𝑌⊆𝑉 𝐺 に対して、 無向グラフ𝐸 𝑋,𝑌 ≔ 𝑥,𝑦 ∈𝐸 𝐺 :𝑥∈𝑋∖𝑌,𝑦∈𝑌∖𝑋 𝑥,𝑦 ∈𝐸 𝐺 :𝑥∈𝑋∖𝑌,𝑦∈𝑌∖𝑋 有向グラフ 𝐸 + 𝑋,𝑌 ≔ 𝑥,𝑦 ∈𝐸 𝐺 :𝑥∈𝑋∖𝑌,𝑦∈𝑌∖𝑋 𝑥,𝑦 ∈𝐸 𝐺 :𝑥∈𝑋∖𝑌,𝑦∈𝑌∖𝑋 1 2 Y X 4 3 𝐸 𝑋,𝑌 = 1,2

32 2.1 基礎的な定義 X 無向グラフGと𝑋⊆𝑉 𝐺 に対して、 𝛿 𝑋 ≔𝐸 𝑋,𝑉 𝐺 ∖𝑋 として、 Γ 𝑋 ≔ 𝑣∈𝑉 𝐺 ∖𝑋:𝐸 𝑋, 𝑣 ≠𝜙 をXの隣接頂点集合という

33 2.1 基礎的な定義 有向グラフGと𝑋⊆𝑉 𝐺 に対して、 𝛿 + 𝑋 ≔ 𝐸 + 𝑋,𝑉 𝐺 ∖𝑋 𝛿 − 𝑋 ≔ 𝛿 + 𝑉 𝐺 ∖𝑋 𝛿 𝑋 ≔ 𝛿 + 𝑋 ⋃ 𝛿 − 𝑋 と定義する 𝛿 + 𝑣 : 出次数 𝛿 − 𝑣 : 入次数

34 2.1 基礎的な定義 k-正則グラフ すべての点の次数がkであるグラフ

35 2.1 基礎的な定義 グラフの次数に関する性質 すべての点の次数の和は枝の数の倍 奇数次数の頂点の数は偶数 入次数の和=出次数の和

36 2.1 基礎的な定義 補題2.1(1) 有向グラフGと任意の2つの集合𝑋,𝑌⊆𝑉 𝐺 に対して、 以下の(a),(b)が成立 (a) (b)
2.1　基礎的な定義 補題2.1(1) 有向グラフGと任意の2つの集合𝑋,𝑌⊆𝑉 𝐺 に対して、 以下の(a),(b)が成立 (a) 𝛿 + 𝑋 + 𝛿 + 𝑌 = 𝛿 + 𝑋⋂𝑌 + 𝛿 + 𝑋⋃𝑌 + 𝐸 + 𝑋,𝑌 + 𝐸 + 𝑌,𝑋 (b) 　 𝛿 − 𝑋 + 𝛿 − 𝑌 = 𝛿 − 𝑋⋂𝑌 + 𝛿 − 𝑋⋃𝑌 + 𝐸 + 𝑋,𝑌 + 𝐸 + 𝑌,𝑋 証明 対称性より片方だけ証明すればよい。(a)を証明する

37 2.1 基礎的な定義 補題2.1(1) 有向グラフGと任意の2つの集合𝑋,𝑌⊆𝑉 𝐺 に対して、 以下の(a),(b)が成立 (a) 証明
2.1　基礎的な定義 補題2.1(1) 有向グラフGと任意の2つの集合𝑋,𝑌⊆𝑉 𝐺 に対して、 以下の(a),(b)が成立 (a) 𝛿 + 𝑋 + 𝛿 + 𝑌 = 𝛿 + 𝑋⋂𝑌 + 𝛿 + 𝑋⋃𝑌 + 𝐸 + 𝑋,𝑌 + 𝐸 + 𝑌,𝑋 証明 𝑍=𝑉 𝐺 ∖ 𝑋⋃𝑌 とする 𝛿 + 𝑋 + 𝛿 + 𝑌 = 𝐸 + 𝑋,𝑍 + 𝐸 + 𝑋,𝑌∖𝑋 + 𝐸 + 𝑌,𝑍 + 𝐸 + 𝑌,𝑋∖𝑌 = 𝐸 + 𝑋∪𝑌,𝑍 + 𝐸 + 𝑋∩𝑌,𝑍 + 𝐸 + 𝑋,𝑌∖𝑋 + 𝐸 + 𝑌,𝑋∖𝑌 = 𝛿 + 𝑋∪𝑌 + 𝛿 + 𝑋∩𝑌 + 𝐸 + 𝑋,𝑌 + 𝐸 + 𝑌,𝑋

38 = 𝐸 + 𝑋,𝑍 + 𝐸 + 𝑋,𝑌∖𝑋 + 𝐸 + 𝑌,𝑍 + 𝐸 + 𝑌,𝑋∖𝑌
証明 𝑍=𝑉 𝐺 ∖ 𝑋⋃𝑌 とする 𝛿 + 𝑋 + 𝛿 + 𝑌 = 𝐸 + 𝑋,𝑍 + 𝐸 + 𝑋,𝑌∖𝑋 + 𝐸 + 𝑌,𝑍 + 𝐸 + 𝑌,𝑋∖𝑌 = 𝐸 + 𝑋∪𝑌,𝑍 + 𝐸 + 𝑋∩𝑌,𝑍 + 𝐸 + 𝑋,𝑌∖𝑋 + 𝐸 + 𝑌,𝑋∖𝑌 = 𝛿 + 𝑋∪𝑌 + 𝛿 + 𝑋∩𝑌 + 𝐸 + 𝑋,𝑌 + 𝐸 + 𝑌,𝑋 X Y

39 2.1 基礎的な定義 補題2.1(2) 無向グラフGと任意の2つの集合𝑋,𝑌⊆𝑉 𝐺 に対して、 以下の(c),(d)が成立 (c) (d)
2.1　基礎的な定義 補題2.1(2) 無向グラフGと任意の2つの集合𝑋,𝑌⊆𝑉 𝐺 に対して、 以下の(c),(d)が成立 (c) 𝛿 𝑋 + 𝛿 𝑌 = 𝛿 𝑋⋂𝑌 + 𝛿 𝑋⋃𝑌 +2 𝐸 𝑋,𝑌 (d) Γ 𝑋 + Γ 𝑌 ≥ Γ 𝑋⋂𝑌 + Γ 𝑋⋃𝑌 証明 Γ 𝑋 + Γ 𝑌 = Γ 𝑋∪𝑌 + Γ 𝑋 ∩Γ 𝑌 + Γ 𝑋 ∩𝑌 + 𝑋∩Γ 𝑌 Γ 𝑋∩𝑌 ⊆Γ 𝑋 ∩Γ 𝑌 を用いると(d)は得られる

40 2.1 基礎的な定義 関数𝑓: 2 𝑈 →𝑅（U：有限集合、 2 𝑈 :Uのべき集合）は
2.1 基礎的な定義 関数𝑓: 2 𝑈 →𝑅（U：有限集合、　 2 𝑈 :Uのべき集合）は すべての𝑋,𝑌⊆𝑈で𝑓 𝑋∩𝑌 +𝑓 𝑋∪𝑌 ≤𝑓 𝑋 +𝑓 𝑌 ならば劣モジュラー 𝛿 + , 𝛿 − , 𝛿 , Γ が劣モジュラーである(補題2.1より)ことは 後で用いられる

41 2.1 基礎的な定義 完全グラフ: 任意の頂点間に枝が存在 Gの補グラフH: 無向グラフGに対してG+Hが完全グラフとなるようなH
2.1 基礎的な定義 完全グラフ: 任意の頂点間に枝が存在 Gの補グラフH: 無向グラフGに対してG+Hが完全グラフとなるようなH Gのマッチング: 無向グラフGの頂点を共有しない辺の集合 Gの点カバーS: 点集合𝑆⊆𝑉 𝐺 に対して、Gのどの辺も少なくともSの1点と隣接 Gの安定集合S: Sのどの2点もGで隣接していない GのクリークS: Sのどの2点もGで隣接 Gの辺カバーF: 辺集合𝐹⊆𝐸 𝐺 に対して、Gのどの点も少なくともFの1辺と接続

42 2.1 基礎的な定義 命題2.2 グラフGと𝑋⊆𝑉 𝐺 に対して、以下の命題(a)-(c)は互いに等価である (a) XはGの点カバーである
2.1 基礎的な定義 命題2.2 グラフGと𝑋⊆𝑉 𝐺 に対して、以下の命題(a)-(c)は互いに等価である (a) XはGの点カバーである (b) 𝑉 𝐺 ∖𝑋はGの安定集合である (c) 𝑉 𝐺 ∖𝑋はGの補グラフのクリークである

43 2.1 基礎的な定義 線グラフ 点集合𝐸 𝐺 辺集合𝐹= 𝑒 1 , 𝑒 2 : 𝑒 1 , 𝑒 2 ∈𝐸 𝐺 , 𝑒 1 ∩ 𝑒 2 =1
辺集合𝐹= 𝑒 1 , 𝑒 2 : 𝑒 1 , 𝑒 2 ∈𝐸 𝐺 , 𝑒 1 ∩ 𝑒 2 =1 a a b b c c

44 2.1 基礎的な定義 辺の重複を許すウォーク 3 c 2 d b 4 1 e f a 5 g 7 6 同じ辺通らないものをウォーク
2.1 基礎的な定義 辺の重複を許すウォーク 3 c 2 d b 4 1 e f a 5 g 7 6 同じ辺通らないものをウォーク 始点と終点が同じものを閉ウォーク

45 2.1 基礎的な定義 パス 3 c 2 d b 4 1 e f a 5 g 7 6 同じ頂点をとおらないものをパス 全点パスをハミルトンパス

46 2.1 基礎的な定義 閉路 3 c 2 d b 4 1 e f a 5 g 7 6 閉ウォークで同じ頂点をとおらないものを閉路
2.1 基礎的な定義 閉路 3 c 2 d b 4 1 e f a 5 g 7 6 閉ウォークで同じ頂点をとおらないものを閉路 全点閉路をハミルトン閉路

47 2.2 木、閉路、カット G: 無向グラフ 連結: Gに存在する任意の頂点間にパスが存在 する（そうでないとき非連結）
2.2 木、閉路、カット G: 無向グラフ 連結: Gに存在する任意の頂点間にパスが存在 する（そうでないとき非連結） Gの極大な連結部分グラフをGの連結成分 点集合Xで誘導される部分グラフが連結であるとき、Xは連結であるという

48 2.2 木、閉路、カット 関節点v: 𝐺 −𝑣 の連結成分がGより多くなるよう な点v 連結成分 連結成分 関節点

49 2.2 木、閉路、カット 橋e: 𝐺 −𝑒 の連結成分がGより多くなるよう な辺e 連結成分 連結成分 橋

50 2.2 木、閉路、カット 森: 閉路をもたない無向グラフ 木: 連結な森 葉: 木で次数1の点 スターグラフ: 葉でない点が高々1点である木

51 2.2　木、閉路、カット 命題2.3 (a)無向グラフGが連結であるとき、そしてそのときのみ、 すべての𝜙≠𝑋⊂𝑉 𝐺 に対して、𝛿 𝑋 ≠𝜙である (b)Gを有向グラフとし、𝑟∈𝑉 𝐺 とする。 すべての点𝑣∈𝑉 𝐺 に対してr-v-パスが存在するとき、 そしてそのときのみ、 𝑟∈𝑋となるすべての𝑋⊂𝑉 𝐺 に 対して 𝛿 + 𝑋 ≠𝜙である。 (a)だけ証明

52 2.2　木、閉路、カット 命題2.3 (a)無向グラフGが連結であるとき、そしてそのときのみ、 すべての𝜙≠𝑋⊂𝑉 𝐺 に対して、𝛿 𝑋 ≠𝜙である If exist X s.t.𝛿 𝑋 =𝜙… v r r-v-パスは存在しない。　よって非連結

53 2.2　木、閉路、カット 命題2.3 (a)無向グラフGが連結であるとき、そしてそのときのみ、 すべての𝜙≠𝑋⊂𝑉 𝐺 に対して、𝛿 𝑋 ≠𝜙である もし非連結ならば…あるr,vに対して、r-v-パスが存在しない　 rから到達可能な点をRとすると、𝑟∈𝑅,𝑣∉𝑅かつ𝛿 𝑅 =𝜙が得られる

54 定理2.4の証明 a⇒g 端点のパスが一意でなければ閉路が存在 よって Gが木ならば任意の2点間に唯一のパスが存在

55 定理2.4の証明 g⇒e⇒dは命題2.3から得られる d⇒fは自明である f⇒b⇒c n点m辺p個の連結成分からなる森 n=m+p が成り立つことから得られる

56 定理2.4の証明 c⇒a Gからk本取り除いても連結性を保てたとする。 得られたグラフG’はm=n-1-k本の辺をもつ n=m+p=n-1-k+1より k=0 a⇒g⇒e⇒d⇒f⇒b⇒c⇒aが言えた

57 有向木 有向グラフが連結＝無向基礎グラフが連結 根 有向木 有向木ではない

58 定理2.5の証明 (a)⇒(b)と(c)⇒(d)は定理2.4から成り立つ (b)⇒(c) 根以外の点の入次数は1より、任意のvに対してr-v-パスが得られる(vからrまでの唯一のパスをたどれる) (d)⇒(e) 命題2.3から成立

59 定理2.5の証明 (a)⇒(b)と(c)⇒(d)は定理2.4から成り立つ (b)⇒(c) 根以外の点の入次数は1より、任意のvに対してr-v-パスが得られる(vからrまでの唯一のパスをたどれる) (d)⇒(e) 命題2.3から成立

60 定理2.5の証明 (f)⇒(g)⇒(a) 自明 (e)⇒(f) (e)の極小性からrの入次数は0
命題2.3よりすべてのvに対してr-v-パスが存在 あるvに対して2つのr-v-パスがあったとすると eをとってもどの点もrから到達可能。矛盾 (f)⇒(g)⇒(a)　自明 e

61 カット 𝜙≠𝑋⊂𝑉 𝐺 を用いて𝛿 𝑋 と書ける辺集合 有向の場合は 𝛿 + 𝑋 t s 頂点sとtを分離するカットをs-t-カット

62 無向パス 無向閉路 無向カット それぞれ、無向基礎グラフにおけるパス、閉路、カット

63 補題2.6 Gを有向グラフとし、𝑒∈𝐸 𝐺 とする。eは黒で彩色され、残りの各辺は赤、黒あるいは緑のいずれかで彩色されているとする。このとき、以下の(a)あるいは(b)のいずれかが成立し、両方同時に成立することはない。 (a) eを含み、赤と黒の辺だけからなる無向閉路で、黒い辺はすべて同一の向きをもつようなものが存在する。 (b) eを含み、緑と黒の辺からなる無向カットで、黒い辺はすべて同一の向きを持つようなものが存在する。

64 下のグラフは(a)を満たし、(b)を満たさない
(a)　eを含み、赤と黒の辺だけからなる無向閉路で、黒い辺はすべて同一の向きをもつようなものが存在する。 (b)　eを含み、緑と黒の辺からなる無向カットで、黒い辺はすべて同一の向きを持つようなものが存在する。 下のグラフは(a)を満たし、(b)を満たさない e

65 yから黒い辺と赤い辺(赤い辺は向きを無視)をたどって到達できる点にラベル付け
xがラベル付けされたら(a)を満たす無向閉路を持つ y x e

66 yから黒い辺と赤い辺(赤い辺は向きを無視)をたどって到達できる点にラベル付け
xがラベル付けされなければラベル付けされた頂点集合が(b)を満たす無向カットを構成する y x e

67 (a)を満たす無向閉路と(b)を満たす無向カットに共通する辺は黒
y x e

68 有向グラフの強連結 有向グラフGは、すべての𝑠,𝑡∈𝑉 𝐺 に対してsからtのパスとtからsのパスがあるとき、強連結であるという。 有向グラフの極大な強連結部分グラフを強連結成分という。

69 系2.7 有向グラフGの各辺は、有向閉路あるいは有向カットに含まれる。さらに、以下の(a)-(c)は互いに連結である。 (a) Gは強連結である (b) Gは有向カットを含まない (c) Gは連結で、Gのどの辺も有向閉路に含まれる

70 系2.7 有向グラフGの各辺は、有向閉路あるいは有向カットに含まれる。さらに、以下の(a)-(c)は互いに連結である。 (a) Gは強連結である (b) Gは有向カットを含まない (c) Gは連結で、Gのどの辺も有向閉路に含まれる 命題2.3 (b)Gを有向グラフとし、𝑟∈𝑉 𝐺 とする。すべての点𝑣∈𝑉 𝐺 に対してr-v-パスが存在するとき、そしてそのときのみ、 𝑟∈𝑋となるすべて𝑋⊂𝑉 𝐺 に対して 𝛿 + 𝑋 ≠𝜙である。

71 系2.7(補題2.6の適用) 有向グラフGの各辺は、有向閉路あるいは有向カットに含まれる。さらに、以下の(a)-(c)は互いに連結である。 (a) Gは強連結である (b) Gは有向カットを含まない (c) Gは連結で、Gのどの辺も有向閉路に含まれる

72 系2.7 有向グラフGの各辺は、有向閉路あるいは有向カットに含まれる。さらに、以下の(a)-(c)は互いに連結である。 (a) Gは強連結である (b) Gは有向カットを含まない (c) Gは連結で、Gのどの辺も有向閉路に含まれる X 𝑟∈𝑉 𝐺 ：任意の点 目標：各𝑣∈𝑉 𝐺 に対してr-v-パスが存在 正しくないと仮定 r

73 定義2.8 トポロジカル順序 Gを有向グラフとする。任意の辺 𝑣 𝑖 , 𝑣 𝑗 ∈𝐸 𝐺 に対して、i<jが成立するような点集合𝑉 𝐺 = 𝑣 1 ,…, 𝑣 𝑛 の順序をGのトポロジカル順序という。 1 3 2 5 6 4

74 命題2.9 有向グラフがトポロジカル順序を持つ ⇔ 無閉路(有向閉路を持たない)である 証明(⇒) 対偶は自明 (⇐)辺数に関する帰納法

75 辺𝑒∈𝐸 𝐺 を持つものとする。eはある有向カットに属する
帰納法の仮定から、それぞれの頂点集合から誘導されるグラフにはトポロジカル順序が存在

76 サイクル空間とコサイクル空間 有向グラフGの各無向閉路にベクトルを対応させる 無向閉路を形成する辺に1 or -1(符号は向きに対応)
それ以外の辺に0 𝐶 1 1 2 𝜁 𝐶 1 = 1 − 3 4 6 5 7 8

77 サイクル空間とコサイクル空間 有向グラフGの各無向閉路にベクトルを対応させる 無向閉路を形成する辺に1 or -1(符号は向きに対応)
それ以外の辺に0 無向閉路に対応するベクトルの集合で生成されるベクトル空間の部分空間をサイクル空間という

78 サイクル空間とコサイクル空間 有向グラフGの各無向カットにベクトルを対応させる 無向カットを形成する辺に1 or -1(符号は向きに対応)
それ以外の辺に0 𝐷 1 1 2 𝜁 𝐷 1 = −1 1 0 3 4 6 5 7 8

79 サイクル空間とコサイクル空間 有向グラフGの各無向カットにベクトルを対応させる 無向カットを形成する辺に1 or -1(符号は向きに対応)
それ以外の辺に0 無向カットに対応するベクトルの集合で生成されるベクトル空間の部分空間をコサイクル空間という

80 命題2.10 有向グラフGのサイクル空間とコサイクル空間は直交する D C
任意の閉路Cと任意の無向カットDに対して、𝜁 𝐶 と𝜁 𝐷 のスカラー積が0になることを示す

81 命題2.10 有向グラフGのサイクル空間とコサイクル空間は直交する D C 考慮するべき辺は共通する辺のみ
(他の辺に対応するベクトルの成分はC,Dのどちらかにおいて0となる)

82 命題2.10 有向グラフGのサイクル空間とコサイクル空間は直交する D C 無向カットを有向カットとしてもスカラー積の値に影響を与えない
(有向カットの非零成分の符号はすべて一致すると考えても一般性を失わない)

83 命題2.10 有向グラフGのサイクル空間とコサイクル空間は直交する D C 閉路を考えると、 Dに入る辺の数＝Dから出る辺の数
つまり、ベクトルにおいて、 1となる成分の数＝0となる成分の数

84 サイクル基底 コサイクル基底 無向閉路の集合は、対応するベクトルの集合がサイクル空間の基底となるとき、サイクル基底と呼ばれる 無向カットの集合は、対応するベクトルの集合がコサイクル空間の基底となるとき、コサイクル基底と呼ばれる。

85 基本閉路と基本カット Gをグラフ、Tを無向閉路を含まないGの極大な部分グラフとする
各𝑒∈𝐸 𝐺 ∖𝐸 𝑇 に対して、T+eに含まれる唯一の無向閉路をTに関するeの基本閉路という e

86 基本閉路と基本カット Gをグラフ、Tを無向閉路を含まないGの極大な部分グラフとする
各𝑒∈𝐸 𝑇 に対して、 𝛿 𝐺 𝑋 ∩𝐸 𝑇 = 𝑒 となる集合𝑋⊆𝑉 𝐺 が存在する。 𝛿 𝐺 𝑋 をTに関するeの基本カットという X e

87 定理2.11 Gを有向グラフ、Tを無向閉路を持たないGの極大な部分グラフとする。 Tに関する 𝐸 𝐺 ∖𝐸 𝑇 個の𝐸 𝐺 ∖𝐸 𝑇 の辺の基本閉路の集合はGのサイクル基底となる。 Tに関する 𝐸 𝑇 個の𝐸 𝑇 の辺の基本カットの集合はコサイクル基底となる。 各基本閉路は他の基本閉路に含まれない辺eを含むので、基本閉路に対応する 𝐸 𝐺 ∖𝐸 𝑇 個のベクトルは線形独立 基本カットに対応する 𝐸 𝑇 個のベクトルに対しても同様 2つのベクトル空間は互いに直交するので、次元の和は 𝐸 𝐺

88 T: 無向基礎グラフが木となる有向グラフ 𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を 𝐶 𝑒 として、族𝐹≔ 𝐶 𝑒 :𝑒∈𝐸 𝑇 を考える
1 2 3

89 T: 無向基礎グラフが木となる有向グラフ 𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を 𝐶 𝑒 として、族𝐹≔ 𝐶 𝑒 :𝑒∈𝐸 𝑇 を考える
1 2 3 𝐶 1

90 T: 無向基礎グラフが木となる有向グラフ 𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を 𝐶 𝑒 として、族𝐹≔ 𝐶 𝑒 :𝑒∈𝐸 𝑇 を考える
𝐶 2 1 2 3 𝐶 1

91 T: 無向基礎グラフが木となる有向グラフ 𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を 𝐶 𝑒 として、族𝐹≔ 𝐶 𝑒 :𝑒∈𝐸 𝑇 を考える
𝐶 2 1 2 3 𝐶 3 𝐶 1

92 T: 無向基礎グラフが木となる有向グラフ 𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を 𝐶 𝑒 として、族𝐹≔ 𝐶 𝑒 :𝑒∈𝐸 𝑇 を考える
もしTが有向木ならばFの任意の2要素は共通部分を持たないか、あるいは一方が他方に含まれるかである 1 2 3 𝐶 3 𝐶 2 𝐶 1

93 定義2.12 集合システム 空でない有限集合UとUの部分集合の族Fの対(U,F)は集合システムと呼ばれる。 任意の2つの集合X,Yに対して 𝑋∖𝑌,𝑌∖𝑋,𝑋⋂𝑌,𝑈∖ 𝑋⋃𝑌 のいずれかが空⇒クロスフリー (どのX,Yを見ても、一方が他方を含んでいる、共通する要素がない、すべての要素をカバーする、のいずれかを満たす) 𝑋∖𝑌,𝑌∖𝑋,𝑋⋂𝑌のいずれかが空⇒ラミナー (どのX,Yを見ても、一方が他方を含んでいる、共通する要素がない、のいずれかを満たす)

94 T: 無向基礎グラフが木となる有向グラフ 𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を 𝐶 𝑒 として、族𝐹≔ 𝐶 𝑒 :𝑒∈𝐸 𝑇 を考える
𝐶 2 1 クロスフリー族 2 3 𝐶 3 𝐶 1

95 T: 無向基礎グラフが木となる有向グラフ 𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を 𝐶 𝑒 として、族𝐹≔ 𝐶 𝑒 :𝑒∈𝐸 𝑇 を考える
もしTが有向木ならばFの任意の2要素は共通部分を持たないか、あるいは一方が他方に含まれるかである 1 ラミナー族 2 3 𝐶 3 𝐶 2 𝐶 1

96 定義から、 集合システム 𝑈,𝐹 がクロスフリーであることと、任意の𝑟∈𝑋に対して、 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋 がラミナー族であることは等価であることが得られる

97 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋
r 𝐶 2 1 クロスフリー族 2 3 𝐶 3 𝐶 1

98 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋
r 𝐶 2 1 2 3 𝐶 3 𝐶 1

99 定義2.13 Tを無向基礎グラフが木となる有向グラフとする。 Uを有限集合とし、𝜑:𝑈→𝑉 𝑇 とする。 𝑒= 𝑥,𝑦 に対して、 𝑆 𝑒 ≔ 𝑠∈𝑈: 𝜑 𝑠 と𝑦は𝑇−𝑒の同じ連結成分に属する と定義して、 𝐹≔ 𝑆 𝑒 :𝑒∈𝐸 𝑇 とする。このとき、 𝑇,𝜑 を 𝑈,𝐹 の木表現という。

100 クロスフリー族 𝑏,𝑐,𝑑,𝑒,𝑓 , 𝑐 , 𝑎,𝑏,𝑐 , 𝑒 , 𝑎,𝑏,𝑐,𝑒,𝑓 , 𝑒,𝑓 の木表現
d それぞれの辺の先にある頂点集合は、族の1つの要素に対応する b f a c e

101 クロスフリー族 𝑏,𝑐,𝑑,𝑒,𝑓 , 𝑐 , 𝑎,𝑏,𝑐 , 𝑒 , 𝑎,𝑏,𝑐,𝑒,𝑓 , 𝑒,𝑓 の木表現
d それぞれの辺の先にある頂点集合は、族の1つの要素に対応する b f a c e

102 クロスフリー族 𝑏,𝑐,𝑑,𝑒,𝑓 , 𝑐 , 𝑎,𝑏,𝑐 , 𝑒 , 𝑎,𝑏,𝑐,𝑒,𝑓 , 𝑒,𝑓 の木表現
d それぞれの辺の先にある頂点集合は、族の1つの要素に対応する b f a c e

103 命題2.14 𝑈,𝐹 は木表現 𝑇,𝜑 をもつ集合システムであるとすると、 𝑈,𝐹 はクロスフリーである Tが有向木ならばラミナーである クロスフリーは木表現可能 ラミナー族は有向木で木表現可能

104 命題2.14 𝑈,𝐹 は木表現 𝑇,𝜑 をもつ集合システムであるとすると、 𝑈,𝐹 はクロスフリーである Tが有向木ならばラミナーである クロスフリーは木表現可能 ラミナー族は有向木で木表現可能

105 𝑇,𝜑 : 𝑈,𝐹 の木表現 𝑒= 𝑣,𝑤 ,𝑓= 𝑥,𝑦 ∈𝐸 𝑇 とすると、Tの無向v-x-パスPが得られる (a)𝑤,𝑦∉𝑉 𝑃 (b) 𝑤∉𝑉 𝑃 かつ𝑦∈𝑉 𝑃 (c)𝑦∉𝑉 𝑃 かつ𝑤∈𝑉 𝑃 (d) 𝑤,𝑦∈𝑉 𝑃 の4通りが考えられる

106 𝑇,𝜑 : 𝑈,𝐹 の木表現 𝑒= 𝑣,𝑤 ,𝑓= 𝑥,𝑦 ∈𝐸 𝑇 とすると、Tの無向v-x-パスPが得られる (a)𝑤,𝑦∉𝑉 𝑃 (b) 𝑤∉𝑉 𝑃 かつ𝑦∈𝑉 𝑃 (c)𝑦∉𝑉 𝑃 かつ𝑤∈𝑉 𝑃 (d) 𝑤,𝑦∈𝑉 𝑃 w v x y 𝑆 𝑒 ∩ 𝑆 𝑓 =∅ e f 𝑆 𝑒 𝑆 𝑓

107 𝑇,𝜑 : 𝑈,𝐹 の木表現 𝑒= 𝑣,𝑤 ,𝑓= 𝑥,𝑦 ∈𝐸 𝑇 とすると、Tの無向v-x-パスPが得られる (a)𝑤,𝑦∉𝑉 𝑃 (b) 𝑤∉𝑉 𝑃 かつ𝑦∈𝑉 𝑃 (c)𝑦∉𝑉 𝑃 かつ𝑤∈𝑉 𝑃 (d) 𝑤,𝑦∈𝑉 𝑃 w v y x 𝑆 𝑒 ⊆ 𝑆 𝑓 (c)の場合は 𝑆 𝑓 ⊆ 𝑆 𝑒 e f 𝑆 𝑒 𝑆 𝑓

108 𝑇,𝜑 : 𝑈,𝐹 の木表現 𝑒= 𝑣,𝑤 ,𝑓= 𝑥,𝑦 ∈𝐸 𝑇 とすると、Tの無向v-x-パスPが得られる (a)𝑤,𝑦∉𝑉 𝑃 (b) 𝑤∉𝑉 𝑃 かつ𝑦∈𝑉 𝑃 (c)𝑦∉𝑉 𝑃 かつ𝑤∈𝑉 𝑃 (d) 𝑤,𝑦∈𝑉 𝑃 v w y x 𝑆 𝑒 ∪ 𝑆 𝑓 =𝑈 Tが有向木ならばこのパターンは起こりえない。 その場合はラミナー族 e f 𝑆 𝑓 𝑆 𝑒

109 命題2.14 𝑈,𝐹 は木表現 𝑇,𝜑 をもつ集合システムであるとすると、 𝑈,𝐹 はクロスフリーである Tが有向木ならばラミナーである クロスフリーは木表現可能 ラミナー族は有向木で木表現可能

110 F: ラミナー族 𝑉 𝑇 ≔𝐹∪ 𝑟 𝐸 ′ ≔ 𝑋,𝑌 ∈𝐹×𝐹:𝑋⊃𝑌≠∅かつ𝑋⊃𝑍⊃𝑌となる𝑍が存在しない
𝐸 ′ ≔ 𝑋,𝑌 ∈𝐹×𝐹:𝑋⊃𝑌≠∅かつ𝑋⊃𝑍⊃𝑌となる𝑍が存在しない 𝐸 𝑇 ≔𝐸′∪ 𝑟,𝑋 :𝑋は𝐹の極大要素 Fが空集合を含むならば、任意の極小集合Xに(X,Φ)を追加 各x∈𝑈に対して、xを含む極小集合Xを用いて 𝜑 𝑥 =𝑋 xを含む集合がないときは 𝜑 𝑥 =𝑟 として𝜑を定義 Tはrを根とする有向木 r X Y

111 F: クロスフリー族 𝑟∈𝑈とすると、 はラミナー族 𝑈,𝐹 の木表現を 𝑇,𝜑 とする 各辺𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して 𝑆 𝑒 ∈𝐹′ 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∉𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∉𝐹 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋

112 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋
F: クロスフリー族 𝑟∈𝑈とすると、 はラミナー族 𝑈,𝐹 の木表現を 𝑇,𝜑 とする 各辺𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して 𝑆 𝑒 ∈𝐹′ 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∉𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∉𝐹 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋 𝑈∖ 𝑆 𝑒 𝑆 𝑒 e

113 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋
F: クロスフリー族 𝑟∈𝑈とすると、 はラミナー族 𝑈,𝐹 の木表現を 𝑇,𝜑 とする 各辺𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して 𝑆 𝑒 ∈𝐹′ 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∉𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∉𝐹 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋 𝑈∖ 𝑆 𝑒 𝑆 𝑒 z

114 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋
F: クロスフリー族 𝑟∈𝑈とすると、 はラミナー族 𝑈,𝐹 の木表現を 𝑇,𝜑 とする 各辺𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して 𝑆 𝑒 ∈𝐹′ 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∉𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∉𝐹 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋 𝑈∖ 𝑆 𝑒 𝑆 𝑒 e

115 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋
F: クロスフリー族 𝑟∈𝑈とすると、 はラミナー族 𝑈,𝐹 の木表現を 𝑇,𝜑 とする 各辺𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して 𝑆 𝑒 ∈𝐹′ 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∉𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∉𝐹 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋 𝑈∖ 𝑆 𝑒 𝑆 𝑒 e

116 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋
F: クロスフリー族 𝑟∈𝑈とすると、 はラミナー族 𝑈,𝐹 の木表現を 𝑇,𝜑 とする 各辺𝑒= 𝑥,𝑦 ∈𝐸 𝑇 に対して 𝑆 𝑒 ∈𝐹′ 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∉𝐹かつ𝑈∖ 𝑆 𝑒 ∈𝐹 𝑆 𝑒 ∈𝐹かつ𝑈∖ 𝑆 𝑒 ∉𝐹 𝐹 ′ ≔ 𝑋∈𝐹:𝑟∉𝑋 ∪ 𝑈∖𝑋:𝑋∈𝐹,𝑟∈𝑋 𝑈∖ 𝑆 𝑒 𝑆 𝑒 e

117 系2.15 Uの異なる部分集合の… ラミナー族は高々2|U|個の要素しか含まない クロスフリー族は高々4|U|-2個の要素しか含まない
非空真部分集合のラミナー族F 命題2.14における構成法では… 異なる部分集合の数=枝の数=頂点数-1 各頂点に対して 出次数が2以上である or ラベル付けされる ラベル付けされる頂点の数は高々|U|個 出次数が2以上となるのは高々 𝐸 𝑇 2 𝐸 𝑇 +1= 𝑉 𝑇 ≤ 𝑈 + 𝐸 𝑇 2 𝐹 = 𝐸 𝑇 ≤2 𝑈 −2 空集合とUを合わせると…

118 系2.15 Uの異なる部分集合の… ラミナー族は高々2|U|個の要素しか含まない クロスフリー族は高々4|U|-2個の要素しか含まない
非空真部分集合のクロスフリー族F Fの変換により得られるラミナー族F’ 𝐹 ≤2 𝐹 ′ ≤4 𝑈 −4 空集合とUを合わせると…