第10回 - Donald Home Page

4.4: 独立集合，被覆と監視問題
[部屋の手配の問題]
宿泊客n人があるホテルに
部屋の予約を入れてきた。
ホテルはm部屋持っているが，
宿泊客が泊まってもよいと
思っている部屋は異なる。
最大何人の予約を成立させる
ことが可能か？
H26 グラフ理論
ー第10回ー
マッチングと独立集合
予約客の希望の関係
1
2
独立集合：グラフ G=(V, E) で，どの辺 e∈ E に対しても，
e の端点のうち多くともどちらか一方しか含まない
部分集合 S⊆V を，独立集合という．点数が最大の
独立集合の大きさを G の独立数といい α(G) で表す．
[コミュニティーの発見問題]
特定の条件を満たす人の集まりをコミュニティーという．
できるだけ大きなコミュニティーを発見する問題．
α(G) = 3
知り合い同士を表すネットワーク
お互いが知り合いである
最大のコミュニティー
G
これらの問題をグラフ理論として特徴付ける
3
独立集合(黒丸)
(independent set)
最大独立集合
(max. independent set)
4
1
グラフのクリーク：グラフ G=(V, E) の部分グラフで
完全グラフであるものを G のクリークという．
頂点が最も多いクリークを G の最大クリークという．
グラフの点被覆：グラフ G=(V, E) で，どの辺 e∈ E に
対しても，e の両端の点のうち少なくとも一方を含む
ある部分集合 S⊆V を，G の点被覆という．
最小の点被覆の大きさ (被覆数) をβ(G) と表す．
β(G)=3
β(G)=3
G
G
点被覆
(set cover)
最小点被覆
(min. set cover)
クリーク
(clique)
最大クリーク
(max. clique)
5
6
グラフ G の最大独立集合，最小点被覆，最大クリーク
の計算は困難．(簡単な計算法は知られていない)
グラフ G の最大独立集合，最小点被覆，最大クリーク
の計算は困難．(簡単な計算法は知られていない)
このグラフの最小点被覆は？
これが最小？
このグラフの最小点被覆は？
7
最小点被覆の解
8
2
最小点被覆問題は，最適解を計算する簡単な方法は
知られていないが，以下のように近似的な解を求める
簡単な方法がある．
グラフの独立集合，点被覆，クリークには自明な関係が
成立し，どれか一つが計算できれば他の解を直ちに
求めることができる．(1対1の関係がある)
アルゴリズム１（貪欲法）
それまでに被覆されていない辺のうち，最も被覆する
数が多い点を選んでいく手法
アルゴリズム２（最大マッチング法）
最大マッチングを求めるアルゴリズムを利用する手法
これらの手法は最適解の2倍以内の解を保証する．
(詳細は次回)
点被覆：どの辺に対してもどちらかの
端点は選ばれている
9
元のグラフの補グラフを考えると，以下の関係も自明
最小点被覆
独立集合：辺でないどの頂点の組も
どちらの端点も選ばれている
最大独立集合
10
以上をまとめると，以下の関係となる．
定理：任意のグラフ G=(V,E) とその頂点の
部分集合 S⊆V に対して，以下は等価である．
(1) S が G の最大独立集合
(2) V-S が G の最小点被覆
(3) S が G の補グラフの最大クリーク
どの頂点の組に対しても
それらを結ぶ辺がない
最大独立集合
それらの辺(左図の点線)は
補グラフの辺(右図)
補グラフの最大クリーク
11
12
3
辺に関する独立集合と被覆
辺の被覆：グラフ G=(V, E) で，G のどの点も S⊆ E の
ある辺の端点となっているとき，S を G の辺被覆という．
最小の辺被覆の大きさを辺被覆数といい，β’(G) で表す．
辺の独立集合：グラフ G=(V, E) で，ある部分集合
S⊆ E のどの2辺も接していないとき，S を G の
辺独立集合 (マッチング) という( α’(G) )．
β’(G)=3
α’(G)=3
G
マッチング
（辺独立集合）
G
最大マッチング
（完全マッチングでもある）
辺被覆
最小辺被覆
13
[紛らわしい概念について]
基本定理:
, β’(Kp)=
.
(1)α(Kp)=1, β(Kp)=p-1, α’(Kp)=
(2)α(Kn,m)=n, β(Kn,m)=m, α’(Kn,m)=m, β’(Kn,m)=n, (n≧ m).
頂点の(被覆・独立集合)と辺の(被覆・独立集合)

頂点の被覆・独立集合
証明: (1) α(独立数)，β(被覆数)であることに注意
α(Kp)=1： Kpの任意の点はその他のすべての点と
接続しているので，α(Kp)=1.
β(Kp)=p-1：どのような点の選び方をしても i 番目に選んだ点が
新たに被覆する辺の数は，p-i本であるので，最後の１本を被覆
するまでに選んだ点の総数はp-1である．
 辺を被覆するように頂点を選ぶ
 頂点が独立する(隣接しない)ように頂点を選ぶ

14
辺の被覆・独立集合
 頂点を被覆するように辺を選ぶ
Kp
 辺が独立する(隣接しない)ように辺を選ぶ
15
最初に選ぶ点が被覆する辺の数はp-1
どれを選んでも次の点が被覆する辺数は p-2
16
4
定理4.3: 任意のグラフ G と任意の S⊆V(G) に対して，
以下の条件は等価である．
(1) S は G の独立集合である
(2) V(G)-S が G の被覆である
基本定理:
, β’(Kp)=
.
(1)α(Kp)=1, β(Kp)=p-1, α’(Kp)=
(2)α(Kn,m)=n, β(Kn,m)=m, α’(Kn,m)=m, β’(Kn,m)=n, (n≧ m).
証明: (1)
：１つの辺 e=(i,j) を選ぶ毎に，i も j も
α’(Kp)=
他の辺に使うことが出来ないから．
：１本辺を選ぶ毎に2個ずつ頂点を被覆していくから．
β’(Kp)=
(2)は自明なので省略する．
Kp
証明：S が G の独立集合ならば，G のどの辺も S の点を
両端には持っていない（多くともどちらか一方）．このこと
は G の任意の辺の少なくとも一方の点が V(G)-S に
含まれることと同値，すなわち V(G)-S が G の被覆と同値．
どの辺も V(G)-S の頂点を持つ．
そうならないのはSの頂点同士に辺がある
ときだけで，それはSが独立であることに反する
ある辺を選ぶことで，
(a) 独立な辺として利用可能な点が2個減る
(b) 選んでいない点が2個減る
S
V(G)-S が G の被覆となる
17
18
ガライの定理:
孤立点を持たないグラフ G に対して，
α’(G)+β’(G)=|V(G)|が成り立つ．
定理4.3: S⊆V(G) が G の独立集合であることと
V(G)-S が G の被覆であることは同値．
系4.3.1: 任意のグラフ G に対して，
α(G) +β(G) = |V(G)| が成り立つ．
α’(G)=3
証明： S を最大独立集合とし，K を最小被覆とすると，
定理4.3より，V(G)-S は被覆，V(G)-K は独立集合である．
このことから，
α(G) ≧ |V(G)-K| = |V(G)|-β(G)
β(G) ≦ |V(G)-S| = |V(G)|-α(G)
したがって，α(G)+β(G)=|V(G)| が成り立つ．
19
β’(G)=3
α’(G)+β’(G)=|V(G)| となり，
これは一般に成り立つ
最大マッチング
最小辺被覆
20
5
ガライの定理:
孤立点を持たないグラフ G に対して，
α’(G)+β’(G)=|V(G)|が成り立つ．
ガライの定理:
孤立点を持たないグラフ G に対して，
α’(G)+β’(G)=|V(G)|が成り立つ．
証明： α’(G)+β’(G) ≦|V(G)| の証明
M を最大マッチングとすると，M は 2α’(G) 個の点を被覆する．
(α’は隣接しない辺の本数．よって頂点はその2倍)
U を M の端点でない点集合とすると，U の各点に接続する辺が
少なくとも1辺ずつ存在する(孤立点がないから)．
証明： α’(G)+β’(G) ≦|V(G)| の証明
これらの辺集合を M ’ とすると，M と M ’ に共通要素はなく，
M ∪M ’はG の辺被覆であるから，
β’(G) ≦ |M∪M’| = |M|+|U| = α’(G) + (|V(G)|-2α’(G))
= |V(G)|-α’(G)
となり，α’(G)+β’(G) ≦|V(G)| を得る．
最大マッチング M
最大マッチング M
U に接続する M 以外の辺
U の点
U に接続する M 以外の辺
21
証明：逆の関係： |V(G)| ≦α’(G)+β’(G)の証明．
L’ を G の最小辺被覆とし，L をその連結成分の集合とすると，
すべての連結成分は木である．
もしそうでないなら閉路があり，そこから辺を取り除いても
G を被覆できるので，最小であることに反する．
|L| ≦α’(G) である(各連結成分内で1つ以上独立な辺を選べるから)．
また，各連結成分が木であるので，
木の性質から，頂点数=辺数+1が成り立つので，
|V(G)| = |V1|+...+|VL |= (|E1|+1)+...+(|EL|+1)=|L’|+|L|であることから，
|V(G)|= |L’|+|L| ≦α’(G)+β’(G)．以上より，α’(G)+β’(G)=|V(G)|.
U の点
22
次回は最大マッチングの効率的な計算と，それを応用
した最大独立集合の近似計算について講義する．
最小辺被覆 L’ (L=2)
(2つの木からなる)
23
24
6

Download Report