运筹学-图论.pptx

《运筹学》任课教师：饶卫振邮 箱：mailto:raoweizhen@163.comraoweizhen@163.com手 机Q：8316203011 图与网络优化引言--图论的起源哥尼斯堡七桥问题11 图与网络优化引言--图论的起源莱昂哈德·欧拉（Leonhard Euler ，1707年4月15日～1783年9月18日），瑞士数学家、自然科学家。1707年4月15日出生于瑞士的巴塞尔，1783年9月18日于俄国圣彼得堡去世。欧拉出生于牧师家庭，自幼受父亲的影响。13岁时入读巴塞尔大学，15岁大学毕业，16岁获得硕士学位。欧拉是18世纪数学界最杰出的人物之一，他不但为数学界作出贡献，更把整个数学推至物理的领域11 图与网络优化引言--图论的起源欧拉的解决思路AACCDDBB11 图与网络优化引言--图论的起源一笔画问题：任意1个能够1笔画出的点线图，所具有的特征：如果单线图，每个点连接的边数为偶数（欧拉圈），或者仅有两个点连接的边为奇数（欧拉链），那么这个图可以1笔画出。11 图与网络优化引言--图论的起源欧拉解决哥尼斯堡七桥问题结论由于该图既不是欧拉圈，也不是欧拉链，因此不能1笔画出。即哥尼斯堡7桥问题无解。ACDB11 图与网络优化11.1 图的基本概念在实际生活中，点线图可以表示非常多的对象，如实际的交通网络、电力光缆网络、管道网络等，虚拟网络如人际关系网络、信息传播网络等。概念（1）有向图、无向图；（2）点、弧、边；（3）关联边、次；（4）端点、相邻点、环、多重边、简单图、多重图；（5）奇点、偶点、悬挂点、孤立点。定理：任何1个图中奇点的个数必定为偶数个。初等链（圈）、简单链（圈）的概念，例P297图11-9.连通图和不连通图，支撑子图11 图与网络优化11.2 树的基本概念一个没有圈的连通图为树；包含n个节点的树，一定包括n-1条边11 图与网络优化11.3 最小支撑树及求解方法任何1个连通加权图，均可能有1个或多个支撑子图为树，其中权重和最小的为最小支撑数，如下图去掉任何1条边，均为该图支撑数，其最小支撑数权重和为9.543432211 图与网络优化11.3 最小支撑树及求解方法破圈法步骤概述：找到加权连通图中任何1个圈，去掉权重最大的边，不断找到当前图中的圈，重复该步骤，直到图中没有圈为止小支撑树的总权重为：3+2+2+2+1=10练习题：P326-图11-3911 图与网络优化11.3 最小支撑树及求解方法避圈法以P325-11.5为例TM城市PeTPaMNLPe×T13×Pa5160×M777057×L505925534×Pe1320502L34PaN最小支撑树的总权重为：2+13+20+34+50=11911 图与网络优化11.4 最短路问题Dijkstra算法运筹学附件资料/饶卫振-教学课件.ppt求解最短路问题的运筹学附件资料/饶卫振-教学课件.pptDijkstra运筹学附件资料/饶卫振-教学课件.ppt算法运筹学附件资料/饶卫振-教学课件.pptppt运筹学附件资料/饶卫振-微课视频.avi求解最短路问题的运筹学附件资料/饶卫振-微课视频.aviDijkstra运筹学附件资料/饶卫振-微课视频.avi算法视频L11 图与网络优化11.4 最短路问题Bellman算法v1v2v3v4v5v6v7v8v10-1-23v2602v3-30-5v4802v5-10v61017v7-10v8-3-50v5v2-126-3-31-1v3v6v87v1-218-5-5132v7v4-111 图与网络优化11.4 最短路问题Bellman算法t=3t=400-5-5-2-2-7-7-3-3-1-1-5-566v1v2v3v4v5v6v7v8t=1t=2v10-1-23v2602v3-30-5v4802v5-10v61017v7-10v8-3-5000-1-5-2-2-731-1511 图与网络优化11.4 最短路问题Bellman算法t=3t=400-5-5-2-2-7-7-3-3-1-1-5-566v1v2v3v4v5v6v7v8t=1t=2v10-1-23v2602v3-30-51v4802v5-10v61017v7-10v8-3-5000-1-5-2-2-731-1511 图与网络优化11.4 最短路问题Bellman算法负回路：如果D为有向图，C是D中的一个回路，且W(C)小于零，那么C是D中的一个负回路。如果D中不含负回路，那么图中任意两点间的最短中间点数量至多为n-2个，即至多迭代n-1次就能求解到某点至其他所有节点的最短路。如果一个有向图D，采用Bellman算法，迭代次数超过t=n-1，仍然不收敛，那么D中存