NetworkX でランダムグラフの最大連結部分を数える - Qiita

NetworkX という Python 向けの素敵なグラフライブラリを知ったので、練習がてら「ランダムグラフの最大連結部分のサイズがどんくらいになるか」という実験をしてみた。 （ここでの「グラフ」とは数値データを可視化する図のことではなく、ネットワークグラフ的な意味でのグラフ） 問題設定 頂点 (node) がN個ある。 ランダムに2点を選んで辺 (edge) で結ぶ。これをS回繰り返す。 辺でつながった部分（連結部分）の最大サイズはいくらか。 この問題は S. Kauffman の著書「自己組織化と進化の論理」3章で紹介されたもので、多様な物質の混合物から生命が創発するモデルの一部として登場している。 コードと実行 ここでは networkx, numpy, matplotlib, および pydot をインスコしたものとする。インストール手順については最後に軽く触れる。 上記の問題に従