ROSECODE 512
Trees gracious numberings
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:
[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))) ?
- 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 0You 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]