运筹学-图与网络分析新编.ppt

运筹学运筹学运筹学 Operations Research Operations Research 运筹学 Operations Research Chapter 6 work Modeling 最小(支撑)树问题 Minimal (Spanning)Tree Problem 最短路问题 Shortest Path Problem 最大流问题 Maximal Flow Problem 旅行售货员与中国邮路问题 Traveling Salesman and China Carrier Problem 图论是专门研究图的理论的一门数学分支,属于离散数学范畴,与运筹学有交叉,它有 200 多年历史,大体可划分为三个阶段: 第一阶段是从十八世纪中叶到十九世纪中叶,处于萌芽阶段,多数问题围绕游戏而产生,最有代表性的工作是所谓的 Euler 七桥问题,即一笔画问题。引言引言第二阶段从十九世纪中叶到二十世纪中叶,这时,图论问题大量出现,如 Hamilton 问题,地图染色的四色问题以及可平面性问题等,这时,也出现用图解决实际问题,如 Cayley 把树应用于化学领域, Kirchhoff 用树去研究电网络等. 第三阶段二十世纪中叶以后,由生产管理、军事、交通、运输、计算机网络等方面提出实际问题,以及大型计算机使大规模问题的求解成为可能,特别是以 Ford 和 Fulkerson 建立的网络流理论,与线性规划、动态规划等优化理论和方法相互渗透,促进了图论对实际问题的应用。哥尼斯堡(现名加里宁格勒)是欧洲一个城市, Pregei 河把该城分成两部分,河中有两个小岛,十八世纪时,河两边及小岛之间共有七座桥,当时人们提出这样的问题: 有没有办法从某处(如 A )出发,经过各桥一次且仅一次最后回到原地呢? 例:哥尼斯堡七桥问题例:哥尼斯堡七桥问题 AB C D 数学家 Euler 在1736 年巧妙地给出了这个问题的答案, 并因此奠定了图论的基础, Euler 把A、B、C、D 四块陆地分别收缩成四个顶点,把桥表示成连接对应顶点之间的边,问题转化为从任意一点出发,能不能经过各边一次且仅一次,最后返回该点。这就是著名的 Euler 问题。无向连通图 G为欧拉图的充要条件是 G中所有顶点的度数都是偶数。例:有7 个人围桌而坐,如果要求每次相邻的人都与以前完全不同,试问不同的就座方案共有多少种? 用顶点表示人,用边表示两者相邻,因为最初任何两个人都允许相邻,所以任何两点都可以有边相连。例:圆桌交友问题例:圆桌交友问题假定第一次就座方案是(1,2,3,4,5,6,7,1 ),那么第二次就座方案就不允许这些顶点之间继续相邻,只能从图中删去这些边。 12345 6 7 1 12 23 3 7 76 64 45 5