 | Hi all, first of all thanks for replying to previous post. I have a new
version of the problem that I'm sure has a solution this time. The goal
is to minimize the double sumation:
sum(i=1;N){sum(j=1;d_i){ a_i_j^2)}}
with the following constrains:
1. sum(j=1;d_i){a_i_j} = N-1
2. sum(i=1;N){d_i} = 2(N-1)
>From the geometric point of view, if we have a tree with node i
connected to node j:
....(i)----(j)...
then a_i_j is the number of nodes seen by the link i-j towards j
(including j). d_i is the degree of node i (number of children). N is
the total number of nodes in the tree.
So we have also:
d_i>=1
a_i_j>=1
N>0
I know the solution is a line 1--2--3...---N, where d_i=2, except for
the terminals.
Any idea how tp prove this? Thanks!
--Ricardo
|
|
