运输配送图与网络分析课件.ppt

图与网络分析F问题提出问题提出â应用：生产组织，邮递员问题，通讯网络等â哥尼斯堡七桥问题ABCDF哥尼斯堡七桥问题哥尼斯堡七桥问题â在图中找一条经过每边一次且仅一次的路——欧拉回路ADBC由点和边组成F“环球旅行环球旅行”问题问题<在图中找一条经过每个点一次且仅一次的路——哈密尔顿回路F“中国邮路问题中国邮路问题”<在图中找一条经过每边的最短路——类似带权的欧拉回路F“货郎担问题货郎担问题”<在图中找一条经过每个点一次且仅一次的最短路——带权的哈密尔顿回路 在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图  例1:图1是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线一、图与网络的基本知识一、图与网络的基本知识太原重庆武汉南京徐州连云港上海郑州石家庄塘沽青岛济南天津北京图1运输配送图与网络分析 例2:有六支球队进行足球比赛，我们分别用点v1…v6表示这六支球队它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。

这个胜负情况，可以用图2所示的有向图反映出来v3v1v2v4v6v5图图2 2一、图与网络的基本知识一、图与网络的基本知识运输配送图与网络分析1.图的基本概念 例例 1: 铁路交通图铁路交通图 例例 2: 球队比赛图球队比赛图F点点: 表示研究对象表示研究对象.F连线：表示两个对象之间的某种特定关连线：表示两个对象之间的某种特定关系F关系的对称性：两对象之间的关系可互关系的对称性：两对象之间的关系可互换 F边：不带箭头的联线，表示对称关系边：不带箭头的联线，表示对称关系F弧：带箭头的联线，表示不对称关系弧：带箭头的联线，表示不对称关系F无向图：简称图，由点和边组成无向图：简称图，由点和边组成 表示为：表示为： G=（（V，，E）） V--点集合点集合 E--边集合边集合â例：右图V={v1，v2，v3，v4} E={e1，e2，…,e7}e1=[v1,v2]e2=[v1,v2], …,e7=[v4,v4] F 有向图：由点和弧组成表示为：有向图：由点和弧组成表示为： D=（（V，，A）） V--点集合点集合 A--弧集合弧集合F点数点数: p(G) 或或 p(D)F边数边数: q(G)F弧数弧数:q(D)v1v2v3v4v5例：右图V={v1，v2,…,v5}A={a1，a2,…,a7}a1={v1,v5},a2={v5,v4},…,a7={v1,v4}无向图的有关概念F端点端点: : e=[u,v]∈E, e=[u,v]∈E, 则则u,vu,v是是e e的端点的端点, , 称称u,vu,v相邻相邻. .F关联边关联边: e: e是点是点u,vu,v的关联边的关联边. .F环环: : 若若u=v, eu=v, e是环是环. .F多重边多重边: : 两点之间多于一条边两点之间多于一条边. .F简单图简单图: : 无环无环, ,无多重边的图无多重边的图. .F多重图多重图: : 无环无环, ,允许有多重边的图允许有多重边的图. . F次次: : 以点以点v v为端点的边的个数称为为端点的边的个数称为v v的次的次. . 表示为表示为: d(v): d(v)F悬挂点悬挂点: : 次为次为1 1的点的点. .F悬挂边悬挂边: : 悬挂点的关联边悬挂点的关联边. .F孤立点孤立点: : 次为次为0 0的点的点. .F奇点奇点: : 次为奇数的点次为奇数的点. .F偶点偶点: : 次为偶数的点次为偶数的点. .孤立点悬挂边F定理定理1: 图图G=(V,E)中中,所有点的次之和是所有点的次之和是边数的两倍边数的两倍, 即即:F定理定理2: 任意一图中任意一图中, 奇点的个数为偶数奇点的个数为偶数. 证明证明: :设设 V1-- V1--奇点的集合奇点的集合, , V2-- V2--偶点的集合偶点的集合偶数偶数偶数一、树及其性质一、树及其性质在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树树。

树在自然科学和社会科学,特别是在计算机科学领域中有广泛的应用例：已知有六个城市，它们之间要架设线，要求任意两个城市均可以互相通话，并且线的总长度最短第二节第二节 树树v6v3v4v2v5v1六个城市的一个网就作成一个图这个图必须是连通图这个图必须是无圈的图是一个不含圈的连通图，代表了一个线网v6v3v4v2v5v1运输配送图与网络分析再再比比如如，，乒乒乓乓球球单单打打比比赛赛抽抽签签后后的的对对阵阵形形式式以以及及企企业业的的组织结构图等组织结构图等A B C D E F G H总经理市场总监常务副总经理学术总监市场总学术总教质部研发部人事部第二节第二节 树树运输配送图与网络分析 二、图的生成（支撑）树定义15 设图K=(V,E’)是图G=(V,E)的一生成（支撑）子图,如果图K=(V,E’)是一个树,那么称K是G的一个生成树G中属于生成树的边称为树枝，不在生成树上的边称为弦例如,图3b 是图3a 的一个生成树 图3v6v5v2v3v4v1av6v5v2v3v4v1b显然，如果图K=( V, E’ )是图G=(V, E)的一个生成树，那么K 的边数是n(G)-1，G中不属于生成树K的边数是m(G)-n(G)+1。

第二节第二节 树树运输配送图与网络分析图的生成树的求法图的生成树的求法1 1：：定理7充分性的证明，提供了一个寻找连通图生成树的方法,叫做““破圈法破圈法””就是从图中任取一个圈，去掉一条边再对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个生成树例:用破圈法求下图的一个生成树V5V4V2V3V1e6e5e4e3e2e1e7e8第二节第二节 树树运输配送图与网络分析圈(v1,v2,v3,v1)去e3 ；圈( v1,v2,v4,v3,v1 )去e4 ；圈( v3,v4 v5,v3 )去e6 ；圈( v1,v2,v5,v4,v3,v1 )去e7； 得到生成树，如图所示v2e1e2e5e8v1v3v4图8-12V5V4V2V3V1e6e5e4e3e2e1e7e8第二节第二节 树树运输配送图与网络分析三、最小生成树问题三、最小生成树问题定义16 连通图G =（V，E），每条边上有非负权L(e)一棵生成树所有树枝上权的总和，称为这个生成树的权生成树的权具有最小权的生成树称为最小生成树最小生成树（最小支撑树），简称最小树这里所指的权，是具有广义的数量值。

根据实际研究问题的不同，可以具有不同的含义例如长度、费用、流量等等如前所述，在已知的几个城市之间联结线网，要求总长度最短或总建设费用最少，这个问题的解决可以归结为最小支撑树问题再如，城市间交通线的建造等，都可以归结为这一类问题第二节第二节 树树运输配送图与网络分析求最小生成树的常用方法有破圈法破圈法：① 在网络图中寻找一个圈若不存在圈，则已经得到最短树或网络不存在最短树；② 去掉该圈中权数最大的边； 反复重复 ① ② 两步，直到得到最小生成树例5 某六个城市之间的道路网如图4a所示，要求沿着已知长度的道路联结六个城市的线网，使得线的总长度最短v6v5v2v3v4图4av1627535441第二节第二节 树树运输配送图与网络分析 解：这个问题就是求赋权图的最小支撑树用破圈法求解v3v2v1v4v6v553142图8.13bv6v5v2v3v4图8.13av1627535441第二节第二节 树树运输配送图与网络分析课堂练习第二节第二节 树树运输配送图与网络分析主页主页主页主页小岛小岛A小岛小岛B运输配送图与网络分析欧拉欧拉 （Leonhard Euler 公元1707-1783年） 运输配送图与网络分析判断下列图形能否一笔画判断下列图形能否一笔画图1图5图4图3图2不连通的图形不能一笔画不连通的图形不能一笔画 连通的图形连通的图形有可能有可能一笔画一笔画 运输配送图与网络分析观察下列图形，完成统计表观察下列图形，完成统计表 图7图5图1图8图6图4图3图2可以一笔画的图形 不能一笔画的图形 图形序号奇点个数偶点个数　　图形序号奇点个数偶点个数　　运输配送图与网络分析不连通的图形不能一笔画不连通的图形不能一笔画 连通的图连通的图形形有可能有可能一笔画一笔画 全都是偶点的连全都是偶点的连通图可以一笔画通图可以一笔画 奇点个数超过两个的连通图奇点个数超过两个的连通图形不能一笔画形不能一笔画 画时以任一点为起点，画时以任一点为起点，最后仍回到该点最后仍回到该点 画时以一个奇点为起点，画时以一个奇点为起点，另一个奇点为终点另一个奇点为终点有两个奇点的连有两个奇点的连通图可以一笔画通图可以一笔画 运输配送图与网络分析你能笔尖不离纸，一笔画出图中你能笔尖不离纸，一笔画出图中的每个图形吗？的每个图形吗？ 运输配送图与网络分析判断下列图形能否一笔画判断下列图形能否一笔画图5图4图3图2图6图1运输配送图与网络分析下图是一个公园的平面图，要使游人走遍每一条路不重复，出口和入口应设在哪儿？运输配送图与网络分析甲　邮局　　乙　甲乙两个邮递员去送信，两人以同样的速甲乙两个邮递员去送信，两人以同样的速度走遍所有的街道，甲从度走遍所有的街道，甲从A点出发，乙从点出发，乙从B点出发，最后都回到邮局（点出发，最后都回到邮局（C）。

如果）如果要选择最短的线路，谁先回到邮局？要选择最短的线路，谁先回到邮局？运输配送图与网络分析主页主页主页主页运输配送图与网络分析二、 奇偶点图上作业法奇偶点图上作业法（1）找出图G中的所有的奇顶点，把它们两两配成对，而每对奇点之间必有一条通路，把这条通路上的所有边作为重复边追加到图中去，这样得到的新连通图必无奇点2）如果边e=（u,v）上的重复边多于一条，则可从重复边中去掉偶数条，使得其重复边至多为一条，图中的顶点仍全部都是偶顶点3）检查图中的每一个圈，如果每一个圈的重复边的总长不大于该圈总长的一半，则已经求得最优方案如果存在一个圈，重复边的总长大于该圈总长的一半时，则将这个圈中的重复边去掉，再将该圈中原来没有重复边的各边加上重复边，其它各圈的边不变，返回步骤（2）运输配送图与网络分析判判定定标标准准1: 在最优邮递路线上，图中的每一条边至多有一条重复边 判判定定标标准准2 : 在最优邮递路线上，图中每一个圈的重复边总权小于或等于该圈总权的一半运输配送图与网络分析ABCDEGHIJKNML1111222211322122图图1运输配送图与网络分析求解步骤：求解步骤：1、性图中，添加弧（即双线条），使得到的新图、性图中，添加弧（即双线条），使得到的新图上没有奇点，如图上没有奇点，如图2所示。

所示注意：如果邮递员走遍所有的路段，则路线图上所有（注意：如果邮递员走遍所有的路段，则路线图上所有的点都必须变成偶点，每一个点至少有一进一出的点都必须变成偶点，每一个点至少有一进一出ABCDEGHIJKNML1111222211322122图图2运输配送图与网络分析2、调整添弧，使每个圈的添弧总长度不大于圈总长度、调整添弧，使每个圈的添弧总长度不大于圈总长度的一半ABCDEGHIJKNML1111222211322122图图3总长度为总长度为6，而添弧总长度，而添弧总长度为为5，所以去掉原来的添弧，所以去掉原来的添弧B-H,H-I和和C-I,在该圈未在该圈未添弧的路段添弧的路段B-C上添弧运输配送图与网络分析总长度为总长度为8，而添弧总长度，而添弧总长度为为5，所以去掉原来的添弧，所以去掉原来的添弧I-K,I-M,在该圈未添弧的在该圈未添弧的路段路段K-N,M-N上添弧ABCDEGHIJKNML1111222211322122图图4运输配送图与网络分析ABCDEGHIJKNML1111222211322122图图53、最优解：在图、最优解：在图5中，所有的圈的添弧部分的长度都不超过中，所有的圈的添弧部分的长度都不超过整圈长度的一半，所以它构成一个最优解。

整圈长度的一半，所以它构成一个最优解运输配送图与网络分析 设设L点为邮局，则可以一笔画出邮递员送信的最短路点为邮局，则可以一笔画出邮递员送信的最短路径如图径如图6所示ABCDEGHIJKNML1111222211322122图图6运输配送图与网络分析课堂作业：求解下图所示网络的中国邮路问题，图中数字为该边的长 v1v2v3v4v5v6v7v8v9243449556434运输配送图与网络分析。