8.10. マッチングに関する練習問題

目次
練習問題 8.9

\(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\) が奇数である。 [\(k = 1\) でも構わない。]

  • 添え字が偶数の辺 \(e_{2}, e_{4}, \ldots, e_{k-1}\) が全て \(M\) に属する。 [この条件は \(k=1\) のとき空虚な真となる。]

  • 添え字が奇数の辺 \(e_{1}, e_{3}, \ldots, e_{k}\) は \(E \setminus M\) に属する。

  • 始点 \(v_{0}\) は \(M\) でマッチ済みでない。

  • 終点 \(v_{k}\) は \(M\) でマッチ済みでない。

\(M\) が \(G\) の要素数最大のマッチングであるのは \(M\) の増加路が存在しないとき、かつそのときに限ると示せ。

[ヒント: \(M\) と \(M^{\prime}\) を \(G\) の二つのマッチングとするとき、対称差 \(\left( M \cup M^{\prime}\right) \setminus\left( M \cap M^{\prime}\right) \) に関して何が言えるだろうか?]

練習問題 8.10

\(\left( G,X,Y\right) \) を二部グラフ、\(A\) を \(X\) の部分集合、\(B\) を \(Y\) の部分集合とする。\(G\) が \(A\)-完全なマッチングと \(B\)-完全なマッチングを持つと仮定する。\(G\) が \(A\cup B\) 完全なマッチングを持つと示せ。

練習問題 8.11

\(\left( G,X,Y\right) \) を二部グラフとする。\(X\neq\varnothing\) であり、\(G\) は \(X\)-完全なマッチングを持つと仮定する。

\(G\) の辺 \(e\) が無益 (useless) とは、\(e\) を含む \(X\)-完全なマッチングが \(G\) に存在しないことを言う。

条件「\(x\) を含む無益な辺が存在しない」を満たす頂点 \(x \in X\) が存在することを示せ。

練習問題 8.12

二部グラフ \(\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\) が存在しない。

[Remark: 結婚相手を探している男女の設定を使うと、この命題は次のように言い換えられる: \(m\) 人の男性と \(w\) 人の女性がいて、\(w\geq2m-1\) が成り立つとする。このとき、任意の男性が「自分の結婚相手を気に入っている」と「自分が気に入っている女性が全て結婚していない」の少なくとも一方を満たすように男性のそれぞれを (一人の) 女性と結婚させることができる。]

[解答: これは 2017 年春学期に開講された講義で出した homework set #3 の Exercise 3 である。解答は講義ページに載っている。]

練習問題 8.13

\(\left( G,X,Y\right) \) と \(\left( H,U,V\right) \) を二部グラフとする。

\(G\) が単純グラフで \(X\)-完全なマッチングを持つと仮定する。さらに、\(H\) も単純グラフで \(U\)-完全なマッチングを持つと仮定する。

定義 2.14.10 で定義した \(G\) と \(H\) のデカルト積 \(G\times H\) を考える。 [\(G\) と \(H\) を単純グラフとしたのは、多重グラフに対する \(G\times H\) の定義を避けるためである。]

  1. \(\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) \) が二部グラフだと示せ。

  2. \(G\times H\) が \(\left( X\times V\right) \cup\left( Y\times U\right) \)-完全なマッチングを持つと示せ。

[解答: これは 2017 年春学期に開講された講義で出した homework set #4 の Exercise 3 である。解答は講義ページに載っている。]

広告