inamori https://blog.hatena.ne.jp/inamori/ inamori’s diary https://inamori.hateblo.jp/ 数学 プログラミング おさらい 2部グラフをあるルールに従ってランダムに作ったとき、 完全マッチングする確率を求める。 擬似乱数を使ってグラフを作ってもよいが、 正確に求めるために、全ての場合を考える。 ただし、場合の数は約135億あるから、 同型のグラフはなるべくまとめて考え、 実質的に場合の数を減らしたい。 ここで同型とは、グラフ理論の本にもあまりちゃんと書いてないんだが（汗）、 隣接行列の行を適当に入れ替えて （列も同時に入れ替わることになる）、 一致すれば同型とする。 （とりあえず）同型判定方法 まず、連結成分に分ける。 点数が多い連結成分を上（番号が小さいほう）にもってくる。 同じなら、次数が大きい点があ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finamori.hateblo.jp%2Fentry%2F20051024%2Fp1" title="2部グラフの同型の判定（1） - inamori’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2005-10-24 00:00:00 rich https://inamori.hateblo.jp/entry/20051024/p1 1.0 100%