8.1图的基本概念.ppt

v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 §8.2 树 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 min=1+4+9+3+17+23=57 §8.2 树 课堂练习： 3 7 4 9 3 4 6 3 2 1 Min C(T)=12 Min C(T)=15 2 5 4 1 7 3 3 1 4 4 7 5 答案： §8.2 树 3 4 1 2 2 3 2 3 2 4 2 Min C(T)=12 2 1 3 6 3 8 5 3 4 5 6 7 4 5 4 3 2 1 Min C(T)=18 §8.2 树 作业： P237 习题8.3 8.4（b） §8.2 树 小结 学习要点： 1. 理解无向图和有向图的基本概念和性质； 2. 理解树的概念和性质； 3. 掌握求支撑树的破圈法和避圈法。 The end,thank you! 后来，管校长因为那一个特殊的年份一个特殊的事件在美国发表了不恰当的言论，从云南回国时受到大学生的热烈欢迎，因此，他离开山东回了老家上海，到复旦大学任教。 大学开学典礼上，这个数学家管校长说，你们上大学，只要学会了两个能力就可以了，一个是学会学习。大家不要笑，你不要以为你已经会学习了，不一定。 中学时代，有老师跟着你教，不会的可以随时问，上了大学，不一样了。 大学老师上完课就回家了，你想问也找不到，更多的是靠你自我学习，你要不回自我学习自我教育，这四年大学上下来，可能也学不了多少东西。 学会学习表现在，你会利用图书馆，我们学校有上百万藏书，不会用太可惜了，你会利用图书馆了，就学会学习了。自我学习的能力，是一辈子的财富，离开学校走向社会，这种能力更会让你受益终生，希望你们能够学会、养成。 二是学会合作。21世纪以来，所有重大的发明发现，百分之八十以上是合作的产物，爱迪生一个人一千多项专利的时代过去了，如果你不能与人合作，不能与人很好地合作，你的一生是难有重大成就的。 过去这么多年了，我还时常记得，时常向人提起，管校长给我们的忠告。 用现在的话说，管校长讲的这两点，就是情商与智商吧。 “哥尼斯堡 7 桥”难题最终在 1736 年由数学家 Euler 的一篇论文给予了完满的解决，这是图论的第一篇论文。在后来的两百年间图论的发展是缓慢的，直到 1936 年匈牙利数学家 O.K?nig写出了图论的第一本专著《有限图与无限图的理论》。 图论的历史上最具有传奇色彩的问题也许要数著名的“四色猜想”了——历史上许许多多数学猜想之一。 世界近代三大数学难题：费马最后猜想、哥德巴赫猜想和“四色”猜想。 它描述对一张地图着色的问题，在一维直线上用两种颜色可以区分任意多不同线段，在二维平面内至少需要四种颜色可以区分任意多区域（当然最简单的情况是二色，如国际象棋棋盘）；在三维空间内至少需要八种颜色可以区分任意多的立体，（最简单的情况还是二色，如NaCl） * * a b c f e d h g b f e d §8.2 树 a b c f e d h g b f d g §8.2 树 b c e d a b c f e d h g §8.2 树 a b c h a b c f e d h g §8.2 树 a f d g a b c f e d h g §8.2 树 求树的方法：破圈法和避圈法 破圈法 §8.2 树 部分树 §8.2 树 避圈法 v1 v2 v3 v4 v5 v6 v1 v3 v1 v3 v2 v1 v3 v2 v5 v6 v1 v3 v2 v5 v6 v4 v1 v3 v2 v5 §8.2 树 8.2.3 最小支撑树问题 赋权图中求最小树的方法：1.避圈法 2.破圈法 设有一个连通图G=(V,E)，每一边e= [vi,vj] ，有一个非负权 w(e)=wij (wij ≥0) 如果T=(V,E′)是G的一个支撑树，称E′中所有边的权之和为支撑树T 的权，记为w(T)。即 如果支撑树T* 的权w(T*)是G的所有支撑树的权中最小者，则称T*是G的最小支撑树(简称最小树)。即 §8.2 树 避圈法（kruskal）由Joseph Kruskal在1956年发表。 用来解决同样问题的还有Prim算法和Boruvka算法等。 三种算法都是贪婪算法（贪心算法）的应用。 §8.2 树 克鲁斯克尔(Kruskal):1928年生，一家3弟兄都是数学家，1954年在普林斯顿大学获博士学位，导师是Erd?s,他大部