Counting Spanning Trees

Presentation on theme: "Counting Spanning Trees"— Presentation transcript:

1 Counting Spanning Trees
Kun-Mao Chao (趙坤茂) Department of Computer Science and Information Engineering National Taiwan University, Taiwan WWW:

2 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.

3 All 16 spanning trees of K4

4 Cayley’s formula Back in 1889, Cayley devised the well-known formula nn-2 for the number of spanning trees in the complete graph Kn The first explicit combinatorial proof of Cayley's formula is due to Pr\"{u}fer.

5 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.

6

7

8

9

10 Try the following Pr\"{u}fer sequences
Assume the vertex set is {1, 2 ,3, 4, 5, 6, 7, 8}. (a line) (two-star) (star)

11 Knuth’s talk on counting spanning trees
Donald E. Knuth gave a lecture on spanning trees last December. (In fact, he likes to talk about trees in the Christmas season. Christmas trees …) Try it?

12 元宵燈謎 (字謎) 路上行人走，小月照其上 兩人共有十五顆心 日落半林中　 太陽掛在樹頂上 李字少了木，不作子字猜 百年前是草，百年後是木

13 元宵燈謎 (字謎) 路上行人走，小月照其上 趙 兩人共有十五顆心 德 日落半林中 東 太陽掛在樹頂上 果 李字少了木，不作子字猜 一
路上行人走，小月照其上　　　　　趙 兩人共有十五顆心　　　　　　　　德 日落半林中　　　　　　　　　　　東 太陽掛在樹頂上　　　　　　　　　果 李字少了木，不作子字猜　　　　　一 百年前是草，百年後是木　　　　　葉

14 回應與挑戰（一） 同學：停電，猜一字 趙老：．．． 同學：請用英文想 同學：停電是black out 趙老：原來是黑出，黜！

15 回應與挑戰（二） 趙老：我在水中，猜一字 同學：．．． 趙老：請用英文想 趙老：是一個英文字，I in the WATER
同學：原來是WAITER！