8.1 图的-基本概念.pptVIP

;运 筹 学( Operations Research );Chapter8 图与网络优化 ;§8.1 图的基本概念; 长;;欧拉（1707~1782）：根据几何位置的解题方法，1736年证明了不可能存在这样的路线。这是图论领域的第一篇论文，被尊称为图论和拓扑之父。 图论是组合数学的一个分支，它交叉运用了拓扑学、群论、数论等学科，有时将其归为离散数学的一个分支。 图论在物理、化学、工程技术、经营管理、电子计算机、控制论、信息论等领域都有广泛的应用。;例8.1 铁路交通图;(v1) 赵;例8.3 有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况：甲队和其他各队都比赛过一次，乙队和甲、丙队比赛过，丙队和甲、乙、丁队比赛过，丁队和甲、丙、戊队比赛过，戊队和甲、丁队比赛过。;两点之间不带箭头的连线称为边，带箭头的连线称为弧。;v3; 端点,关联边,相邻; 次，奇点，偶点，孤立点;图的基本性质：; 链，圈，初等链（圈），简单链（圈）;;如果任两个顶点之间至少存在一条链，称这样的图为连通图，否则称不连通图。;对图G1=(V1,E1)和G2=(V2,E2), ;v3;;回路：若路的第一个点和最后一个点相同，则该路为回路。; 出次与入次; 赋权图, 网络;网络：在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。;§8.2 树;树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。;例8.5 某企业的组织机构图也可用树图表示。; 树：无圈的连通图即为树;由上可以推得以下性质： 推论1 树连通，但去掉任一条边，必变为不连通。 推论2 树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。; 图的支撑树(或部分树);;;;;;求树的方法：破圈法和避圈法;;避圈法;8.2.3 最小支撑树问题;避圈法（kruskal）由Joseph Kruskal在1956年发表。 用来解决同样问题的还有Prim算法和Boruvka算法等。 三种算法都是贪婪算法（贪心算法）的应用。 ;1. 避圈法（kruskal） : 去掉G中所有边，得到n个孤立点；然后加边。 加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。;; ;5;;;;;;;;;;;;;;练习：应用避圈法求最小树;;;;;;;课堂练习：;3; 作业： P237 习题8.3 8.4（b） ;小结;The end,thank you!;后来，管校长因为那一个特殊的年份一个特殊的事件在美国发表了不恰当的言论，从云南回国时受到大学生的热烈欢迎，因此，他离开山东回了老家上海，到复旦大学任教。 大学开学典礼上，这个数学家管校长说，你们上大学，只要学会了两个能力就可以了，一个是学会学习。大家不要笑，你不要以为你已经会学习了，不一定。 中学时代，有老师跟着你教，不会的可以随时问，上了大学，不一样了。 大学老师上完课就回家了，你想问也找不到，更多的是靠你自我学习，你要不回自我学习自我教育，这四年大学上下来，可能也学不了多少东西。 学会学习表现在，你会利用图书馆，我们学校有上百万藏书，不会用太可惜了，你会利用图书馆了，就学会学习了。自我学习的能力，是一辈子的财富，离开学校走向社会，这种能力更会让你受益终生，希望你们能够学会、养成。 二是学会合作。21世纪以来，所有重大的发明发现，百分之八十以上是合作的产物，爱迪生一个人一千多项专利的时代过去了，如果你不能与人合作，不能与人很好地合作，你的一生是难有重大成就的。 过去这么多年了，我还时常记得，时常向人提起，管校长给我们的忠告。 用现在的话说，管校长讲的这两点，就是情商与智商吧。