おさらい
2部グラフをあるルールに従ってランダムに作ったとき、
完全マッチングする確率を求める。
擬似乱数を使ってグラフを作ってもよいが、
正確に求めるために、全ての場合を考える。
ただし、場合の数は約135億あるから、
同型のグラフはなるべくまとめて考え、
実質的に場合の数を減らしたい。
ここで同型とは、グラフ理論の本にもあまりちゃんと書いてないんだが（汗）、
隣接行列の行を適当に入れ替えて
（列も同時に入れ替わることになる）、
一致すれば同型とする。
（とりあえず）同型判定方法
まず、連結成分に分ける。
点数が多い連結成分を上（番号が小さいほう）にもってくる。
同じなら、次数が大きい点があるほうを上にもってくる。
同じなら、最大の次数の点が多いほう、等々。
連結成分の点の次数がすべて2なら閉路だが、
この場合は点の数が同じなら同型なので、
並びを工夫して、
上から順に並ぶようにする。
次数が1が2つであと2なら1本道なので、
これも上から順に並べる。
これでも同型とならなかったら、
今回は同型でないと判定する。
結果
場合の数が、
2人目 3 → 3
3人目 16 → 10
4人目 139 → 60
5人目 1739 → 549
6人目 28432 → 7042
7人目 563435 → 114889
8人目 12738288 → 2266243
だいぶ減った。
これなら9人目も行ける？
