0
$\begingroup$

Consider this problem: Say we have $n$ nodes, each node has a maximum degree $d_i$ with $1 \le i \le n$. We want to construct a tree that contains all $n$ nodes and where a node $i$ can have at most $d_i$ children. The goal is to build a tree with minimal height.

Intuitively, I see that a simple algorithm to achieve this would be to put nodes with a highest degree closer to the root. However, I do not quite see how I can mathematically prove this.

Can someone help me start on this problem, are there tree properties that could be useful?

Thanks in advance for your help!

$\endgroup$
0
$\begingroup$

When you want to prove the optimality of an algorithm like this, it is often useful to suppose that $\mathcal{O}$ is an optimal solution. Then show that your solution does no worse than $\mathcal{O}$ on any instance to the problem with respect to the optimized variable. But first, you need to formalize exactly how the algorithm you wish to prove optimal operates, so that you have formal statements to work with. For the idea of "putting nodes with highest degree closer to the root", we could try:

  1. Label the nodes as $v_1, v_2, \dots, v_n$ so that they are sorted in decreasing order of maximum degree: $d_1 \ge d_2 \ge \cdots \ge d_n$.
  2. Let $v_1$ be the root of the tree.
  3. Let the $d_1$ children of $v_1$ be $v_2, v_3, \dots, v_{1+d_1}$.
  4. Let the $d_2, d_3, \dots, d_{d_1+1}$ children of $v_2, v_3, \dots, v_{1+d_1}$, respectively, be: \begin{gather*} v_2: v_{2+d_1}, v_{3+d_1}, \dots, v_{1+d_1+d_2} \\ v_3: v_{2+d_1+d_2}, v_{3+d_1+d_2}, \dots, v_{1+d_1+d_2+d_3} \\ \vdots \\ v_{1+d_1}: v_{2+\sum_{i=1}^{d_1} d_i}, v_{3+\sum_{i=1}^{d_1} d_i}, \dots, v_{1+\sum_{i=1}^{d_1+1} d_i} \end{gather*}
  5. Continue as in step 4 filling out each level of the tree. If there are $m$ nodes $v_j, v_{j+1}, \dots, v_{j+m-1}$ in a level, then we take the next $\sum_{i=j}^{j+m-1} d_i$ nodes in the list, starting with the first node not taken, $v_{j+m}$. The first $d_j$ will be children of $v_j$, the next $d_{j+1}$ children of $v_{j+1}$, and so on until the final $d_{j+m-1}$ nodes are children of $v_{j+m-1}$. Since there is a finite number $n$ of nodes, this process will always terminate in a finite number of steps.

Now that we have a description of the algorithm, we can start talking about the optimality. Suppose $\mathcal{O}$ is an optimal solution. That is, for a given set of nodes $V = \{v_1,\dots,v_n\}$, the solution $\mathcal{O}$ yields a set $E \subseteq \binom{V}{2}$ of edges such that the graph $(V,E)$ is a tree of minimal height $k$. This means that for any possible set of edges $E'\subseteq \binom{V}{2}$ among the vertices $V$, if $(V,E')$ is a tree of height $k'$, then $k'\ge k$. Now we want to compare our algorithm to $\mathcal{O}$. I think this is a decent set-up, so I'll leave the rest for you to figure out.

$\endgroup$
  • $\begingroup$ For a finite set $A$, the notation $\binom{A}{n}$ is the set of subsets of $A$ of size $n$. So, $\binom{V}{2}$ is the set of all possible edges of in a graph with vertex set $V$. $\endgroup$ – Sylexzer Mar 6 '17 at 21:36

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.