组合数学 (Spring 2013)/Cayley's formula: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
← Older editNewer edit →
VisualWikitext
imported>Etone
imported>Etone
Line 68: Line 68:


Therefore, the Prüfer code establishes a bijection between the set of trees on <math>n</math> distinct vertices and the tuples from <math>\{1,2,\ldots,n\}^{n-2}</math>. This proves Cayley's formula.
Therefore, the Prüfer code establishes a bijection between the set of trees on <math>n</math> distinct vertices and the tuples from <math>\{1,2,\ldots,n\}^{n-2}</math>. This proves Cayley's formula.
== Double counting ==
We now present a proof of the Cayley's formula by double counting, which is considered by the [http://en.wikipedia.org/wiki/Proofs_from_THE_BOOK Proofs from THE BOOK] "the most beautiful of them all".
{{Prooftitle|Proof of Cayley's formula by double counting|
(Due to Pitman 1999)
Let <math>T_n</math> be the number of different trees defined on <math>n</math> distinct vertices.
A '''rooted tree''' is a tree with a special vertex. That is, one of the <math>n</math> vertices is marked as the "root" of the tree. A rooted tree defines a natural direction of all edges, such that an edge <math>uv</math> of the tree is directed from <math>u</math> to <math>v</math> if <math>u</math> is before <math>v</math> along the unique path from the root.
We count the number of different ''sequences'' of directed edges that can be added to an empty graph on <math>n</math> vertices to form from it a ''rooted'' tree. We note that such a sequence can be formed in two ways:
# Starting with an unrooted tree, choose one of its vertices as root, and fix an total order of edges to specify the order in which the edges are added.
# Starting from an empty graph, add the edges one by one in steps.
In the first method, we pick one of the <math>T_n</math> unrooted trees, choose one of the <math>n</math> vertices as the root, and pick one of the <math>(n-1)!</math> total orders of the <math>n-1</math> edges. This gives us <math>T_nn(n-1)!=T_nn!</math> ways.
In the second method, we consider the number of choices in one step, and multiply the numbers of choices in all steps. This is done as follows.
Given a sequence of ''adding'' <math>n-1</math> edges to an empty graph to form a rooted tree, we reverse this sequence and get a sequence of ''removing'' edges one by one from the final rooted tree until no edge left. We observe that:
* At first, we remove an edge from the rooted tree. Suppose that the root of the tree is <math>r</math>, and the removed directed edge is <math>(u,v)</math>.  After removing <math>(u,v)</math>, the original rooted tree is disconnected into two rooted trees, one rooted at <math>r</math> and the other rooted at <math>v</math>.
* After removing <math>k-1</math> edges, there are <math>k</math> rooted trees. In the <math>k</math>th step, a directed edge <math>(u,v)</math> in the current forest is removed and the tree containing <math>(u,v)</math> is disconnected into two trees, one rooted at the old root of that tree, and the other rooted at <math>v</math>.
We now again reverse the above procedure, and consider the sequence of adding directed edges to an empty graph to form a rooted tree.
* At first, we have <math>n</math> rooted trees, each of 0 edge (<math>n</math> isolated vertices).
* After adding <math>n-k</math> edges, there are <math>k</math> rooted trees. Denoting the directed edge added next as <math>(u,v)</math>. As observed above, <math>u</math> can be any one of the <math>n</math> vertices; but <math>v</math> must be the root of one of the <math>k</math> trees, except the tree which contains <math>u</math>. There are <math>n(k-1)</math> choices of such <math>(u,v)</math>.
Multiplying the numbers of choices in all steps, the number of sequences of adding directed edges to an empty graph to form a rooted tree is given by
:<math>\prod_{k=2}^nn(k-1)=n^{n-2}n!</math>.
By the principle of double counting, counting the same thing by different methods yield the same result.
:<math>T_nn!=n^{n-2}n!</math>,
which gives that <math>T_n=n^{n-2}</math>.
}}


= Kirchhoff's Matrix-Tree Theorem =
= Kirchhoff's Matrix-Tree Theorem =

Revision as of 07:22, 18 April 2013

Cayley's Formula

We now present a theorem of the number of labeled trees on a fixed number of vertices. It is due to Cayley in 1889. The theorem is often referred by the name Cayley's formula.

Cayley's formula for trees
There are [math]\displaystyle{ n^{n-2} }[/math] different trees on [math]\displaystyle{ n }[/math] distinct vertices.

The theorem has several proofs. Classical methods include the bijection which encodes a tree by a Prüfer code, through the Kirchhoff's matrix tree theorem, and by double counting.

Prüfer code

The Prüfer code encodes a labeled tree to a sequence of labels. This gives a bijections between trees and tuples.

In a tree, the vertices of degree 1 are called leaves. It is easy to see that:

  • each tree has at least two leaves; and
  • after removing a leaf (along with the edge adjacent to it) from a tree, the resulting graph is still a tree.

The following algorithm transforms a tree [math]\displaystyle{ T }[/math] of [math]\displaystyle{ n }[/math] vertices [math]\displaystyle{ 1,2,\ldots,n }[/math], to a tuple [math]\displaystyle{ (v_1,v_2,\ldots,v_{n-2})\in\{1,2,\ldots,n\}^{n-2} }[/math].

Prüfer code (encoder)
Input: A tree [math]\displaystyle{ T }[/math] of [math]\displaystyle{ n }[/math] distinct vertices, labeled by [math]\displaystyle{ 1,2,\ldots,n }[/math].
let [math]\displaystyle{ T_1=T }[/math];
for [math]\displaystyle{ i=1 }[/math] to [math]\displaystyle{ n-1 }[/math], do
let [math]\displaystyle{ u_i }[/math] be the leaf in [math]\displaystyle{ T_i }[/math] with the smallest label, and [math]\displaystyle{ v_i }[/math] be its neighbor;
let [math]\displaystyle{ T_{i+1} }[/math] be the new tree obtained from deleting the leaf [math]\displaystyle{ u_i }[/math] from [math]\displaystyle{ T_i }[/math];
end
return [math]\displaystyle{ (v_1,v_2,\ldots,v_{n-2}) }[/math];

It is trivial to observe the following lemma:

Lemma 1
For each [math]\displaystyle{ 1\le i\le n-1 }[/math], [math]\displaystyle{ T_i }[/math] is a tree of [math]\displaystyle{ n-i+1 }[/math] vertices. In particular, the vertices of [math]\displaystyle{ T_i }[/math] are [math]\displaystyle{ u_i,u_{i+1},\ldots,u_{n-1},v_{n-1} }[/math], and the edges of [math]\displaystyle{ T_i }[/math] are precisely [math]\displaystyle{ \{u_j,v_j\} }[/math], [math]\displaystyle{ i\le j\le n-1 }[/math].

And there is a reason that we do not need to store [math]\displaystyle{ v_{n-1} }[/math] in the Prüfer code.

Lemma 2
It always holds that [math]\displaystyle{ v_{n-1}=n }[/math].
Proof.

Every tree (of at least two vertices) has at least two leaves. The [math]\displaystyle{ u_i }[/math], [math]\displaystyle{ 1\le i\le n-1 }[/math], are the leaf of the smallest label in [math]\displaystyle{ T_i }[/math], which can never be [math]\displaystyle{ n }[/math], thus [math]\displaystyle{ n }[/math] is never deleted.

[math]\displaystyle{ \square }[/math]

Lemma 1 and 2 together imply that given a Prüfer code [math]\displaystyle{ (v_1,v_2,\ldots,v_{n-2}) }[/math], the only remaining task to reconstruct the tree [math]\displaystyle{ T }[/math] is to figure out those [math]\displaystyle{ u_i }[/math], [math]\displaystyle{ 1\le i\le n-1 }[/math]. The following lemma state how to obtain [math]\displaystyle{ u_i }[/math], [math]\displaystyle{ 1\le i\le n-1 }[/math], from a Prüfer code [math]\displaystyle{ (v_1,v_2,\ldots,v_{n-2}) }[/math].

Lemma 3
For [math]\displaystyle{ i=1,2,\ldots,n-1 }[/math], [math]\displaystyle{ u_i }[/math] is the smallest element of [math]\displaystyle{ \{1,2,\ldots,n\} }[/math] not in [math]\displaystyle{ \{u_1,\ldots,u_{i-1}\}\cup\{v_i,\ldots,v_{n-1}\} }[/math].
Proof.

Note that [math]\displaystyle{ u_1,u_2,\ldots,u_{n-1},v_{n-1} }[/math] is a sequence of distinct vertices, because [math]\displaystyle{ u_1,u_2,\ldots,u_{n-1} }[/math] are deleted one by one from the tree, and [math]\displaystyle{ v_{n-1}=n }[/math] is never deleted. Thus, each vertex [math]\displaystyle{ v }[/math] appears among [math]\displaystyle{ u_1,u_2,\ldots,u_{n-1},v_{n-1} }[/math] exactly once. And each vertex [math]\displaystyle{ v }[/math] appears for [math]\displaystyle{ deg(v) }[/math] times among the edges [math]\displaystyle{ \{u_i,v_i\} }[/math], [math]\displaystyle{ 1\le i\le n-1 }[/math], where [math]\displaystyle{ deg(v) }[/math] denotes the degree of vertex [math]\displaystyle{ v }[/math] in the original tree [math]\displaystyle{ T }[/math]. Therefore, each vertex [math]\displaystyle{ v }[/math] appears among [math]\displaystyle{ v_1,v_2,\ldots,v_{n-2} }[/math] for [math]\displaystyle{ deg(v)-1 }[/math] times.

Similarly, each vertex [math]\displaystyle{ v }[/math] of [math]\displaystyle{ T_i }[/math] appears among [math]\displaystyle{ v_i,v_{i+1},\ldots,v_{n-2} }[/math] for [math]\displaystyle{ deg_i(v)-1 }[/math] times, where [math]\displaystyle{ deg_i(v) }[/math] is the degree of vertex [math]\displaystyle{ v }[/math] in the tree [math]\displaystyle{ T_i }[/math]. In particular, the leaves of [math]\displaystyle{ T_i }[/math] are not among [math]\displaystyle{ \{v_i,v_{i+1},\ldots,v_{n-2}\} }[/math]. Recall that the vertices of [math]\displaystyle{ T_i }[/math] are [math]\displaystyle{ u_i,u_{i+1},\ldots,u_{n-1},v_{n-1} }[/math]. Then the leaves of [math]\displaystyle{ T_i }[/math] are the elements of [math]\displaystyle{ \{1,2,\ldots,n\} }[/math] not in [math]\displaystyle{ \{u_1,\ldots,u_{i-1}\}\cup\{v_i,\ldots,v_{n-1}\} }[/math]. By definition of Prüfer code, [math]\displaystyle{ u_i }[/math] is the leaf in [math]\displaystyle{ T_i }[/math] of smallest label, hence the smallest element of [math]\displaystyle{ \{1,2,\ldots,n\} }[/math] not in [math]\displaystyle{ \{u_1,\ldots,u_{i-1}\}\cup\{v_i,\ldots,v_{n-1}\} }[/math].

[math]\displaystyle{ \square }[/math]

Applying Lemma 3, we have the following decoder for the Prüfer code:

Prüfer code (decoder)
Input: A tuple [math]\displaystyle{ (v_1,v_2,\ldots,v_{n-2})\in\{1,2,\ldots,n\}^{n-2} }[/math].
let [math]\displaystyle{ T }[/math] be empty graph, and [math]\displaystyle{ v_{n-1}=n }[/math];
for [math]\displaystyle{ i=1 }[/math] to [math]\displaystyle{ n-1 }[/math], do
let [math]\displaystyle{ u_i }[/math] be the smallest label not in [math]\displaystyle{ \{u_1,\ldots,u_{i-1}\}\cup\{v_i,\ldots,v_{n-1}\} }[/math];
add an edge [math]\displaystyle{ \{u_i,v_i\} }[/math] to [math]\displaystyle{ T }[/math];
end
return [math]\displaystyle{ T }[/math];

In other words, the encoding of trees to tuples by the Prüfer code is reversible, thus the mapping is injective (1-1). To see it is also surjective, we need to show that for every possible [math]\displaystyle{ (v_1,v_2,\ldots,v_{n-2})\in\{1,2,\ldots,n\}^{n-2} }[/math], the above decoder recovers a tree from it.

It is easy to see that the decoder always returns a graph of [math]\displaystyle{ n-1 }[/math] edges on the [math]\displaystyle{ n }[/math] vertices. The only thing remaining to verify is that the returned graph has no cycle in it, which can be easily proved by a timeline argument (left as an exercise).

Therefore, the Prüfer code establishes a bijection between the set of trees on [math]\displaystyle{ n }[/math] distinct vertices and the tuples from [math]\displaystyle{ \{1,2,\ldots,n\}^{n-2} }[/math]. This proves Cayley's formula.

Kirchhoff's Matrix-Tree Theorem

Given an undirected graph [math]\displaystyle{ G([n],E) }[/math], the adjacency matrix [math]\displaystyle{ A }[/math] of graph [math]\displaystyle{ G }[/math] is an [math]\displaystyle{ n\times n }[/math] matrix such that

[math]\displaystyle{ A(i,j)=\begin{cases} 1 & \{i,j\}\in E,\\ 0 & \{i,j\}\not\in E. \end{cases} }[/math]

Let [math]\displaystyle{ D }[/math] be a [math]\displaystyle{ n\times n }[/math] diagonal matrix such that

[math]\displaystyle{ D(i,j)=\begin{cases} \text{deg}(i) & i=j,\\ 0 & i\neq j, \end{cases} }[/math]

where [math]\displaystyle{ \text{deg}(i) }[/math] denotes the degree of vertex [math]\displaystyle{ i }[/math].

The Laplacian matrix [math]\displaystyle{ L }[/math] of graph [math]\displaystyle{ G }[/math] is defined as [math]\displaystyle{ L=D-A }[/math], that is,

[math]\displaystyle{ L(i,j)=\begin{cases} \text{deg}(i) & i=j,\\ -1 & i\neq j\text{ and } \{i,j\}\in E,\\ 0 & \text{otherwise}. \end{cases} }[/math]

Suppose [math]\displaystyle{ G([n],E) }[/math] has [math]\displaystyle{ m }[/math] edges. The incidence matrix [math]\displaystyle{ B }[/math] of graph [math]\displaystyle{ G }[/math] is an [math]\displaystyle{ n\times m }[/math] matrix such that

[math]\displaystyle{ \forall i\in[n], \forall e\in E,\quad B(i,e)=\begin{cases} 1 & e=\{i,j\}\text{ and } i\lt j,\\ -1 & e=\{i,j\}\text{ and } i\gt j,\\ 0 & \text{otherwise}. \end{cases} }[/math]

The following proposition is easy to verify.

Proposition
[math]\displaystyle{ L=BB^T }[/math].
Proof.

For any [math]\displaystyle{ i,j\in[n] }[/math], we have

[math]\displaystyle{ (BB^T)(i,j)=\sum_{e\in E}B(i,e)B^T(e,j)=\sum_{e\in E}B(i,e)B(j,e) }[/math].

It is easy to verify that

[math]\displaystyle{ \sum_{e\in E}B(i,e)B(j,e)= \begin{cases} \text{deg}(i) & i=j,\\ -1 & i\neq j\text{ and } \{i,j\}\in E,\\ 0 & \text{otherwise}, \end{cases} }[/math]

which is equal to the definition of [math]\displaystyle{ L }[/math].

[math]\displaystyle{ \square }[/math]
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=组合数学_(Spring_2013)/Cayley%27s_formula&oldid=5576"