Document

2章
マッチング
詫間
風人
はじめに
 マッチング：G＝（V,E)に含まれる独立な辺の集合M
A
例）
B
C
D
E
M＝{{A,B},{C,F},{D,G}}
U＝{A,B,C}
F
G
H
頂点集合UのすべてがMに属す辺に接続しているとき、Uの頂点は
マッチされている
Mのどの辺にも接続していない頂点はマッチされていない
 k-因子 : k-正則全域部分グラフ
はじめに
 マッチング：G＝（V,E)に含まれる独立な辺の集合M
A
例）
B
C
D
E
F
G
H
頂点集合UのすべてがMに属す辺に接続しているとき、Uの頂点は
マッチされている
Mのどの辺にも接続していない頂点はマッチされていない
 k-因子 : k-正則全域部分グラフ
2.1
二部グラフのマッチング
交互道と増大道
マッチされていないAの頂点を始点とし、E＼MとMに属す辺を交互に
含んでいるものをMに関する交互道と呼ぶ
Bに属すマッチされていない頂点を終点とする交互道を増大道と呼ぶ
2.1
二部グラフのマッチング
Gのどの辺もU⊆Vに属す頂点に接続しているとき、UをEの
被覆（Gの頂点被覆）と呼ぶ
2.1
二部グラフのマッチング
定理2.1.1（Kolingの定理）
マッチングの最大値は頂点被覆の最小値と一致
（証明）
• MをGの最大マッチングとする
• 𝑀 の各辺 𝑒 = {𝑢,𝑣}(𝑢 ∈ 𝐴,𝑣 ∈ 𝐵) に対し， 𝑒 を含む交互道があるとき
は 𝑣，ないときは 𝑢 を選び頂点集合 𝑈 をつくる. このとき|𝑈|= |𝑀|
2.1
二部グラフのマッチング
（証明続き）
• 任意の頂点被覆は， 𝑀 の各辺 {𝑢,𝑣} に対し，𝑢 か 𝑣 のいずれかを含む
ので，|𝑀| 以上
• よって，Uが頂点被覆であることを示せばよい
2.1
二部グラフのマッチング
（証明続き）
• 任意の辺 𝑎,𝑏 ∈ 𝐸 の 𝑎 、𝑏 の少なくともどちらか一方は 𝑈 に含まれる
ことを示す必要あり
• 𝑀 は最大マッチングなので，𝑎 または 𝑏 に接続する辺を含む（さもなけ
れば 𝑀 ∪{𝑎,𝑏} もマッチングとなり，𝑀 が最大であることに反する）
2.1
二部グラフのマッチング
（証明続き）
• [case1]𝑀 が 𝑎 に接続する辺を含んでいないとき． 𝑏 に接続する辺 𝑒
∈ 𝑀 が存在する．すると， 𝑎,𝑏,𝑒 が交互道となるので 𝑏 ∈ 𝑈
2.1
二部グラフのマッチング
（証明続き）
•
•
•
•
[case2] 𝑀 が 𝑎 に接続する辺 𝑒 を含むとき．𝑎 ∈𝑈の時は明白
𝑎 ∉ 𝑈 と仮定
[case2-1] 𝑒 = {𝑎,𝑏} のとき．𝑈 の定義より 𝑏 ∈ 𝑈
[case2-2] 𝑒 ≠ {𝑎,𝑏} のとき．
Case2-1
Case2-2
2.1
二部グラフのマッチング
• 𝑈 の定義より，𝑒 を終辺とする交互道 𝑃 が存在．
• [case2-2-1] 𝑃 が 𝑏 を通るとき．𝑃 は 𝑏 に接続する
𝑒’∈ 𝑀 を通るはずなので， 𝑈 の定義より 𝑏 ∈ 𝑈．
• [case2-2-2]𝑃 が 𝑏 を通らないとき．
𝑀 が最大マッチングなので増大道はない．
よって，𝑏 に接続する 𝑒’∈ 𝑀 が存在．
交互道は 𝑒’まで延長できるので， 𝑏 ∈ 𝑈．（証明終わり）
2.1
二部グラフのマッチング
結婚定理：Aのマッチングを持つための必要条件
S⊆Aに対して、|N(S)| ≥ |S|
2.1
二部グラフのマッチング
(証明）
•
•
•
•
•
𝐺 が 𝐴 のマッチングを持たないとする．
𝐺 の最小頂点被覆を，𝑈 = 𝐴’∪𝐵’(𝐴’⊂𝐴,𝐵’⊆𝐵)とする．
Königの定理より 𝐴’ + 𝐵’ = 𝑈 < 𝐴 ．
よって， 𝐵’< 𝐴−𝐴’
一方，𝑈 が頂点被覆であることから， 𝐴−𝐴’ の頂点と 𝐵 −𝐵’ の頂点を
結ぶ辺は存在しない．
• したがって， 𝑁(𝐴−𝐴’ )≤ 𝐵’ < 𝐴−𝐴’ となり，定理の条件に矛盾．(終
わり)
2.1
二部グラフのマッチング
2.1.3. 任意の集合S⊆Aと自然数ｄ∈ ℕ に対して、|N(S)|≥|S|−
dが成り立つなら、Gは辺数が|A|−ｄのマッチングを含む
S
d=1
|N(S)|≥|S|−d
2
≥ 3ー1
2.1
二部グラフのマッチング
（証明）
• Bに新たな頂点をd個追加し、Aに属すすべての頂点と辺で結ぶ
• 結婚定理の条件より、Aのマッチングを含み、|A|−ｄのマッチングを
含む
2.1
二部グラフのマッチング
• 2.1.4. ｋ≥１に対して、Gがｋ-正則ならば、Gは１-因子を持つ
（証明）
•
•
•
•
•
Gがｋ-正則ならば|A|=|B|
結婚定理よりGがAのマッチングを含むことを示せば十分
Ｓ⊆Ａは全体でk|S|本の辺でＮ(S)と結ばれている
それらの辺はN(S)に接続するk|N(S)|本の辺のうちに含まれている
K|S|≤k|N(S)|となり、結婚の定理の条件を満たしている
2.1
二部グラフのマッチング
• 2.1.5. 正の偶次数の正則グラフは2-因子を持つ
（証明）
• Gを任意の2k-正則グラフ（k≥1）とする
• Gは連結であると仮定する
• 定理1.8.1.よりGはオイラー周遊を含む
2.1
二部グラフのマッチング
（証明続き）
• 2部グラフG’はk-正則であるから2.1.4.より1-因子をもつ
• 1個の頂点に戻すと2-因子になる
2.2
一般のグラフにおけるマッチング
 奇成分（q(G))：位数が奇数の連結成分の個数
1-因子の辺が各奇成分からSに向かって伸びているので次が成り立つ
すべてのS⊆V(G)に対してｑ(GーS)≤|S|（Tutteの条件）
2.2
一般のグラフにおけるマッチング
2.2.2. 橋を持たない任意の3-正則グラフは1-因子を持つ
（証明）
•
•
•
•
•
•
•
Tutteの条件を満たすことを示す
S⊆V(G)に対して、G−Sの奇成分Cを考える
Gは3-正則なので、GにおけるCの頂点の次数の総和は奇数である
Cに含まれる辺は2回使われるので、奇数本のS-C辺がある
3本以上存在するので、SとG−Sの間の辺の総数は３ｑ(G−S）以上
その値は3-正則であるから3|S|以下でもある
よって、q(G-S)≤|S|を得る
S
C
2.2
一般のグラフにおけるマッチング
Gにおいて、v∈Gに対してG−vが1-因子を持つ場合、
Gを因子臨界的という
GーSの連結成分を1個の頂点に縮約し、Sの内部の辺をすべて
除去して得られるグラフHsがSのマッチングを含んでいるとき、
SはGーSにマッチ可能であるという
G
Gーv
2.2
一般のグラフにおけるマッチング
2.2.3：任意のグラフGは、次の2つの条件頂点の集合Sを持つ
i. SはG−Sにマッチ可能
ii. GーSのすべての連結成分が因子臨界的
グラフGが1-因子を持つための必要十分条件は|S|=|CGーS|
S
2.2
一般のグラフにおけるマッチング
2.2.3：任意のグラフGは、次の2つの条件頂点の集合Sを持つ
i. SはG−Sにマッチ可能
ii. GーSのすべての連結成分が因子臨界的
グラフGが1-因子を持つための必要十分条件は|S|=|CGーS|
S
2.3 道被覆
 有向道：頂点x0~xkと辺e0~ek-1からなる有向グラフP≠∅でeiが
xiからxi+1に向かう辺になっているもの
ter(P)
P
x0
x1
x2
x3
 道被覆：Gの中の交わりのない辺の集合で、すべての頂点を包含
2.3 道被覆
• 2.3.1. 任意の有向グラフGは、a(G)本の道からなる道被覆を持つ
• |極小端点道被覆|≤|最大独立点集合|
ter(ρ’)⊆ter（ρ)となるような道被覆が存在しないρ
（証明）
• 頂点数k+1のGの極小端点道被覆 ρ＝｛P1~Pm｝を選ぶ
2.3 道被覆
（証明続き）
•
•
•
•
ρ＝｛P1~Pm｝道被覆とし、各iに対して、vi:=ter(Pi)とおく
もし{ vi | 1 ≤ i ≤ m ｝が独立集合ならば証明の必要はない
v2からv1に向かう辺があると仮定する
v1を削除したら、ρ’={P1v~Pm}はG’:=G-v1の道被覆となっている
2.3 道被覆
（証明続き）
• ρ’’の道被覆が存在すると仮定する（場合分け）
• 道P∈ρ’’がvで終わっている
PをPvv1に取り換えるとρの極小性に反する
• 道P∈ρ’’がv2（vで終わっているものはないとする）で終わっている
• PをPv2v1に取り換えるとρの極小性に反する
• Ρ’’に自明な道{v1}を併せるとρの極小性に反する
問題
ヒント：増大道
ヒント：2.2.2

Download Report