11_22

組合せ最適化第1,2章
M2
酒井隆行
第1章はじめに
様々な実際的な問題
抽象的な最適化問題
第1章はじめに
様々な実際的な問題
抽象的な最適化問題
例えば…
第1章はじめに
最適化問題の例1
なるべく早く、ドリルで板の複数個の位置に穴をあけたい
（移動は等速）
問題1.1 ドリル穴あけ問題(Drilling Problem)
インスタンス: 平面上のn個の点 𝑝1 , … , 𝑝𝑛 ∈ 𝑅𝑛
タスク: 𝑛−1
𝑛=1 𝑑 𝑝𝜋 𝑖 , 𝑝𝜋 𝑖+1 が最小となるような順列
𝜋: 1, … , 𝑛 → 1, … , 𝑛
第1章はじめに
最適化問題の例1
• 各従業員にジョブを割り振る
• 担当可能なジョブは従業員ごとに異なる
• 処理能力の差はない
• 同一のジョブに対して、同時に複数の従業員が担当可
• 従業員は複数のジョブを担当可(同時には不可)
早く終わらせたい
問題1.2 ジョブ割当問題(Job Assignment Probrem)
インスタンス: n個の非負実数𝑡1 , … , 𝑡𝑛 ∈ 𝑅+ (ジョブの処理時間)
m人の従業員と各ジョブ𝑖 ∈ 1, … , 𝑛 に対する担当可な従業員
の部分集合𝑆𝑖 ∈ 1, … , 𝑚
タスク: 各𝑖 = 1, … , 𝑛で 𝑗∈𝑆𝑖 𝑥𝑖,𝑗 = 𝑡𝑖 を満たす𝑥𝑖𝑗 ∈ 𝑅+ 𝑖 = 1, … , 𝑛, 𝑗 ∈ 𝑆𝑖 の
うちで、 max
𝑖:𝑗∈𝑆𝑖 𝑥𝑖𝑗 が最小となるような𝑥𝑖𝑗 ∈ 𝑅+ を求める
𝑗∈ 1,…,𝑚
1.1 列挙
問題1.1 ドリル穴あけ問題(Drilling Problem)
インスタンス: 平面上のn個の点 𝑝1 , … , 𝑝𝑛 ∈ 𝑅𝑛
タスク: 𝑛−1
𝑛=1 𝑑 𝑝𝜋 𝑖 , 𝑝𝜋 𝑖+1 が最小となるような順列
𝜋: 1, … , 𝑛 → 1, … , 𝑛
最適解を計算するアルゴリズムは…?
順列を全列挙すると最適解は見つかる
1.1 列挙
アルゴリズム1.1 パス列挙アルゴリズム
(Path Enumeration Algorithm)
入力: 自然数𝑛 ≥ 3と平面上のn個の点の集合 𝑝1 , … , 𝑝𝑛
出力: パスの長さ 𝑐𝑜𝑠𝑡 𝜋 ∗ ≔ 𝑛−1
が最小とな
𝑖=1 𝑑 𝑝𝜋∗ 𝑖 , 𝑝𝜋∗ 𝑖+1
る順列 𝜋 ∗ : 1, … , 𝑛 → 1, … , 𝑛
(疑似コード略)
順列を、辞書式順に小さいものから順に調べて、
costの最も小さいものを保存
O 𝑛2 𝑛! （解析は甘い）
もっと高速なアルゴリズムは…?
1.2 アルゴリズムの計算時間
アルゴリズムの入力 = 数のリスト
数がすべて整数ならば、2進数表現でコード化可能
有理数は分母と分子を別々にコード化
有理数データからなるインスタンスxに対して、
入力サイズ𝑠𝑖𝑧𝑒 𝑥 = すべての数の2進数表現に必要なビット数
1.2 アルゴリズムの計算時間
定義1.3
A：集合Xの要素を入力として受け取るアルゴリズム
𝑓: 𝑁 → 𝑅+
ある定数𝛼 > 0が存在して、任意の入力𝑥 ∈ 𝑋に対して Aがその計算を高々
𝛼𝑓 𝑠𝑖𝑧𝑒 𝑥 回の初等的操作で終了するならば
Aは𝑶 𝒇 時間で走る or Aの計算時間は𝑶 𝒇 であるという
1.2 アルゴリズムの計算時間
定義1.4
有理数入力に対するアルゴリズム
ある整数kが存在して、入力サイズnのどの入力に対しても、
𝑂 𝑛𝑘 時間で走り、計算の途中で生じる数もすべて𝑂 𝑛𝑘 ビットで記憶
で
きるとき、多項式時間で走るという
任意の入力に対するアルゴリズム
ある整数kが存在して、n個の数のどの入力に対しても𝑂 𝑛𝑘 時
間
で走り、有理数入力に対しても多項式時間で走るとき、強多項式
時間で走るという
k=1のときは線形時間アルゴリズムという
1.3 線形の最適化問題
問題1.2 ジョブ割当問題(Job Assignment Probrem)
インスタンス: n個の非負実数𝑡1 , … , 𝑡𝑛 ∈ 𝑅+ (ジョブの処理時間)
m人の従業員と各ジョブ𝑖 ∈ 1, … , 𝑛 に対する担当可な従業員
の部分集合𝑆𝑖 ∈ 1, … , 𝑚
タスク: 各𝑖 = 1, … , 𝑛で 𝑗∈𝑆𝑖 𝑥𝑖,𝑗 = 𝑡𝑖 を満たす𝑥𝑖𝑗 ∈ 𝑅+ 𝑖 = 1, … , 𝑛, 𝑗 ∈ 𝑆𝑖 の
うちで、 max
𝑖:𝑗∈𝑆𝑖 𝑥𝑖𝑗 が最小となるような𝑥𝑖𝑗 ∈ 𝑅+ を求める
𝑗∈ 1,…,𝑚
ジョブが完了する時刻Tを用いて、線形計画問題として定式化可能
𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒
𝑠. 𝑡
𝑇
𝑗∈𝑆𝑖 𝑥𝑖𝑗
=𝑡
(𝑖 ∈ 1, … , 𝑛 )
𝑥𝑖𝑗 ≥ 0
(𝑖 ∈ 1, … , 𝑛 ,𝑗 ∈ 𝑆𝑖 )
𝑖:𝑗∈𝑆𝑖 𝑥𝑖𝑗 ≤ 𝑇 (𝑖 ∈ 1, … , 𝑛 )
1.3 線形の最適化問題
𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒
𝑠. 𝑡
𝑇
𝑗∈𝑆𝑖 𝑥𝑖𝑗
=𝑡
(𝑖 ∈ 1, … , 𝑛 )
𝑥𝑖𝑗 ≥ 0
(𝑖 ∈ 1, … , 𝑛 ,𝑗 ∈ 𝑆𝑖 )
𝑖:𝑗∈𝑆𝑖 𝑥𝑖𝑗 ≤ 𝑇 (𝑖 ∈ 1, … , 𝑛 )
すべての実行可能解の集合は多面体と呼ばれ、凸であることがわかる。
最適解が存在するならば、必ず多面体の頂点のいずれかが最適解となる
列挙よりもいい方法がある(後の章で)
集合𝑆𝑖 をグラフでモデル化すると…
各ジョブiと各従業員jに対して頂点を考える
ジョブと、そのジョブを担当できる従業員を結ぶ
多くの組合せ最適化問題はグラフ理論を用いて定式化される
1.3 線形の最適化問題
便宜上、
どのジョブも処理時間は1時間
1時間でジョブを全部完了できるか
という問題を考えると…
ジョブ
従業員
すべてのiとjに対して 0 ≤ 𝑥𝑖𝑗 ≤ 1
各𝑖 = 1, … , 𝑛に対して
𝑗∈𝑆𝑖 𝑥𝑖𝑗 = 1
各j = 1, … , 𝑚 に対して
𝑖:𝑗∈𝑆𝑖 𝑥𝑖𝑗 ≤ 1
となるような 𝑥𝑖𝑗 を求める問題になる
解が存在するならば整数解も存在（すべてのiとjに対して𝑥𝑖𝑗 = 0 𝑜𝑟 1）
よって
各ジョブを1人の従業員に割り当て、かつどの従業員も2個以上ジョブが割り当て
られないように割り当てることと等価
グラフ的には、すべてのジョブをカバーするマッチングを求めればよい
1.4 ソーティング
問題1.1 ドリル穴あけ問題(Drilling Problem)
インスタンス: 平面上のn個の点 𝑝1 , … , 𝑝𝑛 ∈ 𝑅𝑛
タスク: 𝑛−1
𝑛=1 𝑑 𝑝𝜋 𝑖 , 𝑝𝜋 𝑖+1 が最小となるような順列
𝜋: 1, … , 𝑛 → 1, … , 𝑛
もし、直線上にn個の点があったら…
端から順に穴をあければよい
つまり…
与えられたn個の点を座標順に並び替えればよい
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
8
1,5
2
1
6,4
5
6
3,7
4
3
7
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
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
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
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
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
第2章グラフ
2.1
2.2
2.3
2.4
2.5
2.6
基礎的な定義
木、閉路、カット
連結性
オイラーグラフと2部グラフ
平面性
平面的双対性
2.1 基礎的な定義
• 無向グラフ 𝐺 = 𝑉, 𝐸, Ψ
– Ψ: 𝐸 → 𝑋 ⊆ 𝑉: 𝑋 = 2
• 有向グラフ 𝐺 = 𝑉, 𝐸, Ψ
– Ψ: 𝐸 →
𝑣, 𝑤 ∈ 𝑉 × 𝑉: 𝑣 ≠ 𝑤
Vの要素: 頂点
Eの要素: 辺
2.1 基礎的な定義
• 無向グラフ 𝐺 = 𝑉, 𝐸, Ψ
– Ψ: 𝐸 → 𝑋 ⊆ 𝑉: 𝑋 = 2
• 有向グラフ 𝐺 = 𝑉, 𝐸, Ψ
– Ψ: 𝐸 →
𝑣, 𝑤 ∈ 𝑉 × 𝑉: 𝑣 ≠ 𝑤
Ψ 𝑒 = Ψ 𝑒′ となる2つの辺は並列である
並列辺をもたないグラフは単純である
2.1 基礎的な定義
• 無向グラフ 𝐺 = 𝑉, 𝐸, Ψ
– Ψ: 𝐸 → 𝑋 ⊆ 𝑉: 𝑋 = 2
• 有向グラフ 𝐺 = 𝑉, 𝐸, Ψ
– Ψ: 𝐸 →
𝑣, 𝑤 ∈ 𝑉 × 𝑉: 𝑣 ≠ 𝑤
単純グラフについては𝐺 = 𝑉 𝐺 , 𝐸 𝐺
2.1 基礎的な定義
• 有向グラフGに対する無向基礎グラフG’
辺の向きをなくす
G
G’
2.1 基礎的な定義
• 𝐺 = 𝑉 𝐺 , 𝐸 𝐺 に対する部分グラフ𝐻 = 𝑉 𝐻 , 𝐸 𝐻
• 𝑉 𝐻 ⊆ 𝑉 𝐺 かつ𝐸 𝐻 ⊆ 𝐸 𝐺
1
1
2
4
2
4
3
G
H
• 𝐸 𝐻 = 𝑥, 𝑦 ∈ 𝐸 𝐺 : 𝑥, 𝑦 ∈ 𝑉 𝐻 を満たすときHはGの誘導部分
グラフ(𝐻 = 𝐺 𝑉 𝐻 と書くこともある)
– 上のHは誘導部分グラフではない
2.1 基礎的な定義
•
𝑉 𝐻 = 𝑉 𝐺 のとき、Hは全点であるという
1
1
2
4
2
4
3
G
3
H
•
𝑣 ∈ 𝑉 𝐺 のとき、 𝑉 𝐺 ∖ 𝑣 で誘導されるGの部分グラフ
を𝐺−𝑣 と表記する
•
𝑒 ∈ 𝐸 𝐺 のとき、 𝐺−𝑒 を𝐺−𝑒 ≔ 𝑉 𝐺 , 𝐸 𝐺 ∖ 𝑒 と表記
する
2.1 基礎的な定義
• 2つのグラフG,Hに対して、G+Hは
–𝑉 𝐺+𝐻 =𝑉 𝐺 ∪𝑉 𝐻
– 𝐸 𝐺 + 𝐻 は𝐸 𝐺 と𝐸 𝐻 の直和
1
1
1
2
4
3
+
2
5
=
2
4
3
5
2.1 基礎的な定義
• 2つの無向グラフGとHに対して、（有向も同様）
– 全単射Φ𝑉 : 𝑉 𝐺 → 𝑉 𝐻 とΦ𝐸 : 𝐸 𝐺 → 𝐸 𝐻 が
存在して、すべての 𝑣, 𝑤 ∈ 𝐸 𝐺 で
Φ𝐸 𝑣, 𝑤 = Φ𝑉 𝑣, 𝑤 , Φ𝑉 𝑣, 𝑤
となるとき、GとHは同形であるという
1
2
3
6
5
4
1→a
2→b
3→f
4→d
5→e
6→c
a
b
f
c
e
d
2.1 基礎的な定義
• 無向グラフGと𝑋 ⊆ 𝑉 𝐺 に対して、Xを縮約する
とは…
– Xのすべての点とG[X]のすべての辺を削除
– 新しい点xを追加
– 𝑣 ∈ 𝑋, 𝑤 ∉ 𝑋となる各辺 𝑣, 𝑤 を辺 𝑥, 𝑤 で置き換え
1
x
2
2
4
3
X={1,4}
3
G/Xと書くことも
2.1 基礎的な定義
• グラフGと𝑋, 𝑌 ⊆ 𝑉 𝐺 に対して、
– 無向グラフ𝐸 𝑋, 𝑌 ≔
1
𝑥, 𝑦 ∈ 𝐸 𝐺 : 𝑥 ∈ 𝑋 ∖
2
Y
X
4
3
𝐸 𝑋, 𝑌 = 1,2
2.1 基礎的な定義
X
無向グラフGと𝑋 ⊆ 𝑉 𝐺 に対して、
𝛿 𝑋 ≔ 𝐸 𝑋, 𝑉 𝐺 ∖ 𝑋
として、
Γ 𝑋 ≔ 𝑣 ∈ 𝑉 𝐺 ∖ 𝑋: 𝐸 𝑋, 𝑣
をXの隣接頂点集合という
≠𝜙
2.1 基礎的な定義
有向グラフGと𝑋 ⊆ 𝑉 𝐺 に対して、
𝛿 + 𝑋 ≔ 𝐸 + 𝑋, 𝑉 𝐺 ∖ 𝑋
𝛿− 𝑋 ≔ 𝛿+ 𝑉 𝐺 ∖ 𝑋
𝛿 𝑋 ≔ 𝛿+ 𝑋 ⋃ 𝛿− 𝑋
と定義する
𝛿 + 𝑣 : 出次数
𝛿 − 𝑣 : 入次数
2.1 基礎的な定義
• k-正則グラフ
– すべての点の次数がkであるグラフ
2.1 基礎的な定義
• グラフの次数に関する性質
– すべての点の次数の和は枝の数の倍
• 奇数次数の頂点の数は偶数
– 入次数の和=出次数の和
2.1 基礎的な定義
補題2.1(1)
有向グラフGと任意の2つの集合𝑋, 𝑌 ⊆ 𝑉 𝐺 に対して、
以下の(a),(b)が成立
(a)
𝛿+ 𝑋 + 𝛿+ 𝑌
= 𝛿 + 𝑋⋂𝑌 + 𝛿 + 𝑋⋃𝑌 + 𝐸 + 𝑋, 𝑌 + 𝐸 + 𝑌, 𝑋
(b)
𝛿− 𝑋 + 𝛿− 𝑌
= 𝛿 − 𝑋⋂𝑌 + 𝛿 − 𝑋⋃𝑌 + 𝐸 + 𝑋, 𝑌 + 𝐸 + 𝑌, 𝑋
証明
対称性より片方だけ証明すればよい。(a)を証明する
2.1 基礎的な定義
補題2.1(1)
有向グラフGと任意の2つの集合𝑋, 𝑌 ⊆ 𝑉 𝐺 に対して、
以下の(a),(b)が成立
(a)
𝛿+ 𝑋 + 𝛿+ 𝑌
証明
𝑍=𝑉
𝛿+ 𝑋
= 𝐸+
= 𝐸+
= 𝛿+
= 𝛿 + 𝑋⋂𝑌 + 𝛿 + 𝑋⋃𝑌 + 𝐸 + 𝑋, 𝑌 + 𝐸 + 𝑌, 𝑋
𝐺 ∖ 𝑋⋃𝑌 とする
+ 𝛿+ 𝑌
𝑋, 𝑍 + 𝐸 + 𝑋, 𝑌 ∖ 𝑋 + 𝐸 + 𝑌, 𝑍 + 𝐸 + 𝑌, 𝑋 ∖ 𝑌
𝑋 ∪ 𝑌, 𝑍 + 𝐸 + 𝑋 ∩ 𝑌, 𝑍 + 𝐸 + 𝑋, 𝑌 ∖ 𝑋 + 𝐸 + 𝑌, 𝑋 ∖ 𝑌
𝑋 ∪ 𝑌 + 𝛿 + 𝑋 ∩ 𝑌 + 𝐸 + 𝑋, 𝑌 + 𝐸 + 𝑌, 𝑋
証明
𝑍=𝑉
𝛿+ 𝑋
= 𝐸+
= 𝐸+
= 𝛿+
𝐺 ∖ 𝑋⋃𝑌 とする
+ 𝛿+ 𝑌
𝑋, 𝑍 + 𝐸 + 𝑋, 𝑌 ∖ 𝑋 + 𝐸 + 𝑌, 𝑍 + 𝐸 + 𝑌, 𝑋 ∖ 𝑌
𝑋 ∪ 𝑌, 𝑍 + 𝐸 + 𝑋 ∩ 𝑌, 𝑍 + 𝐸 + 𝑋, 𝑌 ∖ 𝑋 + 𝐸 + 𝑌, 𝑋 ∖ 𝑌
𝑋 ∪ 𝑌 + 𝛿 + 𝑋 ∩ 𝑌 + 𝐸 + 𝑋, 𝑌 + 𝐸 + 𝑌, 𝑋
X
Y
2.1 基礎的な定義
補題2.1(2)
無向グラフGと任意の2つの集合𝑋, 𝑌 ⊆ 𝑉 𝐺 に対して、
以下の(c),(d)が成立
(c)
𝛿 𝑋 +𝛿 𝑌
= 𝛿 𝑋⋂𝑌 + 𝛿 𝑋⋃𝑌 + 2 𝐸 𝑋, 𝑌
(d)
Γ 𝑋 +Γ 𝑌
≥ Γ 𝑋⋂𝑌 + Γ 𝑋⋃𝑌
証明
Γ 𝑋 +Γ 𝑌
= Γ 𝑋∪𝑌 + Γ 𝑋 ∩Γ 𝑌 + Γ 𝑋 ∩𝑌 + 𝑋∩Γ 𝑌
Γ 𝑋∩𝑌 ⊆Γ 𝑋 ∩Γ 𝑌
を用いると(d)は得られる
2.1 基礎的な定義
• 関数𝑓: 2𝑈 → 𝑅（U：有限集合、 2𝑈 :Uのべき集合）は
– すべての𝑋, 𝑌 ⊆ 𝑈で𝑓 𝑋 ∩ 𝑌 + 𝑓 𝑋 ∪ 𝑌 ≤ 𝑓 𝑋 + 𝑓 𝑌
ならば劣モジュラー
𝛿 + , 𝛿 − , 𝛿 , Γ が劣モジュラーである(補題2.1より)ことは
後で用いられる
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辺と接続
2.1 基礎的な定義
命題2.2
グラフGと𝑋 ⊆ 𝑉 𝐺 に対して、以下の命題(a)-(c)は互いに等価
である
(a) XはGの点カバーである
(b) 𝑉 𝐺 ∖ 𝑋はGの安定集合である
(c) 𝑉 𝐺 ∖ 𝑋はGの補グラフのクリークである
2.1 基礎的な定義
• 線グラフ
– 点集合𝐸 𝐺
– 辺集合𝐹 =
𝑒1 , 𝑒2 : 𝑒1 , 𝑒2 ∈ 𝐸 𝐺 , 𝑒1 ∩ 𝑒2 = 1
a
a
b
b
c
c
2.1 基礎的な定義
• 辺の重複を許すウォーク
3
c
2
d
b
4
1
e
f
a
7
5
g
6
同じ辺通らないものをウォーク
始点と終点が同じものを閉ウォーク
2.1 基礎的な定義
• パス
3
c
2
d
b
4
1
e
f
a
7
5
g
6
同じ頂点をとおらないものをパス
全点パスをハミルトンパス
2.1 基礎的な定義
• 閉路
3
c
2
d
b
4
1
e
f
a
7
5
g
6
閉ウォークで同じ頂点をとおらないものを閉路
全点閉路をハミルトン閉路
2.2 木、閉路、カット
• G: 無向グラフ
– 連結: Gに存在する任意の頂点間にパスが存在
する（そうでないとき非連結）
– Gの極大な連結部分グラフをGの連結成分
– 点集合Xで誘導される部分グラフが連結であると
き、Xは連結であるという
2.2 木、閉路、カット
• 関節点v: 𝐺−𝑣 の連結成分がGより多くなるよう
な点v
連結成分
連結成分
関節点
2.2 木、閉路、カット
• 橋e: 𝐺−𝑒 の連結成分がGより多くなるよう
な辺e
連結成分
連結成分
橋
2.2 木、閉路、カット
•
•
•
•
森: 閉路をもたない無向グラフ
木: 連結な森
葉: 木で次数1の点
スターグラフ: 葉でない点が高々1点である木
2.2 木、閉路、カット
命題2.3
(a)無向グラフGが連結であるとき、そしてそのときのみ、
すべての𝜙 ≠ 𝑋 ⊂ 𝑉 𝐺 に対して、𝛿 𝑋 ≠ 𝜙である
(b)Gを有向グラフとし、𝑟 ∈ 𝑉 𝐺 とする。
すべての点𝑣 ∈ 𝑉 𝐺 に対してr-v-パスが存在するとき、
そしてそのときのみ、 𝑟 ∈ 𝑋となるすべての𝑋 ⊂ 𝑉 𝐺 に
対して𝛿 + 𝑋 ≠ 𝜙である。
(a)だけ証明
2.2 木、閉路、カット
命題2.3
(a)無向グラフGが連結であるとき、そしてそのときのみ、
すべての𝜙 ≠ 𝑋 ⊂ 𝑉 𝐺 に対して、𝛿 𝑋 ≠ 𝜙である
If exist X s.t.𝛿 𝑋 = 𝜙…
r
v
r-v-パスは存在しない。よって非連結
2.2 木、閉路、カット
命題2.3
(a)無向グラフGが連結であるとき、そしてそのときのみ、
すべての𝜙 ≠ 𝑋 ⊂ 𝑉 𝐺 に対して、𝛿 𝑋 ≠ 𝜙である
もし非連結ならば…あるr,vに対して、r-v-パスが存在しない
rから到達可能な点をRとすると、𝑟 ∈ 𝑅, 𝑣 ∉ 𝑅かつ𝛿 𝑅 = 𝜙
が得られる
定理2.4の証明
a⇒g
端点のパスが一意でなければ閉路が存在
よって
Gが木ならば任意の2点間に唯一のパスが存在
定理2.4の証明
g⇒e⇒dは命題2.3から得られる
d⇒fは自明である
f⇒b⇒c
n点m辺p個の連結成分からなる森
n=m+p
が成り立つことから得られる
定理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が言えた
有向木
• 有向グラフが連結＝無向基礎グラフが連結
根
有向木
有向木ではない
定理2.5の証明
(a)⇒(b)と(c)⇒(d)は定理2.4から成り立つ
(b)⇒(c)
根以外の点の入次数は1より、任意のvに対し
てr-v-パスが得られる(vからrまでの唯一のパス
をたどれる)
(d)⇒(e) 命題2.3から成立
定理2.5の証明
(a)⇒(b)と(c)⇒(d)は定理2.4から成り立つ
(b)⇒(c)
根以外の点の入次数は1より、任意のvに対し
てr-v-パスが得られる(vからrまでの唯一のパス
をたどれる)
(d)⇒(e) 命題2.3から成立
定理2.5の証明
(e)⇒(f)
(e)の極小性からrの入次数は0
命題2.3よりすべてのvに対してr-v-パスが存在
あるvに対して2つのr-v-パスがあったとすると
eをとってもどの点もrから到達可能。矛盾
e
(f)⇒(g)⇒(a) 自明
カット
𝜙 ≠ 𝑋 ⊂ 𝑉 𝐺 を用いて𝛿 𝑋 と書ける辺集合
有向の場合は𝛿 + 𝑋
t
s
頂点sとtを分離するカットをs-t-カット
• 無向パス
• 無向閉路
• 無向カット
それぞれ、無向基礎グラフにおけるパス、閉路、
カット
補題2.6
Gを有向グラフとし、𝑒 ∈ 𝐸 𝐺 とする。eは黒で彩色され、残
りの各辺は赤、黒あるいは緑のいずれかで彩色されてい
るとする。このとき、以下の(a)あるいは(b)のいずれかが成
立し、両方同時に成立することはない。
(a) eを含み、赤と黒の辺だけからなる無向閉路で、黒い
辺はすべて同一の向きをもつようなものが存在する。
(b) eを含み、緑と黒の辺からなる無向カットで、黒い辺は
すべて同一の向きを持つようなものが存在する。
(a) eを含み、赤と黒の辺だけからなる無向閉路で、黒い辺は
すべて同一の向きをもつようなものが存在する。
(b) eを含み、緑と黒の辺からなる無向カットで、黒い辺はすべ
て同一の向きを持つようなものが存在する。
下のグラフは(a)を満たし、(b)を満たさない
e
yから黒い辺と赤い辺(赤い辺は向きを無視)をたどって到達で
きる点にラベル付け
xがラベル付けされたら(a)を満たす無向閉路を持つ
y
x
e
yから黒い辺と赤い辺(赤い辺は向きを無視)をたどって到達で
きる点にラベル付け
xがラベル付けされなければラベル付けされた頂点集合が(b)
を満たす無向カットを構成する
y
x
e
(a)を満たす無向閉路があるとしたら…
(a)を満たす無向閉路と(b)を満たす無向カットに共通する辺は
黒
y
x
e
有向グラフの強連結
有向グラフGは、すべての𝑠, 𝑡 ∈ 𝑉 𝐺 に対してsからtのパスとt
からsのパスがあるとき、強連結であるという。
有向グラフの極大な強連結部分グラフを強連結成分という。
系2.7
有向グラフGの各辺は、有向閉路あるいは有向カットに含まれ
る。さらに、以下の(a)-(c)は互いに連結である。
(a) Gは強連結である
(b) Gは有向カットを含まない
(c) Gは連結で、Gのどの辺も有向閉路に含まれる
系2.7
有向グラフGの各辺は、有向閉路あるいは有向カットに含まれ
る。さらに、以下の(a)-(c)は互いに連結である。
(a) Gは強連結である
(b) Gは有向カットを含まない
(c) Gは連結で、Gのどの辺も有向閉路に含まれる
命題2.3
(b)Gを有向グラフとし、𝑟 ∈ 𝑉 𝐺 とする。すべての点
𝑣 ∈ 𝑉 𝐺 に対してr-v-パスが存在するとき、そしてその
ときのみ、 𝑟 ∈ 𝑋となるすべて𝑋 ⊂ 𝑉 𝐺 に対して
𝛿 + 𝑋 ≠ 𝜙である。
系2.7(補題2.6の適用)
有向グラフGの各辺は、有向閉路あるいは有向カットに含まれ
る。さらに、以下の(a)-(c)は互いに連結である。
(a) Gは強連結である
(b) Gは有向カットを含まない
(c) Gは連結で、Gのどの辺も有向閉路に含まれる
系2.7
有向グラフGの各辺は、有向閉路あるいは有向カットに含まれ
る。さらに、以下の(a)-(c)は互いに連結である。
(a) Gは強連結である
(b) Gは有向カットを含まない
(c) Gは連結で、Gのどの辺も有向閉路に含まれる
𝑟 ∈ 𝑉 𝐺 ：任意の点
目標：各𝑣 ∈ 𝑉 𝐺 に対してr-v-パスが存在
正しくないと仮定
X
r
定義2.8
トポロジカル順序
Gを有向グラフとする。任意の辺 𝑣𝑖 , 𝑣𝑗 ∈ 𝐸 𝐺 に対して、i<jが
成立するような点集合𝑉 𝐺 = 𝑣1 , … , 𝑣𝑛 の順序をGのトポロジ
カル順序という。
1
3
2
4
5
6
命題2.9
有向グラフがトポロジカル順序を持つ
⇔
無閉路(有向閉路を持たない)である
証明(⇒)
対偶は自明
(⇐)辺数に関する帰納法
辺𝑒 ∈ 𝐸 𝐺 を持つものとする。eはある有向カットに属する
e
帰納法の仮定から、それぞれの頂点集合から誘導されるグラフにはトポロジカル
順序が存在
サイクル空間とコサイクル空間
• 有向グラフGの各無向閉路にベクトルを対応させ
る
– 無向閉路を形成する辺に1 or -1(符号は向きに対応)
– それ以外の辺に0
𝐶1
1
2
3
𝜁 𝐶1 =
4
5
6
7
8
1
−1
1
0
0
0
0
0
サイクル空間とコサイクル空間
• 有向グラフGの各無向閉路にベクトルを対応させ
る
– 無向閉路を形成する辺に1 or -1(符号は向きに対応)
– それ以外の辺に0
– 無向閉路に対応するベクトルの集合で生成されるベ
クトル空間の部分空間をサイクル空間という
サイクル空間とコサイクル空間
• 有向グラフGの各無向カットにベクトルを対応さ
せる
– 無向カットを形成する辺に1 or -1(符号は向きに対応)
– それ以外の辺に0
1
2
𝐷1
3
𝜁 𝐷1 =
4
5
6
7
8
0
0
0
1
1
−1
1
0
サイクル空間とコサイクル空間
• 有向グラフGの各無向カットにベクトルを対応さ
せる
– 無向カットを形成する辺に1 or -1(符号は向きに対応)
– それ以外の辺に0
– 無向カットに対応するベクトルの集合で生成されるベ
クトル空間の部分空間をコサイクル空間という
命題2.10
有向グラフGのサイクル空間とコサイクル空間は直交する
D
C
任意の閉路Cと任意の無向カットDに
対して、𝜁 𝐶 と𝜁 𝐷 のスカラー積が0
になることを示す
命題2.10
有向グラフGのサイクル空間とコサイクル空間は直交する
D
C
考慮するべき辺は共通する辺のみ
(他の辺に対応するベクトルの成分
はC,Dのどちらかにおいて0となる)
命題2.10
有向グラフGのサイクル空間とコサイクル空間は直交する
D
C
無向カットを有向カットとしてもスカ
ラー積の値に影響を与えない
(有向カットの非零成分の符号はす
べて一致すると考えても一般性を失
わない)
命題2.10
有向グラフGのサイクル空間とコサイクル空間は直交する
D
C
閉路を考えると、
Dに入る辺の数＝Dから出る辺の数
つまり、ベクトルにおいて、
1となる成分の数＝0となる成分の数
サイクル基底コサイクル基底
無向閉路の集合は、対応するベクトルの集合
がサイクル空間の基底となるとき、サイクル基
底と呼ばれる
無向カットの集合は、対応するベクトルの集合
がコサイクル空間の基底となるとき、コサイクル
基底と呼ばれる。
基本閉路と基本カット
• Gをグラフ、Tを無向閉路を含まないGの極大
な部分グラフとする
– 各𝑒 ∈ 𝐸 𝐺 ∖ 𝐸 𝑇 に対して、T+eに含まれる唯一
の無向閉路をTに関するeの基本閉路という
e
基本閉路と基本カット
• Gをグラフ、Tを無向閉路を含まないGの極大
な部分グラフとする
– 各𝑒 ∈ 𝐸 𝑇 に対して、𝛿𝐺 𝑋 ∩ 𝐸 𝑇 = 𝑒 となる
集合𝑋 ⊆ 𝑉 𝐺 が存在する。 𝛿𝐺 𝑋 をTに関するe
の基本カットという
X
e
定理2.11
Gを有向グラフ、Tを無向閉路を持たないGの極大な部分グラフ
とする。
Tに関する 𝐸 𝐺 ∖ 𝐸 𝑇 個の𝐸 𝐺 ∖ 𝐸 𝑇 の辺の基本閉路の
集合はGのサイクル基底となる。
Tに関する 𝐸 𝑇 個の𝐸 𝑇 の辺の基本カットの集合はコサイク
ル基底となる。
各基本閉路は他の基本閉路に含まれない辺eを含むので、基本閉路に対応する
𝐸 𝐺 ∖ 𝐸 𝑇 個のベクトルは線形独立
基本カットに対応する 𝐸 𝑇 個のベクトルに対しても同様
2つのベクトル空間は互いに直交するので、次元の和は 𝐸 𝐺
T: 無向基礎グラフが木となる有向グラフ
𝑒 = 𝑥, 𝑦 ∈ 𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を𝐶𝑒
として、族𝐹 ≔ 𝐶𝑒 : 𝑒 ∈ 𝐸 𝑇 を考える
1
2
3
T: 無向基礎グラフが木となる有向グラフ
𝑒 = 𝑥, 𝑦 ∈ 𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を𝐶𝑒
として、族𝐹 ≔ 𝐶𝑒 : 𝑒 ∈ 𝐸 𝑇 を考える
1
2
3
𝐶1
T: 無向基礎グラフが木となる有向グラフ
𝑒 = 𝑥, 𝑦 ∈ 𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を𝐶𝑒
として、族𝐹 ≔ 𝐶𝑒 : 𝑒 ∈ 𝐸 𝑇 を考える
𝐶2
1
2
3
𝐶1
T: 無向基礎グラフが木となる有向グラフ
𝑒 = 𝑥, 𝑦 ∈ 𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を𝐶𝑒
として、族𝐹 ≔ 𝐶𝑒 : 𝑒 ∈ 𝐸 𝑇 を考える
𝐶2
1
2
3
𝐶3
𝐶1
T: 無向基礎グラフが木となる有向グラフ
𝑒 = 𝑥, 𝑦 ∈ 𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を𝐶𝑒
として、族𝐹 ≔ 𝐶𝑒 : 𝑒 ∈ 𝐸 𝑇 を考える
もしTが有向木ならばFの任意
の2要素は共通部分を持たな
いか、あるいは一方が他方に
含まれるかである
1
2
3
𝐶3
𝐶2
𝐶1
定義2.12
集合システム
空でない有限集合UとUの部分集合の族Fの対(U,F)は集合シス
テムと呼ばれる。
任意の2つの集合X,Yに対して
𝑋 ∖ 𝑌, 𝑌 ∖ 𝑋, 𝑋⋂𝑌, 𝑈 ∖ 𝑋⋃𝑌 のいずれかが空⇒クロスフリー
(どのX,Yを見ても、一方が他方を含んでいる、共通する要素が
ない、すべての要素をカバーする、のいずれかを満たす)
𝑋 ∖ 𝑌, 𝑌 ∖ 𝑋, 𝑋⋂𝑌のいずれかが空⇒ラミナー
(どのX,Yを見ても、一方が他方を含んでいる、共通する要素が
ない、のいずれかを満たす)
T: 無向基礎グラフが木となる有向グラフ
𝑒 = 𝑥, 𝑦 ∈ 𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を𝐶𝑒
として、族𝐹 ≔ 𝐶𝑒 : 𝑒 ∈ 𝐸 𝑇 を考える
𝐶2
1
2
クロスフリー族
3
𝐶3
𝐶1
T: 無向基礎グラフが木となる有向グラフ
𝑒 = 𝑥, 𝑦 ∈ 𝐸 𝑇 に対して、eの終点を含むT-eの連結成分を𝐶𝑒
として、族𝐹 ≔ 𝐶𝑒 : 𝑒 ∈ 𝐸 𝑇 を考える
もしTが有向木ならばFの任意
の2要素は共通部分を持たな
いか、あるいは一方が他方に
含まれるかである
1
2
ラミナー族
3
𝐶3
𝐶2
𝐶1
定義から、
集合システム 𝑈, 𝐹 がクロスフリーであることと、任
意の𝑟 ∈ 𝑋に対して、
𝐹 ′ ≔ 𝑋 ∈ 𝐹: 𝑟 ∉ 𝑋 ∪ 𝑈 ∖ 𝑋: 𝑋 ∈ 𝐹, 𝑟 ∈ 𝑋
がラミナー族であることは等価であることが得られ
る
𝐹 ′ ≔ 𝑋 ∈ 𝐹: 𝑟 ∉ 𝑋 ∪ 𝑈 ∖ 𝑋: 𝑋 ∈ 𝐹, 𝑟 ∈ 𝑋
r
𝐶2
1
2
クロスフリー族
3
𝐶3
𝐶1
𝐹 ′ ≔ 𝑋 ∈ 𝐹: 𝑟 ∉ 𝑋 ∪ 𝑈 ∖ 𝑋: 𝑋 ∈ 𝐹, 𝑟 ∈ 𝑋
r
𝐶2
1
2
3
𝐶3
𝐶1
定義2.13
Tを無向基礎グラフが木となる有向グラフとする。
Uを有限集合とし、𝜑: 𝑈 → 𝑉 𝑇 とする。 𝑒 = 𝑥, 𝑦 に対して、
𝑆𝑒 ≔ 𝑠 ∈ 𝑈: 𝜑 𝑠 と𝑦は𝑇 − 𝑒の同じ連結成分に属する
と定義して、 𝐹 ≔ 𝑆𝑒 : 𝑒 ∈ 𝐸 𝑇 とする。このとき、 𝑇, 𝜑 を
𝑈, 𝐹 の木表現という。
クロスフリー族
𝑏, 𝑐, 𝑑, 𝑒, 𝑓 , 𝑐 , 𝑎, 𝑏, 𝑐 , 𝑒 , 𝑎, 𝑏, 𝑐, 𝑒, 𝑓 , 𝑒, 𝑓
の木表現
d
b
a
それぞれの辺の先にある頂点集合は、族の1
つの要素に対応する
f
c
e
クロスフリー族
𝑏, 𝑐, 𝑑, 𝑒, 𝑓 , 𝑐 , 𝑎, 𝑏, 𝑐 , 𝑒 , 𝑎, 𝑏, 𝑐, 𝑒, 𝑓 , 𝑒, 𝑓
の木表現
d
b
a
それぞれの辺の先にある頂点集合は、族の1
つの要素に対応する
f
c
e
クロスフリー族
𝑏, 𝑐, 𝑑, 𝑒, 𝑓 , 𝑐 , 𝑎, 𝑏, 𝑐 , 𝑒 , 𝑎, 𝑏, 𝑐, 𝑒, 𝑓 , 𝑒, 𝑓
の木表現
d
b
a
それぞれの辺の先にある頂点集合は、族の1
つの要素に対応する
f
c
e
命題2.14
𝑈, 𝐹 は木表現 𝑇, 𝜑 をもつ集合システムであ
るとすると、
𝑈, 𝐹 はクロスフリーである
Tが有向木ならばラミナーである
クロスフリーは木表現可能
ラミナー族は有向木で木表現可能
命題2.14
𝑈, 𝐹 は木表現 𝑇, 𝜑 をもつ集合システムであ
るとすると、
𝑈, 𝐹 はクロスフリーである
Tが有向木ならばラミナーである
クロスフリーは木表現可能
ラミナー族は有向木で木表現可能
𝑇, 𝜑 : 𝑈, 𝐹 の木表現
𝑒 = 𝑣, 𝑤 , 𝑓 = 𝑥, 𝑦 ∈ 𝐸 𝑇 とすると、Tの無向v-x-パスPが得
られる
(a)𝑤, 𝑦 ∉ 𝑉 𝑃
(b) 𝑤 ∉ 𝑉 𝑃 かつ𝑦 ∈ 𝑉 𝑃
(c)𝑦 ∉ 𝑉 𝑃 かつ𝑤 ∈ 𝑉 𝑃
(d) 𝑤, 𝑦 ∈ 𝑉 𝑃
の4通りが考えられる
𝑇, 𝜑 : 𝑈, 𝐹 の木表現
𝑒 = 𝑣, 𝑤 , 𝑓 = 𝑥, 𝑦 ∈ 𝐸 𝑇 とすると、Tの無向v-x-パスPが得
られる
(a)𝑤, 𝑦 ∉ 𝑉 𝑃
(b) 𝑤 ∉ 𝑉 𝑃 かつ𝑦 ∈ 𝑉 𝑃
(c)𝑦 ∉ 𝑉 𝑃 かつ𝑤 ∈ 𝑉 𝑃
(d) 𝑤, 𝑦 ∈ 𝑉 𝑃
w
v
e
𝑆𝑒
x
y
f
𝑆𝑓
𝑆𝑒 ∩ 𝑆𝑓 = ∅
𝑇, 𝜑 : 𝑈, 𝐹 の木表現
𝑒 = 𝑣, 𝑤 , 𝑓 = 𝑥, 𝑦 ∈ 𝐸 𝑇 とすると、Tの無向v-x-パスPが得
られる
(a)𝑤, 𝑦 ∉ 𝑉 𝑃
(b) 𝑤 ∉ 𝑉 𝑃 かつ𝑦 ∈ 𝑉 𝑃
(c)𝑦 ∉ 𝑉 𝑃 かつ𝑤 ∈ 𝑉 𝑃
(d) 𝑤, 𝑦 ∈ 𝑉 𝑃
w
v
e
𝑆𝑒
y
x
f
𝑆𝑓
𝑆𝑒 ⊆ 𝑆𝑓
(c)の場合は
𝑆𝑓 ⊆ 𝑆𝑒
𝑇, 𝜑 : 𝑈, 𝐹 の木表現
𝑒 = 𝑣, 𝑤 , 𝑓 = 𝑥, 𝑦 ∈ 𝐸 𝑇 とすると、Tの無向v-x-パスPが得
られる
(a)𝑤, 𝑦 ∉ 𝑉 𝑃
(b) 𝑤 ∉ 𝑉 𝑃 かつ𝑦 ∈ 𝑉 𝑃
(c)𝑦 ∉ 𝑉 𝑃 かつ𝑤 ∈ 𝑉 𝑃
(d) 𝑤, 𝑦 ∈ 𝑉 𝑃
v
w
e
y
x
f
𝑆𝑓
𝑆𝑒
𝑆𝑒 ∪ 𝑆𝑓 = 𝑈
Tが有向木ならばこのパ
ターンは起こりえない。
その場合はラミナー族
命題2.14
𝑈, 𝐹 は木表現 𝑇, 𝜑 をもつ集合システムであ
るとすると、
𝑈, 𝐹 はクロスフリーである
Tが有向木ならばラミナーである
クロスフリーは木表現可能
ラミナー族は有向木で木表現可能
F: ラミナー族
𝑉 𝑇 ≔𝐹∪ 𝑟
𝑋, 𝑌 ∈ 𝐹 × 𝐹: 𝑋 ⊃ 𝑌 ≠ ∅かつ𝑋 ⊃ 𝑍 ⊃ 𝑌となる𝑍が存在しない
𝐸 𝑇 ≔ 𝐸′ ∪ 𝑟, 𝑋 : 𝑋は𝐹の極大要素
𝐸′ ≔
r
X
Y
Fが空集合を含むならば、任意の極小集合Xに(X,Φ)を
追加
各x∈ 𝑈に対して、xを含む極小集合Xを用いて
𝜑 𝑥 =𝑋
xを含む集合がないときは
𝜑 𝑥 =𝑟
として𝜑を定義
Tはrを根とする有向木
F: クロスフリー族
𝑟 ∈ 𝑈とすると、
𝐹 ′ ≔ 𝑋 ∈ 𝐹: 𝑟 ∉ 𝑋 ∪ 𝑈 ∖ 𝑋: 𝑋 ∈ 𝐹, 𝑟 ∈ 𝑋
はラミナー族
𝑈, 𝐹 の木表現を 𝑇, 𝜑 とする
各辺𝑒 = 𝑥, 𝑦 ∈ 𝐸 𝑇 に対して𝑆𝑒 ∈ 𝐹′
(a) 𝑆𝑒 ∈ 𝐹かつ𝑈 ∖ 𝑆𝑒 ∈ 𝐹
(b) 𝑆𝑒 ∉ 𝐹かつ𝑈 ∖ 𝑆𝑒 ∈ 𝐹
(c) 𝑆𝑒 ∈ 𝐹かつ𝑈 ∖ 𝑆𝑒 ∉ 𝐹
F: クロスフリー族
𝑟 ∈ 𝑈とすると、
𝐹 ′ ≔ 𝑋 ∈ 𝐹: 𝑟 ∉ 𝑋 ∪ 𝑈 ∖ 𝑋: 𝑋 ∈ 𝐹, 𝑟 ∈ 𝑋
はラミナー族
𝑈, 𝐹 の木表現を 𝑇, 𝜑 とする
各辺𝑒 = 𝑥, 𝑦 ∈ 𝐸 𝑇 に対して𝑆𝑒 ∈ 𝐹′
(a) 𝑆𝑒 ∈ 𝐹かつ𝑈 ∖ 𝑆𝑒 ∈ 𝐹
(b) 𝑆𝑒 ∉ 𝐹かつ𝑈 ∖ 𝑆𝑒 ∈ 𝐹
(c) 𝑆𝑒 ∈ 𝐹かつ𝑈 ∖ 𝑆𝑒 ∉ 𝐹
𝑆𝑒
𝑈 ∖ 𝑆𝑒
e
F: クロスフリー族
𝑟 ∈ 𝑈とすると、
𝐹 ′ ≔ 𝑋 ∈ 𝐹: 𝑟 ∉ 𝑋 ∪ 𝑈 ∖ 𝑋: 𝑋 ∈ 𝐹, 𝑟 ∈ 𝑋
はラミナー族
𝑈, 𝐹 の木表現を 𝑇, 𝜑 とする
各辺𝑒 = 𝑥, 𝑦 ∈ 𝐸 𝑇 に対して𝑆𝑒 ∈ 𝐹′
(a) 𝑆𝑒 ∈ 𝐹かつ𝑈 ∖ 𝑆𝑒 ∈ 𝐹
(b) 𝑆𝑒 ∉ 𝐹かつ𝑈 ∖ 𝑆𝑒 ∈ 𝐹
(c) 𝑆𝑒 ∈ 𝐹かつ𝑈 ∖ 𝑆𝑒 ∉ 𝐹
𝑆𝑒
𝑈 ∖ 𝑆𝑒
z
F: クロスフリー族
𝑟 ∈ 𝑈とすると、
𝐹 ′ ≔ 𝑋 ∈ 𝐹: 𝑟 ∉ 𝑋 ∪ 𝑈 ∖ 𝑋: 𝑋 ∈ 𝐹, 𝑟 ∈ 𝑋
はラミナー族
𝑈, 𝐹 の木表現を 𝑇, 𝜑 とする
各辺𝑒 = 𝑥, 𝑦 ∈ 𝐸 𝑇 に対して𝑆𝑒 ∈ 𝐹′
(a) 𝑆𝑒 ∈ 𝐹かつ𝑈 ∖ 𝑆𝑒 ∈ 𝐹
(b) 𝑆𝑒 ∉ 𝐹かつ𝑈 ∖ 𝑆𝑒 ∈ 𝐹
(c) 𝑆𝑒 ∈ 𝐹かつ𝑈 ∖ 𝑆𝑒 ∉ 𝐹
𝑆𝑒
𝑈 ∖ 𝑆𝑒
e
F: クロスフリー族
𝑟 ∈ 𝑈とすると、
𝐹 ′ ≔ 𝑋 ∈ 𝐹: 𝑟 ∉ 𝑋 ∪ 𝑈 ∖ 𝑋: 𝑋 ∈ 𝐹, 𝑟 ∈ 𝑋
はラミナー族
𝑈, 𝐹 の木表現を 𝑇, 𝜑 とする
各辺𝑒 = 𝑥, 𝑦 ∈ 𝐸 𝑇 に対して𝑆𝑒 ∈ 𝐹′
(a) 𝑆𝑒 ∈ 𝐹かつ𝑈 ∖ 𝑆𝑒 ∈ 𝐹
(b) 𝑆𝑒 ∉ 𝐹かつ𝑈 ∖ 𝑆𝑒 ∈ 𝐹
(c) 𝑆𝑒 ∈ 𝐹かつ𝑈 ∖ 𝑆𝑒 ∉ 𝐹
𝑆𝑒
𝑈 ∖ 𝑆𝑒
e
F: クロスフリー族
𝑟 ∈ 𝑈とすると、
𝐹 ′ ≔ 𝑋 ∈ 𝐹: 𝑟 ∉ 𝑋 ∪ 𝑈 ∖ 𝑋: 𝑋 ∈ 𝐹, 𝑟 ∈ 𝑋
はラミナー族
𝑈, 𝐹 の木表現を 𝑇, 𝜑 とする
各辺𝑒 = 𝑥, 𝑦 ∈ 𝐸 𝑇 に対して𝑆𝑒 ∈ 𝐹′
(a) 𝑆𝑒 ∈ 𝐹かつ𝑈 ∖ 𝑆𝑒 ∈ 𝐹
(b) 𝑆𝑒 ∉ 𝐹かつ𝑈 ∖ 𝑆𝑒 ∈ 𝐹
(c) 𝑆𝑒 ∈ 𝐹かつ𝑈 ∖ 𝑆𝑒 ∉ 𝐹
𝑆𝑒
𝑈 ∖ 𝑆𝑒
e
系2.15
Uの異なる部分集合の…
ラミナー族は高々2|U|個の要素しか含まない
クロスフリー族は高々4|U|-2個の要素しか含まない
非空真部分集合のラミナー族F
命題2.14における構成法では…
異なる部分集合の数=枝の数=頂点数-1
各頂点に対して出次数が2以上である or ラベル付けされる
ラベル付けされる頂点の数は高々|U|個
出次数が2以上となるのは高々
𝐸 𝑇
2
𝐸 𝑇 +1= 𝑉 𝑇 ≤ 𝑈 +
𝐹 = 𝐸 𝑇 ≤2 𝑈 −2
空集合とUを合わせると…
𝐸 𝑇
2
系2.15
Uの異なる部分集合の…
ラミナー族は高々2|U|個の要素しか含まない
クロスフリー族は高々4|U|-2個の要素しか含まない
非空真部分集合のクロスフリー族F
Fの変換により得られるラミナー族F’
𝐹 ≤ 2 𝐹′ ≤ 4 𝑈 − 4
空集合とUを合わせると…

Download Report