4人の学生 $s_1, s_2, s_3, s_4$ に4種類の調査テーマ $T_1, T_2, T_3, T_4$ を割り当てる問題を考えます。各学生が興味を持つテーマが表で与えられています。 (1) 学生とテーマに関するグラフを描き、 (2) マッチングの解が存在するかどうかを確認し、 (3) 解が存在する場合、マッチングの例を答えます。

1. 問題の内容

4人の学生 $s_1, s_2, s_3, s_4$ に4種類の調査テーマ $T_1, T_2, T_3, T_4$ を割り当てる問題を考えます。各学生が興味を持つテーマが表で与えられています。

(1) 学生とテーマに関するグラフを描き、

(2) マッチングの解が存在するかどうかを確認し、

(3) 解が存在する場合、マッチングの例を答えます。

2. 解き方の手順

(1) 学生とテーマに関するグラフを描きます。

グラフの頂点を学生 $s_1, s_2, s_3, s_4$ とテーマ $T_1, T_2, T_3, T_4$ とします。学生 $s_i$ がテーマ $T_j$ に興味を持つとき、頂点 $s_i$ と $T_j$ を結ぶ辺を引きます。

(2) マッチングの解が存在するかどうかを確認します。

ホール条件を用いて考えます。ホール条件とは、学生の部分集合 $S$ に対して、 $S$ に含まれる学生が興味を持つテーマの集合を $N(S)$ とするとき、常に $|S| \le |N(S)|$ が成り立つことです。もしホール条件が満たされなければ、完全マッチングは存在しません。

* $S = \{s_1\}$ のとき、$N(S) = \{T_1, T_2, T_4\}$ なので、 $|S|=1 \le |N(S)| = 3$。

* $S = \{s_2\}$ のとき、$N(S) = \{T_1, T_3, T_4\}$ なので、 $|S|=1 \le |N(S)| = 3$。

* $S = \{s_3\}$ のとき、$N(S) = \{T_3\}$ なので、 $|S|=1 \le |N(S)| = 1$。

* $S = \{s_4\}$ のとき、$N(S) = \{T_1, T_3, T_4\}$ なので、 $|S|=1 \le |N(S)| = 3$。

* $S = \{s_1, s_2\}$ のとき、$N(S) = \{T_1, T_2, T_3, T_4\}$ なので、 $|S|=2 \le |N(S)| = 4$。

* $S = \{s_1, s_3\}$ のとき、$N(S) = \{T_1, T_2, T_3, T_4\}$ なので、 $|S|=2 \le |N(S)| = 4$。

* $S = \{s_1, s_4\}$ のとき、$N(S) = \{T_1, T_2, T_3, T_4\}$ なので、 $|S|=2 \le |N(S)| = 4$。

* $S = \{s_2, s_3\}$ のとき、$N(S) = \{T_1, T_3, T_4\}$ なので、 $|S|=2 \le |N(S)| = 3$。

* $S = \{s_2, s_4\}$ のとき、$N(S) = \{T_1, T_3, T_4\}$ なので、 $|S|=2 \le |N(S)| = 3$。

* $S = \{s_3, s_4\}$ のとき、$N(S) = \{T_1, T_3, T_4\}$ なので、 $|S|=2 \le |N(S)| = 3$。

* $S = \{s_1, s_2, s_3\}$ のとき、$N(S) = \{T_1, T_2, T_3, T_4\}$ なので、 $|S|=3 \le |N(S)| = 4$。

* $S = \{s_1, s_2, s_4\}$ のとき、$N(S) = \{T_1, T_2, T_3, T_4\}$ なので、 $|S|=3 \le |N(S)| = 4$。

* $S = \{s_1, s_3, s_4\}$ のとき、$N(S) = \{T_1, T_2, T_3, T_4\}$ なので、 $|S|=3 \le |N(S)| = 4$。

* $S = \{s_2, s_3, s_4\}$ のとき、$N(S) = \{T_1, T_3, T_4\}$ なので、 $|S|=3 \le |N(S)| = 3$。

* $S = \{s_1, s_2, s_3, s_4\}$ のとき、$N(S) = \{T_1, T_2, T_3, T_4\}$ なので、 $|S|=4 \le |N(S)| = 4$。

ホール条件が満たされているので、マッチングの解が存在します。

(3) マッチングの例を答えます。

以下にマッチングの例を挙げます。

* $s_1 \rightarrow T_2$

* $s_2 \rightarrow T_1$

* $s_3 \rightarrow T_3$

* $s_4 \rightarrow T_4$

3. 最終的な答え

マッチングの解は存在し、例えば以下の割り当てが可能です。

* 学生1：テーマ2

* 学生2：テーマ1

* 学生3：テーマ3

* 学生4：テーマ4