点の数を決めて、ランダムに辺を加えていって、何本目の辺を加えたときに連結になるかを調べた。点の数は、10、20、…、100として、それぞれ10000回繰り返した。
これは段々収束していっているのだろうか。
from random import *class cGraph:
def __init__(self, n):
self.n = n
self.g = [ ];
for i in range(n):
self.g.append([ ])
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)
return True
def exists_edge(self, vs, ve):
for k in self.g[vs]:
if k == ve:
return True
return False
def is_connective(self):
a = [ 0 ] * self.n
a[0] = 1
stk = [ 0 ]
while stk:
vs = stk.pop()
for ve in self.g[vs]:
if a[ve] == 0:
a[ve] = 1
stk.append(ve)
for b in a:
if b == 0:
return False
return True
def disp(self):
for e in self.g:
print e
for m in range(10, 101, 10):
print "m : ", m
seed(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
