男女各8人で合コンしたとする。
そこで女がそれぞれ気に入った男を2人選んだとする。
その選び方が全くのランダムなとき、
8組のカップルができる確率を求める。
最初に考えた問題は、数学的には同じだが、上と違う例だった。
しかし、グラフ理論ではこういった例えをよく用いるようなので、
分かりやすく上のようにした。
さて、言い訳はおいといて、実際に問題を考えていこう。
女が2人の男を選ぶ場合の数は28通りあるので、
場合の数は全部で28の8乗通りある。
実質的には28の7乗だが。
このように全ての場合を考えていては日が暮れてしまうので、
なるべく同型のグラフはまとめて考えていく。
といっても同型の判定もなかなか難しいので、
ここは次のように簡易的に同型の判定を行う。
男は手の数（次数）でソートする。
これで全く同じ男女のつながりなら同型としてまとめて考える。
ここから、男の名前はB0〜B7とし、女の名前はG0〜G7としよう。
最初の女G0が2人の男を選ぶ。
例えば、B2とB5を選んだとしよう。
そうすると、B2とB5の次数が1であとは0となる。
ソートすると、B2,B5が上に来るので、それをB0,B1とすればよい。
こう考えると、最初のG0がどう2人を選んでもその段階では同型になることがわかる。
これらのグラフをコンピュータ上で次のように表現する。
まず、B0とG0〜G7のそれぞれが辺でつながっていればビットを立てる。
すなわち、例えば、G0とG2がB0とつながっていれば、2進数で00000101とする。
それをB0〜B7の順に左から並べる。
こうすると64ビットで収まるので、64ビット符号無し整数で表せる。
このあたりはコンパイラ（処理系）によっても違うだろうが、
32ビットしかないのなら構造体でも作ればよいだろう。
あとあともし一般の人数の男女のことを考えるときに
そういう風にプログラムを組むかもしれない。
あとは、G1が選ぶ場合の数は28通りあるので、
そのグラフになる確率はその前段階（G1が選んだグラフ）の確率の1/28になる。
そして、上の意味での同型のグラフはまとめれば（足し合わせれば）よい。
具体的には連想配列を使う（私の場合STLのmapを使う）。
う〜ん、組んでみたらメモリが足りないみたい。
異なるグラフの数を数えてみると、同型のグラフをまとめている分、
単純にやっているときよりは減っていて、
2人目 28→14
3人目 784→244
4人目 21952→5320
5人目 614656→127722
6人目 17210368→3177554
まさかこんなに減っていないとは。
もうちょっと同型をまとめる工夫が必要。
