平成14年度前期　離散数学入門

水２

1. １０個
2. S⁶₄ 4! = 1560通り
3. 増加道の例：x₂ - y₁ - x₁ - y₂, 最大マッチングは完全マッチング（略）
4. 最大流15, 最小切断 {入口, A, B, D}と{C,出口}、矢印の組はA→C, D→C, D→出口

1. 125個
2. (n⁴+n²+2n)/4=n(n+1)(n²-n+2)/4通り
3. 9ペア。 ラベル付けにより増加道が存在しないことを示すか、 g, i, j, kには J, Kしかつながっていないことから最大不足度が2以上あるので。
4. 最大流15, 矢印は{A→C, D→C, D→出口}

研究室へ戻る