close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Counting Spanning Trees
Kun-Mao Chao (趙坤茂)
Department of Computer Science
and Information Engineering
National Taiwan University, Taiwan
E-mail: [email protected]
WWW: http://www.csie.ntu.edu.tw/~kmchao
Spanning Trees
• A spanning tree for a graph G is a subgraph
of G that is a tree and contains all the
vertices of G.
1
2
1
2
1
2
1
2
3
4
3
4
3
4
3
4
2
All 16 spanning trees of K4
1
2
1
2
1
2
1
2
3
4
(a) (1, 1)
3
4
(b) (1, 2)
3
4
(c) (1, 3)
3
4
(d) (1, 4)
1
1
1
1
2
2
2
2
3
4
(e) (2, 1)
3
4
(f) (2, 2)
3
4
(g) (2, 3)
3
4
(h) (2, 4)
1
1
1
1
2
2
2
2
3
4
(i) (3, 1)
3
4
(j) (3, 2)
3
4
(k) (3, 3)
3
4
(l) (3, 4)
1
1
1
1
2
3
4
(m) (4, 1)
2
3
4
(n) (4, 2)
2
3
4
(o) (4, 3)
2
3
4
(p) (4, 4)
3
Cayley’s formula
• Back in 1889, Cayley devised the wellknown formula nn-2 for the number of
spanning trees in the complete graph Kn
• The first explicit combinatorial proof of
Cayley's formula was given by Pr\"{u}fer
7
in 1918. 1
5
3
2
4
6
8
4
Pr\"{u}fer sequence
• A Pr\"{u}fer sequence of length n-2, for n
>= 2, is any sequence of integers between 1
and n, with repetitions allowed.
• There are nn-2 Pr\"{u}fer sequences of
length n-2.
5
6
7
5
1
3
7
4
3
6
2
5
1
4
6
2
8
8
(b) P = (3, 3)
(a) P = (3)
7
5
1
3
7
4
3
6
2
5
1
4
6
2
8
8
(c) P = (3, 3, 4)
(d) P = (3, 3, 4, 5)
7
5
1
3
2
7
5
1
4
3
6
2
4
6
8
(e) P = (3, 3, 4, 5, 4)
8
(f) P = (3, 3, 4, 5, 4, 6)
7
8
7
5
1
3
7
4
3
6
2
5
1
4
6
2
8
(a) P = (3, 3, 4, 5, 4, 6); V={1, 2, 3, 4, 5, 6, 7, 8}
8
(b) P = (3, 4, 5, 4, 6); V={2, 3, 4, 5, 6, 7, 8}
7
5
1
3
7
4
3
6
2
5
1
4
6
2
8
(c) P = (4, 5, 4, 6); V={3, 4, 5, 6, 7, 8}
8
(d) P = (5, 4, 6); V={4, 5, 6, 7, 8}
7
5
1
3
7
1
4
3
6
2
5
2
4
6
8
(e) P = (4, 6); V={4, 5, 6, 8}
8
(f) P = (6); V={4, 6, 8}
7
5
1
3
2
4
6
8
(g) P = ( ); V={6, 8}
9
Try the following Pr\"{u}fer
sequences
Assume that the vertex set is {1, 2 ,3, 4, 5, 6, 7, 8}.
• 6 3 2 5 4 1 (a line)
• 5 6 3 2 1 8
• 1 1 1 3 3 3 (two-star)
• 1 3 1 3 1 3
• 1 1 1 1 1 1 (star)
• 1 1 1 1 1 2
• 1 2 3 4 5 6
• 6 5 4 3 2 1
10
Knuth’s talk on counting spanning
trees
• Donald E. Knuth gave a lecture on counting
spanning trees in December 2003. (In fact,
he likes to talk about trees in the Christmas
season. Christmas trees …)
Try it?
11
1/--страниц
Пожаловаться на содержимое документа