m点で辺の数がnのときのすべての場合について、連結かどうか判定する。
まず、m点なら可能な辺の数は、m点から2点選ぶから、m(m-1)/2、そのうちn辺を選ぶから、m(m-1)/2Cnの場合がある。それをすべて列挙する。次のような組合せを列挙するジェネレータを作った。
def combination(n, m):
c = range(m)
yield c
while True:
if c[m-1] != n - 1:
c[m-1] += 1
yield c[:]
else:
i = m - 2
while True:
if c[i] < c[i+1] - 1:
c[i] += 1
for j in range(i + 1, m):
c[j] = c[j - 1] + 1
yield c[:]
break
if i == 0:
return
i -= 1
これで、
for c in combination(4, 2):
print c,
とすると、
[0, 1] [0, 2] [0, 3] [1, 2] [1, 3] [2, 3]
と表示される。
さらに、エッジ番号から点のペアに変換する関数を書いて、グラフを作り、それぞれのグラフについて連結性の判定を行った。
また、n点のとき連結であるにはn-1辺が必要だが、いくつ辺があれば必ず連結であるだろうか。連結部が2つあるとすると、点がkとn-k個にそれぞれ分かれる。そのとき最大の辺の数は、
k(k-1)/2 + (n-k)(n-k-1)/2 = k2 - nk - n(n-2)/2
だから、明らかに1点とn-1点に分かれるとき最大の辺数になる。このとき、(n-1)(n-2)/2だから、分かれたときのほうが可能な最大の辺数が少なくなる。よって、連結でないときの最大の辺数は(n-1)(n-2)/2で、ここまで調べればよいことになる。
コードは例によって下で、これを動かしてみたところ、8点の途中までしか結果が出なかった。
| m | n | 連結の場合の数 | 全体の場合の数 | 連結である確率 |
|---|---|---|---|---|
| 4 | 3 | 16 | 20 | 0.8000000 |
| 5 | 4 | 125 | 210 | 0.5952381 |
| 5 | 5 | 222 | 252 | 0.8809524 |
| 5 | 6 | 205 | 210 | 0.9761905 |
| 6 | 5 | 1296 | 3003 | 0.4315684 |
| 6 | 6 | 3660 | 5005 | 0.7312687 |
| 6 | 7 | 5700 | 6435 | 0.8857809 |
| 6 | 8 | 6165 | 6435 | 0.9580420 |
| 6 | 9 | 4945 | 5005 | 0.9880120 |
| 6 | 10 | 2997 | 3003 | 0.9980020 |
| 7 | 6 | 16807 | 54264 | 0.3097265 |
| 7 | 7 | 68295 | 116280 | 0.5873323 |
| 7 | 8 | 156555 | 203490 | 0.7693498 |
| 7 | 9 | 258125 | 293930 | 0.8781853 |
| 7 | 10 | 331506 | 352716 | 0.9398666 |
| 7 | 11 | 343140 | 352716 | 0.9728507 |
| 7 | 12 | 290745 | 293930 | 0.9891641 |
| 7 | 13 | 202755 | 203490 | 0.9963880 |
| 7 | 14 | 116175 | 116280 | 0.9990970 |
| 7 | 15 | 54257 | 54264 | 0.9998710 |
| 8 | 7 | 262144 | 1184040 | 0.2213979 |
| 8 | 8 | 1436568 | 3108105 | 0.4622006 |
| 8 | 9 | 4483360 | 6906900 | 0.6491132 |
| 8 | 10 | 10230360 | 13123110 | 0.7795683 |
def combination(n, m):
c = range(m)
yield c
while True:
if c[m-1] != n - 1:
c[m-1] += 1
yield c[:]
else:
i = m - 2
while True:
if c[i] < c[i+1] - 1:
c[i] += 1
for j in range(i + 1, m):
c[j] = c[j - 1] + 1
yield c[:]
break
if i == 0:
return
i -= 1class cGraph:
def __init__(self, n):
self.n = n
self.g = [ ];
for i in range(n):
self.g.append([ ])
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 edef edge_to_vertices(i, n):
r = i
j = 0
while r >= n - 1 - j:
r -= n - 1 - j
j += 1
return [ j, r + j + 1 ]def calc_connected_probability(m, n):
counter = 0
counter_conn = 0
for c in combination(m * (m - 1) / 2, n):
g = cGraph(m)
for e in c:
v = edge_to_vertices(e, m)
g.add_edge(v[0], v[1])
if g.is_connective():
counter_conn += 1
counter += 1
print "%d %d %d %d %e" % ( m, n, counter_conn, counter,
float(counter_conn) / counter )for m in range(4, 10):
for n in range(m - 1, m * (m - 3) / 2 + 2):
calc_connected_probability(m, n)
