Chapter5
Systems of Distinct Representatives
照山順一
system of distinct representative(以下SDR)
集合列S1,S2,…,Smに対するSDRとは、
以下の条件を満たす異なる要素の列
x1,x2,…,xmのこと。
条件：
356
234
14
34
56
12
56
この様な列が存在するのか？->結婚問題
女性は知っている男性とのみ結婚できる。
すべての女性が結婚できる方法は？
Hall’s Condition
356
234
{1,2,3,4,5,6}
14
34
56
12
56
定理5.1結婚定理(Hall’s marriage theorem)
｢集合S1,…,SmがSDRを持つこと｣は、
｢Hall’s Conditionを満たすこと｣の必要十分条
件である。
証明の方針：(十分性は明らかなので、必要性のみ)
◦ mに関する帰納法。
◦ m=1の時は明らか。
◦ m個より少ない集合について成り立つと仮定。
◦ 2つの場合に分けて考える。
Case1
すべてのkについて、任意のk個の集合の
和集合はkより多く要素をもつ。
Hall’s condition を満たす。
(どのk集合を持ってきても和集合の大きさはk以上)
xを使用しないSDRが存在する。
xを加えて全体のSDRとする。
Case2
あるkについて、k個の集合の和集合が
ちょうどk個の要素をもつ。
k集合のSDR要素を取り除く
和集合の大きさがsより小さいとすると、
もともとこの集合とk集合の和集合の
大きさがk+sより小さくなってしまい、
仮定に矛盾。
Hall’s condition が満たされている。
なぜか？
Hall’s Condition
一般にはHall’s conditionが満たされて
いるかを確認するのは大変。
しかし、集合の性質がわかっていると
楽になることもある。
[系5.2]
集合S1,…,Smをn要素集合のr要素部分集合と
し、それぞれの要素はd個の集合に属してい
る。もし、
ならば、集合S1,…,Smは
SDRを持つ。
[証明]
要素数をダブルカウンティング。
集合S1,…,SmがSDRを持たないとして矛盾を導く。
あるk個の集合(Si1,…, Sik)に対して和集合( Y )の要素
数がkより小さい。(Hall’s conditionから)
dxをこの集合に含まれているxの数とすると、
要素に色(赤or青)が付いた問題を考える。
集合と色分けされた要素が与えられて、
できるだけ赤の要素が少ないSDRを作りたい。
[定理5.3]
｢集合S1,…,Smが赤の要素が高々tのSDRを持つ｣こと
は、
｢集合S1,…,SmがSDRを持ち、すべてのkに対して任
意のk個の集合の和集合が少なくともk-tの青の要素
をもつ｣
ことの必要十分条件である。
十分性は明らか。
十分性
356
234
5
3
・・・
34
56
12
56
4
2
どのようにk個の集合を選んでも、少なくともk-t個の青要素がある
定理5.3の証明
仮定：｢集合S1,…,SmがSDRを持ち、すべてのkに対して任意
のk個の集合の和集合が少なくともk-tの青の要素をもつ｣
R :赤の要素の集合とする。
仮定：|R|>tとする。(そうでないとすると簡単)
集合S1,…,Smを集合S1,…,Sm ,Sm+1,…,Sm+rに拡張
する。(Sm+1=…=Sm+r =R , r = |R| - t )
｢集合S1,…,Smが赤の要素が高々tのSDRを持つ｣
｢集合S1,…,Sm ,Sm+1,…,Sm+rがSDRを持つ｣
定理5.3の証明
示すこと：これらの集合がHall’s conditionを満たす。
356
234
34
56
12
56
24
7…
24
7…
これらの集合のみでの集合らは、
こちらの集合も含んでいる場合
仮定でSDRをもともと持っているのでOK。
和集合の青の要素数の仮定から
右側から選んだ集合の数
(復習)SDRとHall’s condtion
5.2Two applications
Hall’s Theoremを使って集合系に関係のなさ
そうにみえる定理を証明。
5.2.1 Latin rectangles(ラテン長方形)
1からnが各列に1つずつ、各行には高々1つ
の行列。
2
5
4
1
3
4
2
1
3
5
5
1
3
4
2
3×5のラテン長方形
[定理5.4] rがnより小さい時、
r×nラテン長方形は、(r+1)×nラテン長方形
に拡張することができる。
3
4
5
2
1
2
5
4
1
3
[系5.2]
4
2
1
3
集合S1,…,Smをn要素集合のr要素部分集合とし、
5
1
3
4
それぞれの要素はd個の集合に属している。
もし、
ならば、集合S1,…,SmはSDRを持つ。
3×5のラテン長方形から
4×5のラテン長方形へ
5
2
[証明]
第j行にない数字の集合をSjとする。
この時、Sjはすべて n - r 個の要素を持ち、
それぞれの数字は n - r 個の集合に属している。
系5.2よりこの集合系はSDRを持つ。
5.2.2
Decomposition of doubly stochastic matrices
(二重確率行列の分解)
[用語の準備]
doubly stochastic matrix(二重確率行列)：
非負実数を要素に持つ行列で、
各行、各列の要素の和が１。
permutation matrix(置換行列)：
各行、各列に１が１つ
convex combination of matrices(凸結合)：
[Birkhoff-Von Neumann Theorem]
すべての二重確率行列は、
置換行列の凸結合である。
[証明]より一般的なことを証明する。
Aの非負要素の数に関して帰納法。
もし、ちょうどnならば簡単。
nより多いとし、その数より少ないところでは
定理が成り立つと仮定する。
Siを第i行に関して0でない要素がある
列番号の集合とする。
この時、S1,…,SmがHall’s condtionを満たす。
もし満たさないとすると、k行取ってきたときにそ
の中で0でない要素をもつ列がk未満である。この
とき列から見た要素の和は高々(k-1)g 、行から見た
和はkg であり矛盾。
a11
a22
a32
A
a41
a
51
a14
a15
a23
a43
a45
a64
a65
a56
あるSDRが存在し、これをもとに分解でき
ることを証明する。
次のスライドで少し具体的に。
a11
a22
a32
A
a41
a
51
1
P1
0
0
0
a14
a15
a23
a43
a45
a64
a65
0
0
1
1
0
1
1
0
a56
1
5.3 Min-max theorems
[定理5.5]
Aをm×n行列とする。
独立な1の数の最大値は、
Aの1をすべてカバーするのに必要な行と列
の数の最小値と等しい。
1
A
1
1
1
1
1
1
1
1
1
1
1
1
定理5.5の証明
1
A
1
1
1
r：独立な1の数の最大値
R ：Aの1をすべてカバーするのに必要な
行と列の数の最小値
明らかに、Rはr以上。
示すのは、 rがR以上となること。
1
1
1
1
1
1
1
1
1
1
1
A
1
1
1
1
1
1
1
1
1
1
1
定理5.5の証明
1
1
A
1
1
1
1
1
1
1 1
1 1
この部分で
a個の独立な1が
とれることを示す。
1
Siをi行で1がある列の番号の集合とする。
S1,…,SaがSDRを持つことを示す。
持たないとすると、Hall’s theoremからあるk行を
持ってきたときにその部分の1の数がkより小さく
なる。つまりこのk行分をkより少ない列でカバー
できる。しかし、カバーに必要な行と列の数がa+b
より小さくなり矛盾となる。
左下の部分についても同様にすると、
5.4 Matching in bipartite graphs
2部グラフGはAからBへのマッチングをもつのか？
Aの各頂点に関して隣接頂点の集合をとり、
その集合系がSDRを持つか？
[定理5.6](Hall’s Theoremの言い換え)
｢二部グラフGがAからBへのマッチングをも
つ｣ことは、
｢Aのすべてのk頂点部分集合は少なくともk
個の隣接頂点をもつ｣ことの必要十分条件で
ある。
定理5.6を用いて
以下の命題を証明する。
[命題5.7]
X ：n要素集合。
任意の
に対してXのすべてのk
要素部分集合をどの二つも一致することな
く(k+1)要素部分集合に拡張できる。
n=5,k=2
3
2
4
3
4
5
2
5
1
1
命題5.7の証明
Aの頂点：Xのk要素部分集合
Bの頂点：Xの(k+1)要素部分集合
包含関係の成り立つ頂点間に枝が張られている。
示すこと：AからBへの完全マッチングが存在している。
Hall’s Condition
残りの部分は、最大マッチングと最小
頂点被覆の話なので、グラフ理論の講
義を思い出しながら自分で読んでくだ
さい。
© Copyright 2024 ExpyDoc
