2部グラフとマッチング

第２回
グラフ理論・組み合わせ論
情報学部門 瀧本 英二
http://www.i.kyushu-u.ac.jp/~eiji
2
用語の定義（歩道）
無向グラフ 𝐺 = (𝑉, 𝐸) について考える
歩道（walk）：頂点の列 𝑣0 , 𝑣1 , 𝑣2 , … , 𝑣𝑘 ∈ 𝑉 が歩道
⇔ 𝑣0, 𝑣1 , 𝑣1 , 𝑣2 , … , 𝑣𝑘−1 , 𝑣𝑘 ∈ 𝐸
𝑘: その歩道の長さ（歩道を構成する辺の数）
閉じた歩道（closed walk）：始点 𝑣0 と終点 𝑣𝑘 が一致する歩道
歩道の例
閉じた歩道の例
3
用語の定義（道，回路，閉路）
小道（trail）：同じ辺が高々１回しか現れない歩道
道（path）：同じ頂点が高々１回しか現れない歩道
回路（circuit）：閉じた小道（始点と終点が一致する小道）
閉路（cycle）：同じ頂点が高々１回しか現れない閉じた歩道
道の例
閉路の例
２部グラフとマッチング
Hallの結婚定理
5
２部グラフ（bipartite graphs）
定義 無向グラフ (𝑉, 𝐸) が二部グラフであるとは，
𝑉 の分割 𝐴, 𝐵（i.e., 𝑉 = 𝐴 ∪ 𝐵, 𝐴 ∩ 𝐵 = ∅）が存在して
∀𝑒 ∈ 𝐸, 𝐴 ∩ 𝑒 = 𝐵 ∩ 𝑒 = 1
例
2
2
3
1
4
1
7
4
5
5
7
6
6
3
𝐴
𝐵
6
２部グラフの特徴づけ
定理 無向グラフ 𝐺 が２部グラフであるための
必要十分条件は，𝐺 に長さが奇数の閉路が
存在しないことである．
2
3
4
1
5
7
6
閉路：
1. 2,3,6,7,2 （長さ４）
2. 2,3,4,7,2 （長さ４）
3. 4,5,6,7,4 （長さ４）
4. 3,4,7,6,3 （長さ４）
5. 2,3,4,5,6,7,2 （長さ６）
7
証明：
2部グラフである 奇数長の閉路がない
背理法：奇数長の閉路があると仮定
∈𝐴
∈𝐴
矛盾
∈𝐵
∈𝐵
∈𝐴
8
証明：
奇数長の閉路がない  2部グラフである
• 一般性を失わず 𝐺 は連結であると仮定
• 頂点 𝑢 ∈ 𝑉 をひとつ固定する．
•𝐴 = 𝑣 ∈𝑉
𝑢 から 𝑣 への最短路の長さが偶数
𝐵 = 𝑣 ∈ 𝑉 𝑢 から 𝑣 への最短路の長さが奇数
と定義．（𝑢 ∈ 𝐴 に注意）
• 𝐴（𝐵）のどの２頂点間にも辺がないことを示せばよい
定義：
𝐺 が連結 ⇔ 𝐺 の任意の２頂点を結ぶ道が存在
𝑢 から 𝑣 への最短路 = 𝑢 から 𝑣 への長さ最小の道
9
証明：
奇数長の閉路がない  2部グラフである
• 頂点 𝑢 ∈ 𝑉 をひとつ固定する．
•𝐴 = 𝑣 ∈𝑉
𝑢 から 𝑣 への最短路の長さが偶数
𝐵 = 𝑣 ∈ 𝑉 𝑢 から 𝑣 への最短路の長さが奇数
𝑢
𝑢
𝑢
𝑢から全頂点への最短路を表す
全域木（全頂点を結ぶ閉路のない部分グラフ）
10
証明（続き）
𝐺
𝐴
𝑢
𝑣
𝑤
𝑢′
𝑃𝑣
𝑃𝑤
任意の 𝑣, 𝑤 ∈ 𝐴 について考える．
（𝑣, 𝑤 ∈ 𝐵 の場合も同様）
𝑃𝑣 ： 𝑢 から 𝑣 への最短路
𝑃𝑤 ： 𝑢 から 𝑤 への最短路
𝑢′：𝑃𝑣 と 𝑃𝑤 が分岐する頂点
• 𝑃𝑣 と 𝑃𝑤 の長さのパリティ
（遇 or 奇）が等しい．
• よって，
𝑢′ ↝ 𝑣 の長さのパリティ
= 𝑢′ ↝ 𝑤 の長さのパリティ
• よって，もし 𝑣, 𝑤 ∈ 𝐸 なら
𝑢′ ↝ 𝑣 ↝ 𝑤 ↝ 𝑢′
の長さ奇数の閉路ができて
しまい矛盾． （証明終）
12
マッチング（Matching）
定義： グラフ 𝐺 = (𝑉, 𝐸) に対し，互いに素な辺集合
𝑀 ⊆ 𝐸 をマッチングと呼ぶ．
例：
13
２部グラフのマッチング
𝐴：仕事の集合
𝐵：人の集合
{𝑎, 𝑏} ∈ 𝐸 ⇔ 仕事 𝑎 を人 𝑏 に割り当て可能
と考えると，マッチングは仕事の割り当てに相当
仕事
人
14
本日の目標
定理 （Hallの結婚定理）
２部グラフ (𝐴 ∪ 𝐵, 𝐸) が，𝐴 のすべての頂点に接続する
マッチングを持つための必要十分条件は，
∀𝑆 ⊆ 𝐴, 𝑁 𝑆 ≥ 𝑆 ,
ただし，𝑁 𝑆 = {𝑣 ∈ 𝐵 ∣ ∃𝑢 ∈ 𝑆, 𝑢, 𝑣 ∈ 𝐸}．
𝐴
𝐵
15
本日の目標
定理 （Hallの結婚定理）
２部グラフ (𝐴 ∪ 𝐵, 𝐸) が，𝐴 のすべての頂点に接続する
マッチングを持つための必要十分条件は，
∀𝑆 ⊆ 𝐴, 𝑁 𝑆 ≥ 𝑆 ,
ただし，𝑁 𝑆 = {𝑣 ∈ 𝐵 ∣ ∃𝑢 ∈ 𝑆, 𝑢, 𝑣 ∈ 𝐸}．
𝐴
𝐵
16
頂点被覆（vertex cover）
定義： 頂点集合 𝑈 ⊆ 𝑉 が 𝐺 の頂点被覆
⇔ ∀𝑒 ∈ 𝐸, ∃𝑢 ∈ 𝑈, 𝑢 ∈ 𝑒
例：
𝐺
1
6
3
4
7
2
5
8
𝑈 = {1,3,5,6,8} は 𝐺 の頂点被覆
17
マッチングと頂点被覆
Königの定理： ２部グラフ 𝐺 の最大マッチングの
サイズは 𝐺 の最小頂点被覆のサイズに等しい．
𝐴
証明は後で．
𝐵
𝐴
𝐵
18
本日の目標
定理 （Hallの結婚定理）
２部グラフ (𝐴 ∪ 𝐵, 𝐸) が，𝐴 のすべての頂点に接続する
マッチング（𝐴のマッチング）を持つための必要十分条件は
∀𝑆 ⊆ 𝐴, 𝑁 𝑆 ≥ 𝑆 ,
ただし，𝑁 𝑆 = {𝑣 ∈ 𝐵 ∣ ∃𝑢 ∈ 𝑆, 𝑢, 𝑣 ∈ 𝐸}．
𝐴
𝐵
19
証明
• 必要性は明らか【演習問題】なので，十分性を示す．
• 𝐺 の最小頂点被覆を，𝑈 = 𝐴′ ∪ 𝐵 ′ 𝐴′ ⊆ 𝐴, 𝐵 ′ ⊆ 𝐵
とする．
• 【背理法】 𝐺 が 𝐴 のマッチングを持たないとする．
Königの定理より
𝐴′ + 𝐵′ = 𝑈 < 𝐴 ．よって， 𝐵′ < 𝐴 − 𝐴′ ．
• 一方，𝑈 が頂点被覆であることから，
𝐴 − 𝐴′ の頂点と 𝐵 − 𝐵′ の頂点を結ぶ辺は存在しない．
• したがって， 𝑁 𝐴 − 𝐴′ ≤ 𝐵 ′ < 𝐴 − 𝐴′ となり，
定理の条件に矛盾．(終わり)
20
König の定理の証明の準備 - 交互道
２部グラフ 𝐺 = (𝐴 ∪ 𝐵, 𝐸) のマッチング 𝑀 ⊆ 𝐸 を考える．
このとき，マッチしていない 𝐴 の頂点を始点として，
𝐸 − 𝑀 と 𝑀 の辺を交互に通る道を，
𝑀 に関する交互道（alternating path）という．
𝐴
𝐵
𝐴
𝐵
交互道
注：𝑀の辺は𝐵から𝐴の向き
21
König の定理の証明の準備 – 増大道
２部グラフ 𝐺 = (𝐴 ∪ 𝐵, 𝐸) のマッチング 𝑀 ⊆ 𝐸 を考える．
このとき，交互道であり，終点がマッチしていない 𝐵 の
頂点であるものを，𝑀に関する増大道（augmenting path）
という．
𝐴
𝐵
𝐴
𝐵
増大道
【演習問題】
最大マッチング
に関する増大道
は存在しない
22
König の定理の証明
• 𝑀 を 𝐺 の最大マッチングとする．
• 𝑀 の各辺 𝑒 = {𝑢, 𝑣} (𝑢 ∈ 𝐴, 𝑣 ∈ 𝐵) に対し，
𝑒 を含む交互道があるときは 𝑣，ないときは 𝑢 を選び
頂点集合 𝑈 をつくる． 𝑈 = |𝑀| に注意．
𝐴
𝐵
23
証明（続き）
• 任意の頂点被覆は， 𝑀 の各辺 {𝑢, 𝑣} に対し，𝑢 か 𝑣 の
いずれかを含むので，そのサイズは |𝑀| 以上．
• よって，Uが頂点被覆であることを示せばよい．
• すなわち，任意の辺 𝑎, 𝑏 ∈ 𝐸 の端点 𝑎 または 𝑏 の
少なくともどちらか一方は 𝑈 に含まれることを示す．
𝐴
𝐵
24
証明（続き）
• 𝑀 は最大マッチングなので，𝑎 または 𝑏 に接続する
辺を含んでいる．（さもなければ 𝑀 ∪ {𝑎, 𝑏} もマッチング
となり，𝑀 が最大であることに反する．）
【場合１】 𝑀 が 𝑎 に接続する辺を含んでいないとき．
𝑏 に接続する辺 𝑒 ∈ 𝑀 が存在する．すると，
𝑎, 𝑏, 𝑒 が交互道となるので 𝑏 ∈ 𝑈．
𝑎
𝑏
𝑒
𝐴
𝐵
25
証明（続き）
【場合２】 𝑀 が 𝑎 に接続する辺 𝑒 を含むとき．
𝑎 ∈ 𝑈 なら直ちに題意が示されるので，𝑎 ∉ 𝑈 と仮定．
【場合２－１】 𝑒 = {𝑎, 𝑏} のとき．𝑈 の定義より 𝑏 ∈ 𝑈．
【場合２－２】 𝑒 ≠ {𝑎, 𝑏} のとき．
𝐴
𝑎
𝑒
𝑏
𝐵
𝑎
𝑒
𝑏
これが青いこと
（𝑏 ∈ 𝑈）を示したい
【場合２－１】
【場合２－２】
26
𝑃
証明（続き）
𝑎
𝑒
𝑏
𝑒′
𝑎
𝑃
𝑏
𝑒
【場合２－２－１】
𝑎
𝑒
𝑒′
𝑏
【場合２－２－２】
• 𝑈 の定義より，𝑒 を終辺とする交互道 𝑃 が存在．
【場合２－２－１】 𝑃 が 𝑏 を通るとき．𝑃 は 𝑏 に接続する
𝑒 ′ ∈ 𝑀 を通るはずなので， 𝑈 の定義より 𝑏 ∈ 𝑈．
【場合２－２－２】 𝑃 が 𝑏 を通らないとき．
• 𝑀 が最大マッチングなので増大道はない．
• よって，𝑏 に接続する 𝑒 ′ ∈ 𝑀 が存在．
• 交互道は 𝑒′ まで延長できるので， 𝑏 ∈ 𝑈．（証明終わり）