8.9. Hall の結婚定理に関する練習問題
Hall の結婚定理 (定理 8.3.4) を利用する練習問題を少数ではあるがここに示す。
有限集合 \(X\), \(Y\) が \(\left\vert X\right\vert \leq\left\vert Y\right\vert \) を満たすと仮定する。\(f\colon X\rightarrow Y\) を定数でない写像とする (写像が定数 (constant) とは、写像の値が全て等しいことを言う)。任意の \(x \in X\) が \(g\left( x\right) \neq f\left( x\right) \) を満たす単射 \(g\colon X\rightarrow Y\) が存在すると示せ。
有限集合 \(A\), \(B\) が \(\left\vert B\right\vert \geq\left\vert A\right\vert \) を満たすと仮定する。任意の \(\left( i,j\right) \in A\times B\) に対して実数 \(d_{i,j}\) が定まっているとする。\(m_{1}\) と \(m_{2}\) を次のように定める:
\(m_{1} = m_{2}\) を示せ。
単純グラフ \(G=\left( V,E\right) \) が \(\left\vert E\right\vert \geq\left\vert V\right\vert \) を満たすと仮定する。単射 \(f\colon V\rightarrow E\) であって条件「任意の頂点 \(v \in V\) に対して、辺 \(f\left( v\right) \) は \(v\) を含まない」を満たすものが存在すると示せ。
\(S\) を有限集合、\(k\) を自然数とする。\(k\) 個の \(S\) の部分集合 \(A_{1}, A_{2}, \ldots, A_{k}\) が条件「\(S\) の各要素が \(A_{1}, A_{2}, \ldots, A_{k}\) のちょうど一つに含まれる」を満たすとする。次の二つの命題が同値だと示せ:
-
命題 1: 任意の \(i \in\left\{ 1, 2, \ldots, k \right\} \) が \(\sigma\left( A_{i} \right) \cap A_{i} = \varnothing\) を満たす全単射 \(\sigma\colon S \to S\) が存在する。
-
命題 2: 任意の \(i\in\left\{ 1,2,\ldots,k\right\} \) が \(\left\vert A_{i}\right\vert \leq\left\vert S\right\vert /2\) を満たす。
\(S\) を有限集合、\(k\) を自然数とする。\(\left\vert S\right\vert \geq2k+1\) が成り立つと仮定する。単射 \(f\colon \mathcal{P}_{k}\left( S\right) \rightarrow\mathcal{P}_{k+1}\left( S\right) \) であって任意の \(X\in\mathcal{P}_{k}\left( {S}\right) \) が \(f\left( X\right) \supseteq X\) を満たすものが存在すると示せ。
[例: \(S=\left\{ 1,2,3,4,5\right\} \) および \(k=2\) のとき、例えば次のように定義される写像 \(f\) は条件を満たす:
ここに何らかのパターンを見出せるだろうか？ (私には見出せない。)]
\(\left( G,X,Y\right) \) を二部グラフとする。\(X\) の任意の部分集合 \(A\) が \(\left\vert N\left( A\right) \right\vert \geq\left\vert A\right\vert \) を満たすと仮定する (そのため定理 8.3.4 より \(G\) は \(X\)-完全なマッチングを持つ)。
\(X\) の部分集合 \(A\) が \(\left\vert N\left( A\right) \right\vert =\left\vert A\right\vert \) を満たすとき、\(X\) は隣接限界 (neighbor-critical) と言うことにする。
\(A\) と \(B\) が \(X\) の隣接限界な部分集合のとき、\(A\cup B\) と \(A\cap B\) も \(X\) の隣接限界な部分集合だと示せ。