Counting Spanning Trees

Slides:



Advertisements
Similar presentations
我们首先引入的计算概率的数学模型, 是在概率论的发展过程中最早出现的研究 对象,通常称为 古典概型.
Advertisements

昆明机场. 目录  机场历史 机场历史  建设状况 建设状况  运行状况 运行状况  航线 航线.
第十四章 人口(二) 高中地理(一). 第一節 人口成長 第二節 人口組成 第三節 人口問題 第十四章 人口(二)
海伦深深地感激自己的老师, 她说:假如给我三天光明,我 首先要长久地凝视我的老师 — — 安妮 · 莎莉文 !
中國歷史 社會主義文化大革命 我們的報告是關於中國著名的革命 —— 文化大革命。你可會立即想到它何時發 生、怎麼會發生等等。我們將會介紹文 化大革命,希望你細心欣賞。
党课讲座 入党的条件与程序.
中國大陸教育 督導制度探究 凌林煌教授/博士 講授 國立中山大學共同科歷史學程
温故知新 犬 戎 公元前 770年 周平王 公元前771年 东周 洛邑 西周 镐京.
对应用型本科建设中若干问题的认识 张家钰
让我们走进秋天.
我国政府受人民的监督 权力的行使:需要监督.
鹽酥蝦 蝦子先處理好 蝦頭剪至眼睛處,鬚及蝦頭的小腳也都剪乾淨 2 再用廚房用剪刀開背去腸泥
成功的招聘 一、明确用人需求 二、做好面试前的准备 三、行为事例STAR法 四、在面试中恰当的提问 五、做出正确的选聘决定.
專題討論(二) 朴子溪流域漥蓄區位之萃取及應用
第十一章 真理与价值 主讲人:阎华荣.
在悠久的海洋歲月裡 有你我的回憶....
Chapter 12 圖形結構 12.1 圖形的一些專有名詞 12.2 圖形資料結構表示法 12.3 圖形追蹤 12.4 擴展樹
第七章 固 定 资 产.
水土保持法概觀 水保所 碩一 劉大正 陳奕銓.
时代发展趋势: 科学人文交融 华中科技大学 杨叔子 2010年2月修改.
教師升等資料準備說明會 國立屏東科技大學 報告單位:人事室 報告日期:104年6月8日
行政院國軍退除役官兵輔導委員會 嘉義榮民醫院.
Minimum Spanning Trees
Department of Computer Science & Information Engineering
Chap5 Graph.
Chapter 6 Graph Chang Chi-Chung
CeBIT 2017 A note given in BCC class on March 14, 2017
COMPUTEX 2014 A note given in BCC class on June 4, 2014
Chapter 7 圖形與網路 資料結構導論 - C語言實作.
Chapter12 Graphs Definitions Applications Properties
SaaS流程模型的自动演化 Research Group for Cooperative Information Systems
Ch07 圖形與網路 淡江大學 周清江
COMPUTEX 2014 A note given in BCC class on June 4, 2014
Computex 2018 A note given in BCC class on May 29, 2018
公立學校教職員退休資遣撫卹條例重點說明 苗栗縣政府人事處編製 主講人:陳處長坤榮 107年5月2日.
French Open 2014 A note given in BCC class on June 11, 2014
National Taiwan University
今天, AC 你 了吗? 2019/4/21.
圖論的介紹 第二組 徐榮德 鄭又齊 陳俊嘉.
CeBIT 2015 A note given in BCC class on March 18, 2015
崑山科技大學 電子工程系 99學年度 學生實務專題成果展
A Circular Sequence (This phrase can start at any word.)
冀教版 九年级 Lesson 20: Say It in Five.
鄧姚文 資料結構 第八章:圖(Graph) 鄧姚文
Introduction to Computer Science
计算机问题求解 – 论题 图的连通度 2018年11月13日.
半 導 體 概 論 Ming-Lun Lee (李明倫) Department of Electro-Optical Engineering
人事業務績效報告分享 報告人:南屯區大墩國小 徐湘雲.
班級經營分享 主講人:吳姈娟 時間:104年3月4日.
西师大版语文六年级上册第五单元 19.韦德的心愿.
Arguments to the main Function and Final Project
Computex 2019 A note given in BCC class on May 23, 2019
Konig 定理及其证明 杨欣然
Trees Kun-Mao Chao (趙坤茂)
國立清華大學 National Tsing Hua University
Advanced Competitive Programming
Advanced Competitive Programming
組長:李儂.組員:溫芷沂.詹文君 桃園市北門國小5年12班
圖形結構 Graph Structure chapter 9 德明科技大學資訊科技系.
Tree Riddles Kun-Mao Chao (趙坤茂)
Tree Riddles Kun-Mao Chao (趙坤茂)
DDoS A note given in BCC class on May 15, 2013 Kun-Mao Chao (趙坤茂)
A Circular Sequence (This phrase can start at any word.)
A Circular Sequence (This phrase can start at any word.)
Counting Spanning Trees
Graph 1 Michael Tsai 2012/4/24 連載: 學生上課睡覺姿勢大全
Advanced Competitive Programming
计算机问题求解---论题3-12 图中的匹配与因子分解
Department of Mechatronic Technology National Taiwan Normal University
Presentation transcript:

Counting Spanning Trees Kun-Mao Chao (趙坤茂) Department of Computer Science and Information Engineering National Taiwan University, Taiwan E-mail: kmchao@csie.ntu.edu.tw 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.

All 16 spanning trees of K4

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.

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.

Try the following Pr\"{u}fer sequences Assume 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

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?

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

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

回應與挑戰(一) 同學:停電,猜一字 趙老:... 同學:請用英文想 同學:停電是black out 趙老:原來是黑出,黜!

回應與挑戰(二) 趙老:我在水中,猜一字 同學:... 趙老:請用英文想 趙老:是一個英文字,I in the WATER 同學:原來是WAITER!