← RoseCode

ROSECODE 512

Trees gracious numberings

Philippe_57721 · Programming ·

A gracious numbering of a tree with N vertices is defined as follow:
- each vertex is numbered by a number in [0..N-1]
- each edge being numbered by the difference, in absolute value, between the values of its two vertices, the values of the edges contain all integers in [1..N-1] exactly once.

For the tree A(B,C(D,E,F)), here is an example of gracious numbering:
[A] 3
 +-B 4 
 +-[C] 5
	+-D 2 
	+-E 1 
	+-F 0 
You can verify:
[AB] = 1
[AC] = 2
[CD] = 3
[CE] = 4
[CF] = 5

It is conjectured that there exists a gracious numbering for all trees.

How many gracious numberings are there for the following tree: A(B(C,D(E,F)),G(H,I(J,K))) ?
[A]
 +-[B]
 |  +-C 
 |  +-[D]
 |     +-E 
 |     +-F 
 +-[G]
	+-H
	+-[I]
	   +-J
	   +-K 
[My timing: 20 sec]