运筹学课件图与网络分析.ppt

第十章图与网络分析图与网络分析 Graph & Network AnalysisGraph & Network Analysis章节大纲• 图的基本概念 • 树与最小支撑树的应用 • 最短路问题 • 网络最大流问题 • 最小费用最大流问题1847年 物理学家克希荷夫发表了关于树的第一篇论文1857年 英国数学家凯莱利用树的概念研究有机化合物的分子结构 1878年雪尔佛斯脱首次使用“图”这个名词 1936年匈牙利数学家哥尼格发表了第一本图论专著《有限图与无限图的理论》20世纪50年代 图论形成了两个本质上不同的发展方向图论系统的理论研究1736年 数学家欧拉发表了关于图的第一篇论文图论的代数方向图论的最优化方向1736年 瑞士数学家 欧拉（E. Euler) 提出“七桥问题” 通过每座桥刚好一次又回到原地是否可以 一笔画？1859年 英国数学家 哈密尔顿(Hamiltonian)用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即 “环球旅行” —— 由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，从而引起广泛的注意和研究。

—— 发明“环球旅行”游戏用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈这个问题后来就被称为哈密顿问题1850年 英国人格思里提出了“四色猜想”1976年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿个判断，终于完成了四色定理的证明 任何一个平面图，都可以用四种颜色来染色，使得任何两个相邻的区域有不同的颜色—— 世界近代三大数学难题之一 格思里和其弟弟格里斯德·摩尔根的好友、著名数学家哈密尔顿爵士几百年来，许多数学家致力于这项研究：格思里弟弟的老师、著名数学家德·摩尔根英国最著名数学家凯利…………1878～1880年两年间，著名的律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了11年后，即1890年，数学家赫伍德以自己的精确计算指出肯普的证明是错误的不久，泰勒的证明也被人们否定了例 2 有A、B、C、D、E 五个球队举行比赛，已知A 队与其它各队都比赛过一次；B 队和A、C 队比赛过；C 队和A、B、D 队赛过； D 队和A、C、E 队比赛过；E 队和A、D 队比赛过。

那么：这种比赛关系就可以用图来表示ABCDE点：表示球队点与点之间的连线：表示两球队间比赛过例3 五个球队之间的比赛结果是：A队胜了B、D、E队； B队胜了C队； C队胜了A、D队； D队没有胜过；E队胜了D队； —— 用点与点之间带箭头的线描述“胜负关系”关系A队三胜一负B队一胜一负C队两胜一负D队三战三负E队一胜一负从图中可以看出各球队之间比赛情况：ABCDE那么，这种胜负关系该如何用图来描述呢？10.1 图的基本概念v定义 §一个图G是指一个二元组(V(G),E(G))，即 图是由点及点之间的联线所组成其中: 1）图中的点称为图的顶点(vertex)，记为：v2）图中的连线称为图的边(edge)，记为：e ＝［vi, vj]，vi、vj是边 e 的端点3）图中带箭头的连线称为图的弧(arc)，记为：a ＝(vi, vj)，vi、vj是弧 a 的端点—— 要研究某些对象间的二元关系时，就可以借助于图进行研究v分类 §无向图：点集V和边集E构成的图称为无向图 (undirected graph)，记为： G(V，E)—— 若这种二元关系是对称的，则可以用无向图进行研究 §有向图：点集V和弧集A构成的图称为有向图 (directed graph) ，记为：D(V，A)—— 若这种二元关系是非对称的，则可以用有向图进行研究 §有限图: 若一个图的顶点集和边集都是有限集，则 称为有限图.只有一个顶点的图称为平凡图，其他的所有图都称为 非平凡图.1 图反映对象之间关系的一种工具，与几何图形不同。

2 图中任何两条边只可能在顶点交叉，在别的地方是立体交叉，不是图的顶点 3 图的连线不用按比例画，线段不代表真正的长度，点和线的位置有任意性4 图的表示不唯一如：以下两个图都可以描述“七桥问题”图的特点：3 奇点：次为奇数的点4 偶点：次为偶数的点5 孤立点：次为零的点6 悬挂点：次为1的点1 端点：若e =[u，v] E，则称u，v 是 e 的端点 2 点的次：以点 v 为端点的边的个数称为点 v 的次，记为：d(v)在无向图G中，与顶点v关联的边的数目(环算两次),称为顶点v的度或次数，记为 d(v)或 dG(v).在有向图中，从顶点v引出的边的数目称为顶点v的出度，记为d+(v)，从顶点v引 入的边的数目称为v的入度，记为d -(v). 称d(v)= d+(v)+d -(v)为顶点v的度或次 数．点(vertex)的概念例1 G =(V, E)V＝｛v1, v2, v3, v4 , v5 , v6 , v7 ｝E＝｛e1, e2, e3, e4 , e5 , e6 , e7 , e8 ｝奇点：v2，v3偶点：v1，v4v1v2v3v4e1e2e3e4e5e6e7e8v5v6v7悬挂点：v5，v6孤立点：v7如：e1、e2 是多重边。

e8 是悬挂边 v1v2v3v4e1e2e3e4e5e6e7e8v5v6v7e7 是环图 G 或 D 中点的个数记为 p(G) 或 p(D) ，简记为 p图 G 或 D 中边的个数记为 q(G) 或 q(D)，简记为 q点的个数p＝7 边的个数q＝8定理推论 任何图中奇点的个数为偶数．3 初等链（圈）：若链（圈）中各点均不同，则称为初等链（圈） 如：{ v1, e1, v2, e3, v3 }4 简单链（圈） ：若链（圈）中各边均不同，则称为间单链（圈） 1 链：一个点、边的交替的连续序列｛vi1, ei1, vi2, ei2, …, vik, eik｝称为链，记为μ2 圈(cycle)：若链μ的 vi1＝vik，即起点＝终点，则称为圈链(chain)的概念v1v2v3v4e1e2e3e4e5e6e7e8v5v6v7{ v1, e1, v3, e4, v4 }μ：链初等链简单链不是链{ v1, e1, v2, e3, v3 , e6 , v1 }圈初等圈间单圈圈一定是链，链不一定是圈路PATHv路(path)：顶点和边均互不相同的一条途径 v若在有向图中的一个链μ中每条弧的方向一致 ，则称μ为路。

无向图中的路与链概念一致 v回路(circuit)：若路的第一个点与最后一个 点相同，则称为回路 v连通性: 点i和j点是连通的：G中存在一条（i，j）路 G是连通的：G中任意两点都是连通的—— 路一定是链，但链不一定是路例 在右边的无向图中：途径或链：迹或简单链：路或路径：圈或回路： v1v2v3v4e1e2e3e4e5e6μ＝{ v1, e1, v2, e3, v3 }链不是路μ＝{ v1, e2, v2, e3, v3 }链且是路μ＝{ v1, e2, v2, e1, v1 }链是回路—— 注意区别：环、圈、回路的概念在右边的有向图中：连通图(connected graph)：若图中任何两点间至少有一条链，则称为连通图 否则，为不连通图简单图(simple graph)：一个无环、无多重边的图称为间单图多重图(multiple graph)：一个无环，但有多重边的图称为多重图连通分图：非连通图的每个连通部分称为该图的连通分图基础图：去掉有向图中所有弧上的箭头，得到的图称为原有向图的基础图图G＝(V, E)为不连通图但G’＝(V’, E’)是G的连通分图 其中：V’＝{v1, v2, v3, v4}E’＝{e1, e2, e3, e4, e5, e6, e7}图G＝(V, E)是多重图v1v2v3v4e1e2e3e4e5e6e7e8v5v6v7连通图10.2 树（tree） 一、树的定义树：一个无圈的连通图称为树。

例：《红楼梦》中贾府人物之间的血统关系树贾演贾源贾代化贾代善贾放贾敷贾珍贾蓉贾赦贾政贾琏贾宝玉 贾环贾珠贾兰（宁国府）（荣国府）二、树的性质1 设图G＝(V, E)是一个树，点数P(G) ≥ 2，则 G 中至少有 两个悬挂点2 图G＝(V，E)是一个树G不含圈，且恰有p-1条边 （p是点数）3 图G＝(V，E)一个树 G 是连通图，且q(G)＝p(G)－1 （q是边数）4 图G＝(V，E)是树 任意两个顶点之间恰有一条链图的支撑树(spanning tree)1 支撑子图：设图G＝(V，E)，图G’＝(V’，E’)的V’＝V，E’  E，则称G’是G的一个支撑子图2 支 撑 树：设图T＝(V，E’)是图G＝(V，E)的支撑子图，如果T＝(V，E’)是一个树，则称 T 是 G 的一个支撑树如何寻找 “支撑树” 呢？—— 图G’＝(V’，E’)的点集与图G＝(V，E)的点集相同，V’＝V，但图G’＝(V’，E’)的边集仅是图G＝(V，E)的子集E’  E特点——边少、点不少1 最小树定义如果T＝(V，E’)是 G 的一个支撑树，称 T 中所有边的权之和为支撑树T的权，记为W（T），即：若支撑树T* 的权W（T*）是G的所有支撑树的权中最小者， 则称T* 是G 的最小支撑树（最小树）， 即：W（T*）＝ min W(T)最小树(minimum spanning tree)问题例8：1） 破圈法：在图G中任取一个圈，从圈中去掉权数最大的边，对余下 的图重复这个 步骤， 直到G中不含圈为止，即可得到 G 的一个最小树 。

2 求最小树的算法（minimum spanning tree algorithm）v2v14v3v4v53532 142且p＝5 q＝4 1）在圈 v1→v2→v3→v1中去掉［v1,v3］2）在圈 v2→v4→v3→v2中去掉［v2,v3］3）在圈 v2→v4→v5→v2中去掉［v2,v5］4）在圈 v3→v4→v5→v3中去掉［v3,v5］∵图中已经不含圈 ∴ 已经求出了最小树 W(T*)＝4＋2＋1＋2＝9 避圈法是一种选边的过程，其步骤如下：1. 从网络D中任选一点vi，找出与vi相关联的 权最小的边[vi，vj]，得第二个顶点vj；2. 把顶点集V分为互补的两部分V1, 1 ，其中用避圈法解v5v1v3v6v4v2v72 55233 57 5711•最小部分树如图上红线所示；最小权和为14思考：破圈法与必避圈法各自的思路是怎样做的呢 ？——见圈就破，去掉其中权最大的——加边取其中最小的例8 要在5个城市架设线，使城镇之间能够通话两镇直接连接，每两个城镇之间的架设线的造价如下图所示，各边上的数字为造价（ 单位：万元 ）。

问：应如何架线，可使总造价最小？v1v3v2v5v4v6v7252463112424解：v1v3v2v5v4v6v72524631124241 破圈法：2 避圈法：v1v3v2v5v4v6v7252463112424总造价：W(T*)＝2＋2＋1＋1＋2＋2＝10 （万元）本节重点及难点重点难点1 图的概念及性质4 树的概念及性质5 部分树及最小树 2 点的概念及性质3 链的概念及性质1 图的概念及性质4 部分树及最小树 2 点的概念及性质3 链的概念及性质10.3．最短路问题最短路问题是图论应用的基本问题，很多实际 问题，如线路的布设、运输安排、运输网络最小费用流等问题,都可通过建立最短路问题模型来求解.1) 求赋权图中从给定点到其余顶点的最短路.2) 求赋权图中任意两点间的最短路.例 如下图所示的单行线交通网，每个弧旁边的数字 表示这条。