1
$\begingroup$

Suppose that there are $n$ nodes, and that edge $e$ of weight $w_e$ cuts the tree into parts of size $k_e,n-k_e$. Then the average distance is $$ \sum_e w_e k_e (n-k_e). $$ For example : n=6,k=6 list=[1,2,3,4,5,6]

                    Node--------> 1
                                   \(1)<-----------Weight
                                    \
                                     3
                                (3) / \(2)
                                   /   \
                                  4     2
                             (4) / \ (5)
                                /   \
                               5     6

in this case we get $$ \ (1 \cdot 1 \cdot 5 + 2 \cdot 1 \cdot 5 + 3 \cdot 3 \cdot 3 + 4 \cdot 1 \cdot 5 + 5 \cdot 1 \cdot 5) ={87} $$

I'm storing the tree using adjacency lists.

1 approach might be to calculate size of elements of the list of the vertex connected by that edge recursively. For eg here if I cut $3-4$ I go the list of $4$ that contains $5,6$ then for every element in $4$ I go their list and calculate size of them and the vertex in it i.e go to list $5$ and $6$ and calculate size of their list. But I think this might be wrong or too long.

Now how do I find out the value of $k_e$ in the tree in a better and fast way?

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! What have you tried? What approaches have you considered? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. The question of how to compute $k_e$ sounds like a basic exercise or simple matter of programming. Since you haven't told us anything about what you've tried, it's hard to know how best to help you. $\endgroup$ – D.W. Nov 11 '16 at 1:12
  • $\begingroup$ I can't figure out anyway to find that. The original question is different. I came to a solution that involves this. Now I'm stuck at finding value of $k_e$ $\endgroup$ – Sam_Buck Nov 12 '16 at 4:20
  • $\begingroup$ @D.W. I tried this approach but it seems wrong. $\endgroup$ – Sam_Buck Nov 14 '16 at 6:51
1
$\begingroup$

You can use dynamic programming in its version for trees. Choose a root arbitrarily, and calculate recursively the number of vertices in the subtree rooted at each node. This should give you enough information to calculate $k_e$ for each edge $e$. The total running time should be $O(n)$.

I'm leaving the rest of the details for you to ponder.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.