第八章-图与网络模型应用运筹学.ppt

1、 第 6章 Network Analysis图与网络模型1 Introduction to Networks 基本概念2 Shortest Path Problems 最短路问题 3 Minimum spanning tree 最小生成树问题4 Maximum Flow Problems 最大流问题5 Minimum-Cost Flow Problems最小费用最大流问题1实例一 : Seervada Park P266 黙登公司 AOCB DTE72254 1134574图中线上数据表示道路的距离， O 表示入口，子母表示站点（控制点）三个问题： (1)从入口 O到最美景点 T 的最短路？

2、OT smallest total distance (2) 需要在所有站点安装电话线保证通信联系，需要在那些道路下铺设电话线，使总电话最少 ? A minimum total number of miles of telephone line installed; (3) 公园在每条道路上安排了电车，每条道路车辆的运能有一定限制，问如何安排道路上的车次，使从入口到景点 T 的运能最大？ How to route the various trips to maximize the number of trips that can be per day without violating the

3、 limits on any individual road.图 6-1二、 哥尼斯堡 七桥问题东普鲁士的哥尼斯堡城中，有一条普莱格尔河，河中有两个岛屿（奈佛夫岛），河上建有七座桥，将岛与两岸陆地相连（图 6-2）。当地居民喜欢散步，并提出这样一个问题：若从岸或岛上任一处陆地出发，能否通过每座桥正好一次而回到原地。图 6-2 aA BCD尽管试验者很多，但是都没有成功。为了寻找答案， 1736年欧拉将这个问题抽象成图 6-2b所示图形的 一笔画 问题。 CA BD欧拉在他的论文中证明了这是不可能的 :不存在从某个点出发，经过 每座桥一次且只能一次，最终回到原出发地的方案图 6-2b三、四色问题

4、四色问题的提出来自英国， 1852年，毕业于伦敦大学的格思里 (Francis Guthrie)来到一家科研单位搞地图着色工作时，发现了一种有趣的现象： “看来， 每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜色 。 ”这个结论能不能从数学上加以严格证明呢？他与在大学念书的弟弟决心试一试。兄弟二人为证明这一问题使用了一大叠稿纸，可研究工作没有任何进展。 1852年 10月 23日，他的弟弟拿这个问题请教他的老师、著名数学家德 摩尔根 (Augustus de Morgan)， 摩尔根也没有能找到解决这个问题的途径，于是写信向自己的好友、著名数学家哈密尔顿爵士 (Sir Will

5、iam Hamilton)请教。但直到 1865年哈密尔顿逝世为止，这个问题也没有得到解决。 1878年 6月 13日，英国当时著名的数学家凯利 (Arthur Cayley)正式向伦敦数学学会提出这个问题，之后，四色猜想开始成了世界数学界关注的问题。许多一流的数学家纷纷加入研究， 1879年，著名的律师兼数学家肯普 (Alfred Bray Kempe)提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此解决了。 11年后，即1890年，数学家赫伍德 (Percy John Heawood)以自己的精确计算指出肯普的证明是错误的，但该方法经补救后可用来证明五色定理。后来，越来

6、越多的数学家虽然对此绞尽脑汁，但一无所获。于是，人们开始认识到，这个貌似容易的题目，其实是一个可与费马 (Fermat)猜想相媲美的难题。进入 20世纪以后，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。美国数学家富兰克林 (Franklin)于 1922年证明了 25国以下的地图都可以用四色着色， 1926年 ， 结果推进到 27国 ， 1938年，推进到 31国 ， 1940年，推进到 35国， 1970年，推进到 40国，随后又推进到了 96国。后来，由于计算机性能的迅速提高，以及人机对话的出现，大大加快了四色猜想证明的进程。 1976年 6月， 美国数学家阿佩尔(Kenneth

7、 Appel)与哈肯 (Wolfgang Haken)经过整整 4年的紧张工作，在伊利诺斯大学的 两台不同计算机上 ，花费了 1200个小时，作了 100亿个判断，终于完成了四色定理的证明。四色猜想的计算机证明，轰动了世界。它不仅解决了一个历时 100多年的难题，而且有可能成为数学史上一系列新思维的起点。不过也有一些数学家并不满足于计算机取得的成就，他们仍在寻找着简捷明快的纯数学证明方法。 1995年，中国学者 李宏棋 给出了一个数学证明，收录于 中国科学技术文库 数理科学和化学卷。1 图与网络的基本概念图论中 图是由点和边构成 ，可以反映一些对象之间的关系。例如：在一个人群中，对相互认识这个

8、关系我们可以用图来表示，图 6-3就是一个表示这种关系的图。(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1 e3e4e5图 6-32图论中所考察的图不同于以往几何学与分析学中的图形，这里的图 只考虑点与点之间由线连接的关系 。至于画成直线还是曲线，画得长些还是短些，画在这儿还是那儿，都无关紧要。也就是说，点线位置可随意安排，线长不代表实际长度。1 图与网络的基本概念n 无向图 ： 由点和边构成的图，记作 G=（ V， E）。n 有向图 ： 由点和弧构成的图，记作 D=（ V， A）。5n Graph (Network ) G = (V, E) n Node se

9、t (Vertex set) V = v1, v2 , v3 , v4 , v5 顶点集n 弧集 Arc Set E =(v1, v2), (v1, v4 ), (v2, v3 ), (v2, v4 ), (v3, v4 ), (v3, v5 ), (v4, v5 ), (Edge set) (边集 )n 有向弧 Directed Arc 无向弧 (边 )Undirected Arc P54中文书中称赋权的图为网络v2 v3v1 v4v5v2 v3v1 v4v5图 6-4 图 6-5l 一条链 是 (A Path)某些点与 (连接这些点 )的边的交替序列。无重复顶点和重复边的链称为 初等链图 6-5 中 v1 v2 v3 v4 v5 为一条链，且为一条初等链，而 v1 v4 v2 v3 v4 v5 不是 初等链l 两个顶点相同的边称为 环， e22 为环l 两个顶点之间的边数 2时 ,叫 多重边。 v1 ， v2 之间有多重边l 有多重边的图称为 多重图 ，无环且无多重边的图称为 简单图 。这里，主要研究简单图l 圈 Cycle: 起点和终点相同的链称为圈。图 6-6中v1 v2 v4 v3 v1为一个圈简单圈： 如果一个圈中所含的边均不相同初等 圈： 除起点和终点外链中所含的点 均不相同的圈；v1v5v4v3v2e12e34e13 e24e22e13e45图 6-6