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