点の数を決めて、ランダムに辺を加えていって、何本目の辺を加えたときに連結になるかを調べた。点の数は、10、20、…、100として、それぞれ10000回繰り返した。これは段々収束していっているのだろうか。

全ての場合について試すのは無理があるので、前々回と同じようにまとめて考える。 その前に、Pythonで補助的なクラスArrayGenを作る。 例えば、階乗の計算はこのように行っていたが、 def fac(n): p = 1 for i in range(1, n + 1): p *= i return pこれだと…

m点で辺の数がnのときのすべての場合について、連結かどうか判定する。 まず、m点なら可能な辺の数は、m点から2点選ぶから、m(m-1)/2、そのうちn辺を選ぶから、m(m-1)/2Cnの場合がある。それをすべて列挙する。次のような組合せを列挙するジェネレータを作っ…

陸の孤島三好池にようこそ。知立からバスで三好町役場前まで。そこからジョグ。 会場の陸上競技場は学校のグラウンドみたいなところ。早めに並ぶが、真ん中より少しだけ前。もうちょっと前に並んでもよかったか。 スタートラインを通過してもなかなか前に進…

m点で辺の数がm-1で連結のとき、グラフは木になる。ループがなくて連結のグラフを木と呼ぶ。 m点で辺の数がm-1のグラフの数を数える。辺の種類はm(m-1)/2ある。ここからm-1辺を選ぶから、 m(m-1)/2Cm-1 そのうち、連結なグラフの数をT(m)で表す。前々回、T(4…

これを、例にしよう。教科書にはだいたい最初に隣接行列が書いてある。2点をそれぞれ行と列と考えて、その点同士が辺でつながっていれば要素を1、つながっていなければ0とする。これを隣接行列という。Pythonで書くと、 g = [ [ 0, 0, 1, 1 ], [ 0, 0, 0, 0 …

頭の中であれこれ考えてみたが、この問題はかなり難しい。 グラフとは、点とそれを結ぶ辺からなる対象である。 点がm個あり、それをランダムにn個の辺で結んだ場合、そのグラフが連結である確率はどうなるだろう。ただし、辺は同じ点同士を複数回結ばないと…

良いもの。悪いもの。: C++のテンプレートで素数を求めるを参考にさせてもらった。これとちがって、Primeとするとn番目の素数を求める。 テンプレートの引数を説明すると、nはいいとして、pは今調べている素数候補、iはpが割り切れるかどうか調べているi番目…