グラフが連結である確率(7)

同じことを点の数25,50,100,200,400,800,1600で行った。少し工夫して速くしたコードは下。

そして、連結である確率が0.5,0.9,0.99を通過するn/mをプロットした。

このグラフで見る限り、連結である確率が一定のn/mはlogmの1次関数のようである。0.99なら、


n = m(0.6475 * log(m) + 1.2583)

本当は、p = 0.999999あたりを知りたいのだが。



from random import *

class cGraph:
def __init__(self, n):
self.n = n
self.g = [ ];
for i in range(n):
self.g.append([ ])
self.a = [ 0 ] * self.n # connected to 0
self.a[0] = 1

def add_edge_at_random(self):
while True:
vs = randint(0, self.n - 1)
while True:
ve = randint(0, self.n - 1)
if vs != ve:
break
if self.add_edge(vs, ve):
return

def add_edge(self, vs, ve):
if self.exists_edge(vs, ve):
return False
else:
self.g[vs].append(ve)
self.g[ve].append(vs)
self.update_connection(vs, ve)
return True

def exists_edge(self, vs, ve):
for k in self.g[vs]:
if k == ve:
return True
return False

def update_connection(self, vs, ve):
if self.a[vs] + self.a[ve] == 1:
if self.a[vs] == 0:
vs, ve = ve, vs
self.a[ve] = 1
stk = [ ve ]
while stk:
v0 = stk.pop()
for v1 in self.g[v0]:
if self.a[v1] == 0:
self.a[v1] = 1
stk.append(v1)

def is_connective(self):
for b in self.a:
if b == 0:
return False
return True

def disp(self):
for e in self.g:
print e

m = 25
while m < 2000:
seed(m)
print "m : ", m

for k in range(10000):
g = cGraph(m)
n = 0
while True:
g.add_edge_at_random()
n += 1
if g.is_connective():
print n
break
m *= 2