はむ。日記

離散数学とか解析学とかアニメについてつぶやきます。

Hallの定理とその応用

グラフ理論

[Def]近傍

グラフ $G$ の任意の点集合 $S$ に対して、 $S$ のどれかの点に隣接する点の全体を $G$ における $S$ の近傍と呼び、 $N_{G}(S)$ や $N(S)$ と書く。

$G$ を2部分割 $(X,Y)$ を持つ2部グラフとするとき、 $X$ の点がすべて飽和されるような $G$ のマッチングを見つけることは応用上重要である。

[Thm]Hallの定理

$G$ を2部分割 $(X,Y)$ を持つ2部グラフとする。

$G$ は $X$ の点を全て飽和するマッチングを持つ $\Leftrightarrow$ 任意の $S \subseteq X$ に対して、 $|N(S)| \geq |S|$

(証明)

( $\Rightarrow$ )

$X$ の全ての点を飽和するマッチングを $M$ とする。

任意の $S \subseteq X$ を考える。

$S$ を飽和する $M$ の辺を集めた集合を $M_{S}$ とすると、

$|S| = |M_{S}|$ .

$M_{S}$ が飽和する $Y$ の頂点は全て $N(S)$ の元である。

よって、 $|M_{S}| \leq |N(S)|$ .

つまり、 $|S| \leq |N(S)|$ . 　■

( $\Leftarrow$ )

$(X,Y)$ を部集合に持つ2部グラフで $\forall S \subseteq X,|N(S)| \geq |S|$ を満たすものを $G$ とする。

そこで $G$ は $X$ の点を全て飽和するマッチングを持たないと仮定して矛盾を導く。

$M$ を $G$ の最大マッチングとする。

仮定により、 $X$ に属する $M$ 非飽和点 $u$ が存在する。

そこで、 $Z$ を $M$ 交互道によって、 $u$ に連結するような点の全体の集合とする。

$M$ は最大マッチングだから、 $u$ は $Z$ の中で唯一の $M$ 非飽和点である。(もし、そうでないとすると $M$ 増加道が存在することになり $M$ の最大性に矛盾。)

$S = Z \cup X , T = Z \cup Y$ とおく。

明らかに $S \setminus ｛u｝$ の点は $M$ の下で $T$ の点とマッチングされているから

$|T| = |S| -1$ であり、 $T \subseteq N(S)$ が成り立つ。

$N(S)$ のどの点も $M$ 交互道により $u$ に連結されているので $N(S) \subseteq T$ .

よって $N(S) = T$ が成り立つ。

よって $|N(S)| = |T| = |S| - 1 ＜ |S|$ となって仮定に矛盾。　■

[Prob]Hallの定理を応用した面白い問題

トランプのカード52枚を4枚ずつ13個のグループへ任意に分けた時、各グループから1枚ずつカードをうまく選ぶと、A,2,3,4,5,6,7,8,9,10,J,Q,Kを1枚ずつ取り出せる。

(解答)

$A =$ グループに対応する頂点の集合

$B =$ カードのランクに対応する頂点の集合

とおく。

$A$ の各点(グループのこと)に対して、その点とその点に対応するグループに属するカードのランクに対応する $B$ の点を辺で結ぶ。そうでないとき辺を引かない。

この操作により2部グラフができる。

$\forall S \subseteq A$ を考える。

$N(S)$ は $S$ に属するグループに含まれるカードのランクに対応する。

$S$ に属するグループに含まれるカードの総数は $4|S|$

$N(S)$ に対応するランクのカードの総数は $4|N(S)|$

$|N(S)|＜ |S|$ と仮定する。

$|S|$ 個のグループを $N(S)$ に対応するランクのカードだけでつくれない。

実際 $|S|$ 個のグループをつくるには $4|S|$ 枚のカードが必要であるが、この仮定のもとでは $4|N(S)|$ 枚のカードしか用意できないためカードが足りなくなる。

よって $|S| \leq |N(S)|$ .

つまりHallの定理にある条件が成り立つので $A$ を飽和するマッチングが存在する。

そこから各グループからどのカードを選べばよいかわかる。■