2
$\begingroup$

This is the problem:

$d_{T}(v)$ denotes the degree of a vertex in a spanning tree $T$ and $w: V \rightarrow R^+$ is a weight function defined on vertices.

The goal is an algorithm that finds a spanning tree which minimizes the value $\sum_{v \in V}{d_{T}(v)*w(v)}$.

My idea is to define a new weight function on edges in the following way: $m(e_{ij})=w(v_i)+w(v_j)$, i.e. the weight of each edge is the weight of both of its vertices.

Then we run Kruskal on a graph with the given $m$ weight function. The problem is that I have no idea how to prove that it works.

I thought about starting with the expression $min \sum_{e \in E}{m(e)}$ which Kruskal yields, and then somehow change the summation to be over vertices. How can it be done?

Thanks!

$\endgroup$
3
$\begingroup$

It doesn't matter which minimum spanning tree algorithm you use. All you need to notice is that for a tree $T$, $$ \begin{align*} \sum_{(i,j) \in T} m(e_{ij}) &= \sum_{(i,j) \in T} w(v_i) + w(v_j) \\ &= \sum_i \sum_{(i,j) \in T} w(v_i) + \sum_j \sum_{(i,j) \in T} w(v_j) \\ &= 2 \sum_i d_T(i) w(v_i). \end{align*} $$ You take it from here.

$\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.