On the last post (Prufer Code: Linear Representation of a Labeled Tree), we discussed how to convert a labeled tree into Prufer Code and vice versa. On this post, we will look into some of its applications in problem-solving.
This one is the simplest. Though problem-solving may not require generating random trees, problem setting might. In order to generate a random tree with $N$ nodes, all we need to do is generate a Prufer Code of length $N-2$ with each element being in the range of $1$ to $N$. Next, we just convert the Prufer Code into a tree.
The randomness of the tree depends on the randomness of the sequence generated. Using rand() function is not good since it's not truly random. How we can generate a random sequence requires a blog post of its own. Maybe I will write a post on it in near future.
Given $N$ labeled nodes, how many spanning trees can we build?
For example, how many different spanning trees can we build with $3$ nodes?
According to Cayley's Formula, the number of spanning trees we can build with $N$ labeled node is $N^{N-2}$.
Cayley's Formula can be proved by Prufer Code easily. Since there are $N$ nodes, what will be the length of the Prufer Code of the spanning trees? Ans: $N-2$. Next, at each position of the Prufer Code, how many different values can we place? Ans: $N$. Therefore, we have $N^{N-2}$ combinations possible for Prufer Code.
Given $N$ nodes and for each node its degree count, i.e, number of other nodes that are its neighbor, how many different spanning trees can we build while maintaining the degree count of each node?
For example, let $N=5$ and the degree count be $[3, 2, 1, 1, 1]$. How many spanning trees respect these degree constraints? Ans: $3$
So how do we find the answer using Prufer Code? We use the following two information:
So for each node, we know how many times it appears in Prufer Code from its degree count. If the degree count for $i_{th}$ node is $d_i$, then it appears $d_i-1$ times. We also know the total number of openings we have in our Prufer Code ($N-2$ openings). So the number of possible spanning tree while maintaining the degree constraint is:
$$\binom{N-2}{d_1-1} \binom{N-2-(d_1-1)}{d_2-1}...\binom{N-2-(d_1-1)-...-(d_{N-1}-1)}{d_N-1} \\ =\binom{N-2}{d_1-1,d_2-1,...,d_N-1}$$For example, when $N=5$ and degree count is $[3, 2, 1, 1, 1]$, the length of Prufer Code will be $5-2=3$ and the nodes will appear $[3-1,2-1,1-1,1-1,1-1] = [2,1,0,0,0]$ times. So answer will be $\binom{3}{2,1,0,0,0} = \binom{3}{2}\binom{1}{1}=3$.
Simple right? See if you can solve the following problem now: UVa 12956 - Curious Guardians. It's going to require DP along with what we have learned so far.
I know about one more application of Prufer Code, but I did not write about it here because its proof is a bit tricky. So I will probably write a separate post for that. If you are feeling curious about it then here is a spoiler: UVa 11719 - Gridland Airports.
If you have enjoyed learning Prufer Code, then don't forget to share it.
Labels: Combinatorics, Graph, Proof, Theorem, Tree