8.10. マッチングに関する練習問題
\(G=\left( V,E,\varphi\right) \) を多重グラフ、\(M\) を \(G\) のマッチングとする。
\(M\) の増加路 (augmenting path) とは、\(G\) の路 \(\left( v_{0},e_{1},v_{1},e_{2},v_{2},\ldots,e_{k},v_{k}\right) \) であって次の条件を満たすものを言う:
-
\(k\) が奇数である。
-
添え字が偶数の辺 \(e_{2}, e_{4}, \ldots, e_{k-1}\) が全て \(M\) に属する。
-
添え字が奇数の辺 \(e_{1}, e_{3}, \ldots, e_{k}\) は \(E \setminus M\) に属する。
-
始点 \(v_{0}\) は \(M\) でマッチ済みでない。
-
終点 \(v_{k}\) は \(M\) でマッチ済みでない。
\(M\) が \(G\) の要素数最大のマッチングであるのは \(M\) の増加路が存在しないとき、かつそのときに限ると示せ。
\(\left( G,X,Y\right) \) を二部グラフ、\(A\) を \(X\) の部分集合、\(B\) を \(Y\) の部分集合とする。\(G\) が \(A\)-完全なマッチングと \(B\)-完全なマッチングを持つと仮定する。\(G\) が \(A\cup B\) 完全なマッチングを持つと示せ。
\(\left( G,X,Y\right) \) を二部グラフとする。\(X\neq\varnothing\) であり、\(G\) は \(X\)-完全なマッチングを持つと仮定する。
\(G\) の辺 \(e\) が無益 (useless) とは、\(e\) を含む \(X\)-完全なマッチングが \(G\) に存在しないことを言う。
条件「\(x\) を含む無益な辺が存在しない」を満たす頂点 \(x \in X\) が存在することを示せ。
二部グラフ \(\left( G,X,Y\right) \) が \(\left\vert Y\right\vert \geq2\left\vert X\right\vert -1\) を満たすと仮定する。任意の \(x \in X\) が次の二つの命題の少なくとも一方を満たす単射 \(f\colon X\rightarrow Y\) が存在することを示せ:
-
命題 1: \(G\) で \(x\) と \(f \left( x \right) \) が隣接する。
-
命題 2: \(G\) で \(x\) と \(f\left( x^{\prime}\right) \) が隣接するような \(x^{\prime}\in X\) が存在しない。
\(\left( G,X,Y\right) \) と \(\left( H,U,V\right) \) を二部グラフとする。
\(G\) が単純グラフで \(X\)-完全なマッチングを持つと仮定する。さらに、\(H\) も単純グラフで \(U\)-完全なマッチングを持つと仮定する。
定義 2.14.10 で定義した \(G\) と \(H\) のデカルト積 \(G\times H\) を考える。
-
\(\left( G\times H,\ \left( X\times V\right) \cup\left( Y\times U\right) ,\ \left( X\times U\right) \cup\left( Y\times V\right) \right) \) が二部グラフだと示せ。
-
\(G\times H\) が \(\left( X\times V\right) \cup\left( Y\times U\right) \)-完全なマッチングを持つと示せ。