4人の学生($s_1, s_2, s_3, s_4$)に4種類の調査テーマ($T_1, T_2, T_3, T_4$)を割り当てる問題を考える。表は各学生が興味を持つテーマを示している。以下の3つの問に答える。 1. 学生とテーマに関するグラフを描く。

1. 問題の内容

4人の学生($s_1, s_2, s_3, s_4$)に4種類の調査テーマ($T_1, T_2, T_3, T_4$)を割り当てる問題を考える。表は各学生が興味を持つテーマを示している。以下の3つの問に答える。

1. 学生とテーマに関するグラフを描く。

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

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

2. 解き方の手順

1. グラフの作成：学生を頂点集合$S = \{s_1, s_2, s_3, s_4\}$、テーマを頂点集合$T = \{T_1, T_2, T_3, T_4\}$とする二部グラフを作成する。学生$s_i$がテーマ$T_j$に興味を持つ場合に限り、頂点$s_i$と$T_j$の間に辺を引く。

2. マッチングの解の存在確認：ホール(Hall)の結婚定理を用いる。つまり、任意の学生の部分集合$S'$に対し、$S'$の学生が興味を持つテーマの集合$N(S')$の要素数が、$|S'|$以上であるかどうかを確認する。

3. マッチングの例：

* $s_1$は$T_1$または$T_2$を選択できる。

* $s_2$は$T_1, T_3, T_4$を選択できる。

* $s_3$は$T_3$を選択できる。

* $s_4$は$T_1, T_3, T_4$を選択できる。

たとえば、$s_3$が$T_3$を選んだ場合、$s_1$は$T_1$または$T_2$を選択できる。$s_1$が$T_1$を選んだ場合、$s_2$は$T_4$、$s_4$は$T_3$を選べない。$s_1$が$T_2$を選んだ場合、$s_2$は$T_1$または$T_4$を選択できる。$s_4$は$T_1$または$T_4$を選択できる。

可能なマッチングの例を一つ見つける。例えば以下のようなものがある。

* $s_1$ -> $T_2$

* $s_2$ -> $T_1$

* $s_3$ -> $T_3$

* $s_4$ -> $T_4$

3. 最終的な答え

1. 学生とテーマに関するグラフ：（説明省略）

2. マッチングの解は存在する。

3. マッチングの例：

* $s_1$ -> $T_2$

* $s_2$ -> $T_1$

* $s_3$ -> $T_3$

* $s_4$ -> $T_4$