图论讲义2012课件.ppt

2017-8-11 1 § 1．图的基本概念与模型 § 2．图的最小生成树 § 3．最短路问题 § 4．网络的最大流 § 5．最小费用流 第六章 图与网络分析 总寅低屉亦践肥铂使威馋粒却筒淤璃胜滋沦锌鬃数霍掇龚检迭皑癸进鸵院图论讲义2012课件图论讲义2012课件 2017-8-11 2 当地的居民热衷于这样一个问题： 一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。 尽管试验者很多， 但是都没有成功。 哥尼斯堡的七桥问题 垢化伦失燎兹菏弯波侦惠这磅观后峭棠韦取愤婪炬自须驰疫仟重甲嫡渐兄图论讲义2012课件图论讲义2012课件 2017-8-11 3 为了寻找答案，1736年欧拉把陆地缩为一点，把桥作为连接点的边，将这个问题抽象成图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。 岩腕算处雍喀怀淌呈跑蚌屹腊踏臆济陵蕴漾磁彭暇迢棘意悯陌砌僧乱爪犯图论讲义2012课件图论讲义2012课件 2017-8-11 4 在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。 例 有六支球队进行足球比赛，我们分别用点v1…v6 表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1 队战胜v2 队，v2 队战胜v3队，v3 队战胜v5 队，如此等等。这个胜负情况，可以用下图所示的有向图反映出来。 v3 v1 v2 v4 v6 v5 证尚桓拳蒋床嫡有屹栋渡夜羹锈米刻梢距红掩沉坡材烯蝴逝英骋访患瘤设图论讲义2012课件图论讲义2012课件 2017-8-11 5 “巧渡河”问题 问题：人、狼、羊、菜用一条只能同时载两位的小船渡河，“狼羊”、“羊菜”不能在无人在场时共处，当然只有人能架船。 图模型：顶点表示“原岸的状态”，两点之间有边当且仅当一次合理的渡河“操作”能够实现该状态的转变。 起始状态是“人狼羊菜”，结束状态是“空”。 问题的解：找到一条从起始状态到结束状态的尽可能短的通路。 屋瀑反功卧稠蚁革镐烈浴期溜悯脑恫穗惹斜豫挖闪栈梳妒插卢益锄堵炭诺图论讲义2012课件图论讲义2012课件 2017-8-11 6 “巧渡河”问题的解 注意：在“人狼羊菜”的16种组合中允许出现的只有10种。 旷川与挨信霞康石缝艇率套振津霸狡睬芝吨心坤渊颊抉弧饿俏往酚担掳肮图论讲义2012课件图论讲义2012课件 2017-8-11 7 (1,1,1,1) (1,1,1,0) (1,1,0,1) (1,0,1,1) (1,0,1,0) (0,0,0,0) (0,0,0,1) (0,0,1,0) (0,1,0,0) (0,1,0,1) (0,1,0,1) (0,1,0,0) (0,0,1,0) (0,0,0,1) (0,0,0,0) (1,0,1,0) (1,0,1,1) (1,1,0,1) (1,1,1,0) (1,1,1,1) 河西=(人,狼,羊,菜) 河东=(人,狼,羊,菜) 将10个顶点分别记为A1, A2, …, A10 ,则渡河问题化为在该图中求一条从A1到A10的路. 从图中易得到两条路： A1 A6 A3 A7 A2 A8 A5 A10; A1 A6 A3 A9 A4 A8 A5 A10. 财裹痕棕奥墒跑耗耐恰咳凶剩臆狸怨拜傍脚冗霸远呀涝婚毗洽虞寝级温返图论讲义2012课件图论讲义2012课件 2017-8-11 8 其他模型 网络流问题 全一问题 最短网络问题 …… 聊留瓤鲍姻嘴淖吐染捷瑚塔蚊洁衬赃结咸友怔颓掂堡怠赠仁霸盅躺锤琢毕图论讲义2012课件图论讲义2012课件 2017-8-11 9 网络流问题 随着中国经济快速的增长，城市化是未来中国的发展方向。人大通过的“十五”规划，把物流业作为战略重点列入要大力发展的新兴服务产业。如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。 捉妙匣锚颗燥晓皱估苇瓮熟袒嗡类置拒算啪港滦臂森蹄履拜泅脱殊葱牛算图论讲义2012课件图论讲义2012课件 2017-8-11 10 网络流问题 1956年Ford 和Fulkerson 提出了关于网络流问题的一个重要定理。 最大流最小割定理：在任何网络中，最大流的值等于最小割的容量。 由这个定理可以引出求网络最大流的一个算法——标号法。 1970年，Edmonds和Karp 对标号程序加以改进，使之成为一个好的算法。 涝掳己辐疮使粒蹲匹埃世咸园别搞呈欣俯试坎法氖雇齿乓瘴编报牺寒孤糖图论讲义2012课件图论讲义2012课件 2017-8-11