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
である。
なぜこうなるかあれこれ考えてみたがわからない。しかし、図書館で借りてきた本に書いてあった。
- 作者: B.ボロバッシュ,斎藤伸自,西関隆夫
- 出版社/メーカー: 培風館
- 発売日: 1983/01
- メディア: 単行本
- クリック: 1回
- この商品を含むブログ (1件) を見る
一番最後の節に書いてある。しかし、意味を把握するのにすら時間がかかった。3回くらい説明文を読んだだろうか。
木の端点うち最小のものを選ぶ（左上では赤字の1）。その端点に繋がっている点をどこかに書いておく（青字の0）。そして、その端点を削除する。この作業を点の数が2になるまで繰り返す。
こうすると、青字の数字を全部拾って、[0, 0, 3]となる。数字は各成分が0〜4を取り得る。この符号（Prüfer符号）は、木と一対一の対応が取れるから、53通りある。
木の符号化が一意であることは明らか。しかし、逆はどうだろうか。
まず、4を書く。
prev <- 4
符号を逆順に見て、すでに書かれた数なら、残った最大の数（ここでは3）をprevに繋げる。そうでなかったら、その数をprevに繋げる。これを繰り返す。
以下のコードは、木を符号化し、その符号を木にして、木同士を比べて、違っていたらprintする、という作業を1000回繰り返している。
from random import *
import copyclass cGraph:
def __init__(self, n):
self.n = n
self.g = [ ];
for i in range(n):
self.g.append([ ])
def __copy__(self):
g = cGraph(self.n)
g.g = copy.deepcopy(self.g)
return g
def clear(self):
for i in range(self.n):
self.g[i] = [ ]
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 remove_vertex(self, v):
for v2 in self.g[v]:
self.g[v2].remove(v)
self.g[v] = [ ]
def is_end(self, v):
return len(self.g[v]) == 1
def get_num_edges(self):
ary_len = map(lambda x: len(x), self.g)
return reduce(lambda x, y: x + y, ary_len) / 2
def encode_prufer(self):
ary = [ ]
g = copy.copy(self)
while g.get_num_edges() > 1:
ary_end = filter(lambda x: g.is_end(x), range(self.n))
min_end = min(ary_end)
ary.append(g.g[min_end][0])
g.remove_vertex(min_end)
return ary
def decode_prufer(self, ary):
n = len(ary) + 2
g = cGraph(n)
prev = n - 1
used = [ False ] * n
for a in reversed(ary):
used[prev] = True
if used[a]:
v = reduce(max, filter(lambda x: not used[x], range(n)))
else:
v = a
g.add_edge(v, prev)
used[v] = True
prev = a
v = reduce(max, filter(lambda x: not used[x], range(n)))
g.add_edge(prev, v)
return g
def disp(self):
for e in self.g:
print e
def __eq__(self, g):
if self.n == g.n:
for i in range(self.n):
if len(self.g[i]) == len(g.g[i]):
a = sorted(self.g[i])
b = sorted(g.g[i])
for j in range(len(a)):
if a[j] != b[j]:
return False
else:
return False
return True
else:
return False
def __ne__(self, g):
return not self.__eq__(g)
def __str__(self):
a = map( lambda x: str(x), self.g)
return "\n".join(a)def makeTree(m):
g = cGraph(m)
while True:
for i in range(m - 1):
g.add_edge_at_random()
if g.is_connective():
return g
g.clear()m = 5
seed(m)
for i in range(1000):
g = makeTree(m)
e = g.encode_prufer()
g2 = g.decode_prufer(e)
if g != g2:
print False
