资源描述
1图及其分类 p图图是点与线的集合。一个图由一些点及一些点之是点与线的集合。一个图由一些点及一些点之间的联线间的联线(不带箭头或带箭头不带箭头或带箭头)所所组成。组成。p为了区别起见。把两点之间的不带箭头的连线称为了区别起见。把两点之间的不带箭头的连线称为为边边，带箭头的连线称为，带箭头的连线称为弧弧。p用图来描述事物间的联系，不仅直观清晰，便于用图来描述事物间的联系，不仅直观清晰，便于统观全局，而且网络图的画法简便，不必拘泥于统观全局，而且网络图的画法简便，不必拘泥于比例和曲直。总之，这里所讲的图是反映对象之比例和曲直。总之，这里所讲的图是反映对象之间关系的一种工具。间关系的一种工具。2024/6/161图及其分类 图是点与线的集合。一个图由一些点及一些点之间的12无向图p由点和边组成的图称为由点和边组成的图称为无向图无向图。2024/6/162无向图由点和边组成的图称为无向图。2023/8/923无向图2024/6/163无向图2023/8/934环、多重边、简单图、多重图2024/6/164环、多重边、简单图、多重图2023/8/945点的次2024/6/165点的次2023/8/956链、圈、连通图2024/6/166链、圈、连通图2023/8/967子图2024/6/167子图2023/8/978子图v12024/6/168子图v12023/8/989有向图 p由点和弧组成的图称为由点和弧组成的图称为有向图有向图。2024/6/169有向图 由点和弧组成的图称为有向图。2023/8/9910环、多重弧、简单有向图 2024/6/1610环、多重弧、简单有向图 2023/8/91011点的出次和入次、路2024/6/1611点的出次和入次、路2023/8/91112网络的概念 2024/6/1612网络的概念 2023/8/91213图的矩阵表示：关联矩阵 2024/6/1613图的矩阵表示：关联矩阵 2023/8/91314图的矩阵表示：邻接矩阵 2024/6/1614图的矩阵表示：邻接矩阵 2023/8/91415图的矩阵表示：权矩阵 2024/6/1615图的矩阵表示：权矩阵 2023/8/91516树与最小树问题 2024/6/1616树与最小树问题 2023/8/91617树的概念和性质 v1v2v3v4v5v6432172024/6/1617树的概念和性质 v1v2v3v4v5v6432172021718树的概念和性质2024/6/1618树的概念和性质2023/8/91819支撑树 2024/6/1619支撑树 2023/8/91920用破圈法与避圈法求支撑树2024/6/1620用破圈法与避圈法求支撑树2023/8/92021最小树 破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。2024/6/1621最小树 破圈法：任取一圈，去掉圈中最长边，直到无圈。202122最小树 5v1v2v3v4v5v6843752618【例例8.1】用破圈法求下图的最小树。用破圈法求下图的最小树。最小树长为最小树长为 C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同度相同 2024/6/1622最小树 5v1v2v3v4v5v6843752618【例2223避圈法避圈法：取：取图G的的n个孤立点个孤立点v1，v2，vn作为一个支撑图，作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有从最短边开始往支撑图中添加，见圈回避，直到连通（有n1条边）条边）v1v2v3v4v5v643521在上图中，如果添加边在上图中，如果添加边v1,v2就形成圈就形成圈v1,v2,v4，这时就应，这时就应避开添加边避开添加边v1,v2，添加下一条最短边，添加下一条最短边v3,v6。破圈法和避圈法。破圈法和避圈法得到树的形状可能不一样，但最小树的长度相等得到树的形状可能不一样，但最小树的长度相等 5v1v3v515v2v4v684375268Min C(T)=152024/6/1623避圈法：取图G的n个孤立点v1，v2，vn作为2324最小树的寻找方法：矩阵法2024/6/1624最小树的寻找方法：矩阵法2023/8/92425矩阵法举例2024/6/1625矩阵法举例2023/8/92526矩阵法2024/6/1626矩阵法2023/8/92627矩阵法举例2024/6/1627矩阵法举例2023/8/92728矩阵法举例2024/6/1628矩阵法举例2023/8/92829最最短短路路问问题题在在实实际际中中具具有有广广泛泛的的应应用用，如如管管道道铺铺设设、线线路路选选择择等等问问题题，还还有有些些如如设设备备更更新新、投投资资等等问问题题也也可可以以归归结结为为求求最最短短路问题路问题 求最短路有两种算法：求最短路有两种算法：一一是是求求从从某某一一点点至至其其它它各各点点之之间间最最短短离离的的狄狄克克斯斯屈屈拉拉(Dijkstra)算法算法 另一种是针对网络中有负权的另一种是针对网络中有负权的逐次逼近法。逐次逼近法。最短路问题，就是从给定的网络图中找出一点到各点或任意两最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路点之间距离最短的一条路 最短路问题2024/6/1629最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等2930610123214675811165图图669【例例8.3】下图中的权下图中的权cij表示表示vi到到vj的距离（费用、时间），从的距离（费用、时间），从v1修一条公路或架设一条高压线到修一条公路或架设一条高压线到v7，如何选择一条路线使距离最，如何选择一条路线使距离最短，建立该问题的网络数学模型。短，建立该问题的网络数学模型。2024/6/1630 610123214675811165图63031【解解】设设xij为选择弧为选择弧(i，j)的状态变量，选择弧的状态变量，选择弧(i，j)时时xij1，不，不选择弧选择弧(i，j)时时xij0，得到最短路问题的网络模型：，得到最短路问题的网络模型：2024/6/1631【解】设xij为选择弧(i，j)的状态变量，选择弧(i3132Dijkstra标号法原理 2024/6/1632Dijkstra标号法原理 2023/8/93233Dijkstra标号法原理2024/6/1633Dijkstra标号法原理2023/8/93334Dijkstra算法的具体步骤 2024/6/1634Dijkstra算法的具体步骤 2023/8/93435Dijkstra算法的具体步骤2024/6/1635Dijkstra算法的具体步骤2023/8/935366101232146758111659(6,v1)(12,v1)(16,v3)(18,v3)(29,v5)【例例8.3】用用Dijkstra算法求下图所示算法求下图所示v1到到v7的最短路及最短路长的最短路及最短路长 v1 到到v7的最短路为：的最短路为：p17=v1,v2,v3,v5,v7，最短路长为，最短路长为L17=29 2024/6/1636 6101232146758111659(6,3637Dijkstra算法举例2024/6/1637Dijkstra算法举例2023/8/93738Dijkstra算法举例2371845661341052759346822024/6/1638Dijkstra算法举例23718456613410523839逐次逼近法 2024/6/1639逐次逼近法 2023/8/93940逐次逼近法2024/6/1640逐次逼近法2023/8/94041逐次逼近法举例2024/6/1641逐次逼近法举例2023/8/94142逐次逼近法举例2024/6/1642逐次逼近法举例2023/8/94243逐次逼近法举例2024/6/1643逐次逼近法举例2023/8/94344逐次逼近法举例2024/6/1644逐次逼近法举例2023/8/94445最短链问题 2024/6/1645最短链问题 2023/8/94546最短链问题2024/6/1646最短链问题2023/8/94647最短链问题举例2024/6/1647最短链问题举例2023/8/94748最短链问题举例2024/6/1648最短链问题举例2023/8/94849最短链问题举例2024/6/1649最短链问题举例2023/8/94950最短链问题举例2024/6/1650最短链问题举例2023/8/95051最短链问题举例2024/6/1651最短链问题举例2023/8/95152最短链问题举例2024/6/1652最短链问题举例2023/8/95253网络最大流问题 p所谓所谓最大流量问题最大流量问题就是：给一个带收发点的网络（一般收就是：给一个带收发点的网络（一般收点用点用vt表示，发点用表示，发点用vs表示，其余为中间点），其每条弧表示，其余为中间点），其每条弧的权值称之为容量，在不超过每条弧的容量的前提下，要的权值称之为容量，在不超过每条弧的容量的前提下，要求确定每条弧的流量，得出从发点到收点的最大流量。求确定每条弧的流量，得出从发点到收点的最大流量。p在交通运输、物资供应、通讯系统和财政金融等实际工作在交通运输、物资供应、通讯系统和财政金融等实际工作中，常会遇到这类最大流问题。中，常会遇到这类最大流问题。2024/6/1653网络最大流问题 所谓最大流量问题就是：给一个带收发点的网5354网络最大流问题2024/6/1654网络最大流问题2023/8/95455最大流有关概念2024/6/1655最大流有关概念2023/8/95556可行流与最大流 2024/6/1656可行流与最大流 2023/8/95657增广链的概念2024/6/1657增广链的概念2023/8/95758增广链的概念2024/6/1658增广链的概念2023/8/95859截集和截量2024/6/1659截集和截量2023/8/95960截集和截量2024/6/1660截集和截量2023/8/96061截集和截量2024/6/1661截集和截量2023/8/96162满足下例满足下例3个条件的流个条件的流fij 的集合的集合 f=fij 称为称为可行流可行流 发点点vs流出的流出的总流量等于流入收点流量等于流入收点vt的的总流量流量概念回顾2024/6/1662满足下例3个条件的流fij 的集合 f=fij 6263链：链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。从发点到收点的方向规定为链的方向。前向弧：前向弧：与链的方向相同的弧称为前向弧。与链的方向相同的弧称为前向弧。后向弧：后向弧：与链的方向相反的弧称为后向弧。与链的方向相反的弧称为后向弧。增广链增广链:设设 f 是一个可行流，如果存在一条从是一个可行流，如果存在一条从vs到到vt的链，满足：的链，满足：1.所有前向弧上所有前向弧上fij0则该链称为增广链则该链称为增广链前向弧前向弧后向弧后向弧容量容量流量流量这是一条增这是一条增广链广链84469（5）(2)(3)(4)(6)2024/6/1663链：从发点到收点的一条路线（弧的方向不一定都同向）称为链6364寻找网络最大流的Ford-Fulkerson标号法 2024/6/1664寻找网络最大流的Ford-Fulkerson标号法 206465算法的步骤 2024/6/1665算法的步骤 2023/8/96566算法的步骤2024/6/1666算法的步骤2023/8/96667算法举例2024/6/1667算法举例2023/8/96768算法举例2024/6/1668算法举例2023/8/96869算法举例2024/6/1669算法举例2023/8/96970算法举例2024/6/1670算法举例2023/8/97071算法举例2024/6/1671算法举例2023/8/97172算法举例2024/6/1672算法举例2023/8/97273算法举例2024/6/1673算法举例2023/8/97374(14，10)(8，6)(5，3)(6，6)(3，3)(8，7)(3，0)(6，6)(3，1)(10，3)(4，1)(7，7)【例例8.7】求下图发点求下图发点v1到收点到收点v7的最大流及最大流量的最大流及最大流量2024/6/1674(14，10)(8，6)(5，3)(7475无向图最大流标号算法无向图最大流标号算法无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端vi已已标号另一端标号另一端vj未标号的边只要满足未标号的边只要满足 Cijfij0 则则vj就可标号（就可标号（Cijfij）【例例8.8】求下图求下图v1到则到则v7标的最大流标的最大流(12,10)(9,6)(20,10)(8,8)(5,2)(8,3)(7,7)(6,6)(14,5)(13,13)(9,0)(16,13)0,v1,2v4,2v5,2v6,2v2,275无向图最大流标号算法无向图不存在后向弧，可以理解为所有弧7576(12,12)(9,6)(20,10)(8,8)(5,4)(8,3)(7,7)(6,6)(14,7)(13,13)(9,2)(16,15)0,v1,3v4,3v5,3v6,12024/6/1676(12,12)(9,6)(20,107677(12,12)(9,7)(20,10)(8,8)(5,4)(8,3)(7,7)(6,6)(14,8)(13,13)(9,3)(16,16)V=290,v1,10v3,5v4,5v5,5v4,177(12,12)(9,7)(20,107778最小费用网络最大流问题 2024/6/1678最小费用网络最大流问题 2023/8/97879最小费用最大流问题 2024/6/1679最小费用最大流问题 2023/8/97980最小费用增广链 2024/6/1680最小费用增广链 2023/8/98081求最小费用流的基本思想 2024/6/1681求最小费用流的基本思想 2023/8/98182辅助赋权有向网络的构造方法 2024/6/1682辅助赋权有向网络的构造方法 2023/8/98283最小费用最大流算法步骤2024/6/1683最小费用最大流算法步骤2023/8/98384最小费用最大流算法应用举例 2024/6/1684最小费用最大流算法应用举例 2023/8/98485最小费用最大流算法应用举例2024/6/1685最小费用最大流算法应用举例2023/8/98586最小费用最大流算法应用举例2024/6/1686最小费用最大流算法应用举例2023/8/98687最小费用最大流算法应用举例2024/6/1687最小费用最大流算法应用举例2023/8/98788最小费用最大流算法应用举例2024/6/1688最小费用最大流算法应用举例2023/8/98889最小费用最大流算法应用举例2024/6/1689最小费用最大流算法应用举例2023/8/98990最小费用最大流算法应用举例2024/6/1690最小费用最大流算法应用举例2023/8/99091欧拉图2024/6/1691欧拉图2023/8/99192欧拉链、欧拉圈与欧拉图p欧拉链欧拉链 给定一个连通多重图给定一个连通多重图G，若存在一条链，经过每边一次，若存在一条链，经过每边一次且仅一次，称这条链为欧拉链。且仅一次，称这条链为欧拉链。p欧拉圈欧拉圈 若存在一个简单圈，过每边一次，称这个圈为欧拉圈。若存在一个简单圈，过每边一次，称这个圈为欧拉圈。p欧拉图欧拉图 一个具有欧拉圈的图，称为欧拉图。一个具有欧拉圈的图，称为欧拉图。p上面提到的哥尼斯堡七桥问题就是要在图中寻找一个欧上面提到的哥尼斯堡七桥问题就是要在图中寻找一个欧拉圈。拉圈。2024/6/1692欧拉链、欧拉圈与欧拉图欧拉链2023/8/99293定理与推论定理与推论p定理定理1 连通多重图连通多重图G 是欧拉图的充要条件是图中的点全是欧拉图的充要条件是图中的点全为偶点。为偶点。p 定理定理2 连通多重图连通多重图G有欧拉链，当且仅当有欧拉链，当且仅当G中恰有两个中恰有两个奇点。奇点。p上述两个定理可用来识别一个图能否一笔画出。上述两个定理可用来识别一个图能否一笔画出。2024/6/1693定理与推论定理12023/8/99394中国邮递员问题 p中国邮递员问题由我国学者管梅谷在中国邮递员问题由我国学者管梅谷在1962年首先提出。年首先提出。p所谓中国邮递员问题，是指如下问题：某一邮递员负责某所谓中国邮递员问题，是指如下问题：某一邮递员负责某街区的邮件投递工作，每次都要从邮局出发走遍他负责的街区的邮件投递工作，每次都要从邮局出发走遍他负责的所有街道，再回到邮局，他应如何安排投递路线，使所走所有街道，再回到邮局，他应如何安排投递路线，使所走的总路程最短。的总路程最短。p中国邮递员问题的图论语言描述：给定一个连通图，在每中国邮递员问题的图论语言描述：给定一个连通图，在每边上边上ei上赋予一个非负的权上赋予一个非负的权w(ei),要求一个圈（未必是简单要求一个圈（未必是简单的），过每边至少一次，并使圈的总权最小。的），过每边至少一次，并使圈的总权最小。2024/6/1694中国邮递员问题 中国邮递员问题由我国学者管梅谷在19629495中国邮递员问题求解考虑两种情形：考虑两种情形：p如果如果G是欧拉图，则从邮局出发，每边恰好走一是欧拉图，则从邮局出发，每边恰好走一次可回到邮局，这时总权必定最小；次可回到邮局，这时总权必定最小；p如果如果G不是欧拉图，则某些边必然要重复走，我不是欧拉图，则某些边必然要重复走，我们当然要求重复走过的边的总长最小。我们可以们当然要求重复走过的边的总长最小。我们可以用用“奇偶点图上作业法奇偶点图上作业法”解决这一问题。解决这一问题。2024/6/1695中国邮递员问题求解考虑两种情形：2023/8/99596“奇偶点图上作业法”相关定理2024/6/1696“奇偶点图上作业法”相关定理2023/8/99697奇偶点图上作业法2024/6/1697奇偶点图上作业法2023/8/99798奇偶点图上作业法举例2024/6/1698奇偶点图上作业法举例2023/8/99899奇偶点图上作业法举例2024/6/1699奇偶点图上作业法举例2023/8/999100奇偶点图上作业法举例2024/6/16100奇偶点图上作业法举例2023/8/9100101奇偶点图上作业法举例2024/6/16101奇偶点图上作业法举例2023/8/9101102奇偶点图上作业法举例2024/6/16102奇偶点图上作业法举例2023/8/9102103【例例】求解下图的中国邮路问题求解下图的中国邮路问题 35v1v2v4v5v6v74752618v341奇偶点图上作业法举例2024/6/16103【例】求解下图的中国邮路问题 35v1v2v4v5v6103精品课件精品课件！精品课件！104精品课件精品课件！精品课件！1051065v1v2v4v5v6v743752618v34141【解解】最优解如下图最优解如下图14上图为最短欧拉回路，重复经过了上图为最短欧拉回路，重复经过了1，2和和6，7两条边两条边2024/6/161065v1v2v4v5v6v743752618v34141106
展开阅读全文