n点の木の場合の数は、 T(2) = 1 T(3) = 3 T(4) = 16 T(5) = 125 T(6) = 1296 T(7) = 16807 T(8) = 262144 T(9) = 4782969 T(10) = 100000000となっている。これは明らかに、 T(n) = nn-2 である。 なぜこうなるかあれこれ考えてみたがわからない。しかし、…

m点でn辺のグラフが連結である確率を疑似乱数を使って計算している。 今回は、PythonからC++に移植して少し工夫した。すると、速度が100倍になった。そこで、繰り返し回数を10万回にして、m=3200を追加した。疑似乱数が少し気になるが、この問題ではあまり気…

同じことを点の数25,50,100,200,400,800,1600で行った。少し工夫して速くしたコードは下。そして、連結である確率が0.5,0.9,0.99を通過するn/mをプロットした。このグラフで見る限り、連結である確率が一定のn/mはlogmの1次関数のようである。0.99なら、 n =…

点の数を決めて、ランダムに辺を加えていって、何本目の辺を加えたときに連結になるかを調べた。点の数は、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…

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