系统工程课件-ch3图与网络分析

南京农业大学工学院陈青春制作,系统工程,第三章图与网络分析,2,主要内容,1图的基本概念,1图的基本概念,第三章图与网络分析,一、图、连通图、赋权图,二、一笔画问题,三、中国邮路问题,四、子图和树,2有向图,4最短路问题,3图的矩阵表示,3,1图的基本概念,一、图、连通图、赋权图,1图的基本概念,一、图、连通图、赋权图,二、一笔画问题,三、中国邮路问题,四、子图和树,4,1图的基本概念概述,兰德公司简介,概述,5,1图的基本概念一、图、连通图、赋权图1.图,图论中的图与几何图形的区别,一、图、连通图、赋权图,1.图,与以前在数学中学的几何图形不完全相同,哥尼斯堡七桥问题：,示意图,图论中的图,欧拉将此问题归结为一个“一笔画”问题，并证明了是不可能的，因为图中的每个点都与奇数条边相关联，不可能将这个图不重复地一笔画成，这是古典图论中一个著名问题。,6,1图的基本概念一、图、连通图、赋权图1.图,图的基本概念,图论中的图与几何图形的区别,几何图形：,强调几何要素（如长度、角度、面积、形状等）的准确性（如桥的准确位置、长度、岛的面积大小）,两个图在图论中完全相同,图论中的图：,不关注几何要素的准确性，强调点的数量及点之间关系的准确性（如有几个岛、岛之间是否有桥、岛与岸之间是否有桥以及有几座桥）,7,1图的基本概念一、图、连通图、赋权图1.图,图的基本概念（续）,图的基本概念,顶点：,定义3-1：,A,D,B,C,e2,e1,e4,e3,e5,e6,端点：,关联边：,相邻点：,相邻边：,环：,通常用点表示具体的或抽象的事物，而用边表示事物之间的某种联系。,8,1图的基本概念一、图、连通图、赋权图1.图,图的基本概念（续）,图的基本概念（续）,多重图：,多重边：,A,D,B,C,e2,e1,e4,e3,e5,e6,简单图：,图的阶：,顶点的度：,偶点：,奇点：,含有多重边的图称为多重图。,无环无多重边的图称为简单图。,图中顶点的个数称为图的阶。,以v为端点的边的条数称为点v的度，记作deg(v)或d(v),度为偶数的点称为偶点。,度为奇数的点称为奇点。,规定环计算两次,9,1图的基本概念一、图、连通图、赋权图1.图,2.连通图,图的基本概念（续）,悬挂点：,孤立点：,A,D,B,C,e2,e1,e4,e3,e5,e6,悬挂边：,度为1的点称为悬挂点。,与悬挂点关联的边称为悬挂边。,E,F,度为零的点称为孤立点。,所谓连通图，即图中任意两点都能通过一系列顺序相连边通达，这一系列顺序相连的边称为链。,10,1图的基本概念一、图、连通图、赋权图2.联通图,3.赋权图,2.连通图,定义3-3（链、圈）：,简单链：,所有边不重复的链（即各边互不重复）。,即各边顺序相连,以下概念也适用于圈,初等链：,所有点不重复的简单链（即点边均不重复）。,连通图：,若图中任意两点之间至少存在一条链，则图称为连通图，否则称为不连通图。,11,1图的基本概念一、图、连通图、赋权图3.赋权图,二、一笔画问题,3.赋权图,定义3-4（赋权图）：,在实际问题中，常常遇到每条边对应一个数量指标的情况。例如，若用边表示线路（电线、公路、铁路、管道等），则往往要考虑它们的长度，或相应的运输价格等，这时，我们需为图的各边给出相应的数量指标，并称之为“权”。,相对于非赋权图，赋权图在图论的理论和应用方面有着重要的地位，赋权图中的边不仅表示图中各点之间的关联关系，而且同时表示出了各点之间的数量关系，所以赋权图被广泛应用于各领域的最优化问题。,定义3-5（图的权）：,图中各条边权的和称为图的权，记作,12,1图的基本概念,二、一笔画问题,1图的基本概念,一、图、连通图、赋权图,二、一笔画问题,三、中国邮路问题,四、子图和树,13,欧拉不仅证明了哥尼斯堡问题是不可能一笔画回到原出发点的，而且还证明了哥尼斯堡问题甚至不是可一笔画的。为了了解欧拉的结论，我们给出下列定义及定理。,1图的基本概念二、一笔画问题,定义：欧拉链,定义（可一笔画的图）：,我们可以笔不离纸地连续画出该图，并且各边没有重复，即可以“一笔画”画出该图，我们称这种图为可一笔画的。,如果连通图有一条包括所有顶点，但各边只出现一次的路线，则称这个连通图为可一笔画的图。,v3,v4,v1,v2,v5,14,1图的基本概念二、一笔画问题,哈密尔顿图,定义3-7（欧拉链）：,经过且仅经过图中每条边一次的链称为欧拉链。,定义3-8（欧拉圈）：,经过且仅经过图中每条边一次的圈称为欧拉圈。,定理3-1（欧拉链的充要条件）：,连通图含有欧拉链的充分必要条件是图中奇点的个数为0或2。,定理3-2（欧拉链的充要条件）：,连通图含有欧拉圈的充分必要条件是图中不存在奇点。,定义3-8（欧拉图）：,含有欧拉圈的图称为欧拉图。,15,1图的基本概念二、一笔画问题,三、中国邮路问题,哈密尔顿图，非欧拉图（有奇点）,欧拉图，非哈密尔顿图（无奇点）,16,1图的基本概念,1图的基本概念,一、图、连通图、赋权图,二、一笔画问题,三、中国邮路问题,四、子图和树,三、中国邮路问题,17,1图的基本概念三、中国邮路问题1.问题描述,二、中国邮路问题,邮递员在投送报刊信件时，从邮局出发，一般每次都要走遍他所负责的全部街道，任务完成后返回邮局。那么邮递员应该选择一条什么样的路线才能以尽可能少的路程走完所有的街道呢？这个问题是我国著名运筹学家管梅谷教授于1962年首先提出的，并给出了它的解法，因此国际上称为中国邮路问题。,在一个赋权图上，求一个圈，该圈经过图中每条边至少一次，并使圈中各边权值的总和为最小。称经过每条边至少一次的圈为邮递员路线。中国邮路问题就是求最优的邮递员路线。,2.定理,1.问题描述,如何理解最优邮递员路线？,欧拉图：则以邮局为始终点的一个欧拉圈就是最优邮递员路线。非欧拉图：则邮路中的某些边必须重复，带有重复边且总权值最小的圈最优邮递员路线。能形成圈的重复边方案不止一个，这时的问题是重复哪些边最好。,18,1图的基本概念三、中国邮路问题2.定理,定理3-4,2.定理,因为每条边与两个端点相关联，所以计算顶点的度时，每条边均使用了两次，所以全部顶点度的和等于边数的两倍。,定理3-3（顶点度之和与边数的关系）：,说明：,19,1图的基本概念三、中国邮路问题2.定理,3中国邮路问题的求解思路,定理3-4（奇点个数奇偶性）：,证明：,对于任一个图G，奇点的个数必为偶数。（偶点个数更是偶数？）,（1）点集分解：,（2）由定理3-3：,偶数,偶数,（3）,由于奇点集合中所有奇点的度之和为偶数，所以奇点集合中所有奇点的个数必为偶数。,20,1图的基本概念三、中国邮路问题3中国邮路问题的求解思路,4中国邮路问题的求解方法,3.中国邮路问题的求解思路,两种情况：,（1）不存在奇点：,为欧拉图，以邮局为始终点的欧拉圈即为所求,（2）存在奇点：,为非欧拉图，为形成圈，必须须在某些边上重复一次或多次。此时，为了减少重复路线的长度，则需要考虑图中各边的权值。,消除奇点方法1,消除奇点方法2,消除奇点方法3,能消除奇点的方案很多，何为最佳？,求解思路：,在含有奇点的赋权连通图中，增加一些边，使得在新得到的图中不含奇点，并且使得增加边的权值总和最小。,21,1图的基本概念三、中国邮路问题4中国邮路问题的求解方法,（1）增加边的确定方法,4.中国邮路问题的求解方法奇偶点作业法,关键步骤：,（1）,如何增加边，使图不含奇点？,（2）,如何判断增加边的总权值最小？,22,1图的基本概念三、中国邮路问题4中国邮路问题的求解方法,（2）最小权值增加边的确定方法,（1）增加边的确定方法,23,1图的基本概念三、中国邮路问题4中国邮路问题的求解方法,圈条件图示,（2）最小权值增加边的确定方法,定理3-5（最小权值增加边的充要条件）,定理说明：,（i）显然成立,（ii）如果在图中某个圈上增加边的总权值超过该圈原总权值的一半，则去掉该圈的增加边，同时给该圈的其余边加上增加边。这样，图中仍不会出现奇点，但可使增加边的总权值减少到不超过该圈原总权值的一半。,24,1图的基本概念三、中国邮路问题4中国邮路问题的求解方法,5奇偶点图上作业法的步骤,圈条件图示说明：,w2,w1,25,1图的基本概念三、中国邮路问题5奇偶点图上作业法的步骤,例3-3,5奇偶点图上作业法的步骤：,（1）,找奇点，确定初始增加边。在每两个奇点间找一条链，在链经过的所有边上都增加一条边。,（2）,检验定理3-5的两个条件是否满足，若满足则停止求解过程，否则转入第3步。,（3）,调整增加边。,若某边不满足边条件：,则从该条边上去掉偶数条增加边，以保证图中顶点仍全部是偶点；,若某圈不满足圈条件：,则将这个圈上的增加边去掉，将该圈的其余边上增加边，并转回到第2步。,26,1图的基本概念三、中国邮路问题例33,四、子图和树,例3-3求图3-7（a）的最优邮递员路线。,（1）找奇点,v1,v6,v7,v8,v9,v2,v3,v4,v5,4,9,4,6,4,2,5,5,3,4,4,3,解：,初始增加边总权值：21,（2）检验,边条件,圈条件,不满足,（3）调整增加边,（4）再检验,点击，再选一个圈,不满足,点击，显示“不满足”,（5）再调整增加边,点击，显示新增加边，点击，删除旧增加边,调整后的增加边总权值：17，有所改善,（6）再检验,全部13个圈均满足全条件。最优路线总权值53+1568,6.讨论（1）难点（圈检验）（2）找最优路线,点击，显示奇点,点击，显示增加边,确定初始增加边,满足,先选择一个圈，点击,（点击）,27,1图的基本概念,1图的基本概念,一、图、连通图、赋权图,二、一笔画问题,三、中国邮路问题,四、子图和树,四、子图和树,28,1图的基本概念四、子图和树,子图图示,4.子图和树,1.子图,（1）定义3-9（子图）,当寻找一个图中的一部分符合某些条件时，即涉及到子图最简单的图为树，既连通，边数也最少,即子图的全部顶点和边都被原图包含,（2）两种重要的子图,（i）部分图,全部顶点，部分边,（ii）真子图,部分顶点，部分边,29,1图的基本概念四、子图和树,2.树,(a)图G,(b)图G一个部分图,(c)图G的一个真子图,30,1图的基本概念四、子图和树2.树,树的定义,2.树,例3-4,分析：,（1）必须是连通图,因要求任意两个城市之间均能互相通话,如含圈，则从圈上去掉一条边，仍连通,在6个城市v1，v2，v6之间架设电话线，要求任意两个城市之间均能互相通话，试说明对代表这个电话网的图有什么要求。,（2）必须不含圈,满足例3-4要求的图,31,1图的基本概念四、子图和树2.树,关于树的定理,（1）树的定义,定义3-10（树）,一个无圈的连通图称为树，记作T,（2）树的性质,性质1,树中任意两点之间，有且仅有一条链。,因为树是连通的，所以任意两点之间必存在链。,又，如果两点之间有两条不同的链，则必有圈，这与树的定义相矛盾。,性质2,若树中去掉任意一条边，则树成为不连通图。,由性质1,树中任一条边是连接该边两个端点的唯一的一条链，所以去掉这条边后，其两个端点不再连通，,由该性质,树中任一条边是连接该边两个端点的唯一的一条链，,该性质说明，在点集合相同的图中，树是边数最少的连通图。,32,1图的基本概念四、子图和树2.树,关于树的定理,关于树的定理,定理3-6（顶点数与边数的关系）,证明：,该性质说明，在点集合相同的图中，树是边数最少的连通图。,设树T的顶点数为P，则其边数为P-1。,使用归纳法证明。,（1）,设Pk时定理为真（即边数为k-1），证明Pk1时定理成立,33,1图的基本概念四、子图和树2.树,3图的部分树,Pk1，边数？,v1,v2,v3,v4,v5,v6,去掉一条边（边数？）,端点重合,Pk，边数？（由假设，k-1）,边数k-1+1k,34,1图的基本概念四、子图和树3图的部分树,（2）求连通图部分树的方法,3.图的部分树,例3-5,图中所示顶点v1，v2，v9代表9个城市，顶点之间的连线表示电话线架设的允许路线。要求任何两个城市之间都可以彼此通话（允许通过其它城市），并且电话线的根数最少，问满足要求的应是什么图？,（1）定义,部分树的用途很广，因为它是包含图的所有顶点，但边数最少的连通图。,分析：,35,1图的基本概念四、子图和树3图的部分树（2）求连通图部分树的方法,例3-6求部分树（避圈法）,（2）求连通图部分树的方法,（i）避圈法,先去掉图G的所有边，只留下点，然后每次任意放回一条边，但应使其与已经放回的边不构成圈（避圈），反复进行，直到进行不下去为止（即继续放回任何边，都将构成圈）。,（ii）破圈法,在图G中任取一个圈，去掉圈上任意一条边（破圈）。然后再取另一个圈，并破圈，直到图中没有圈为止。,36,1图的基本概念四、子图和树3图的部分树（2）求连通图部分树的方法,例3-6求部分树（破圈法）,例3-6,解：,用避圈法求图3-12的一个部分树。,（1）,按原图位置标出所有点,（2）,任意放一条边,（3）,依次放入其他边，注意避免形成圈,问题：,避圈法求得的图的部分树唯一？,37,1图的基本概念四、子图和树3图的部分树（2）求连通图部分树的方法,4.最小部分树,例3-7,解：,用破圈法求图3-12的一个部分树。,（1）,任意选一个圈,（2）,任意去一条边,（3）,依次选其他圈，并破圈，直至无圈可破,问题：,破圈法求得的图的部分树唯一？,有时只考虑边数最少还不够，还需要考虑总权值最小，这时应求最小部分树,38,1图的基本概念四、子图和树4最小部分树,(2)求赋权连通图的最小部分树的方法,4.最小部分树,（1）最小部分树的定义,定义3-12,对于赋权连通图G，其所有部分树中总权值最小的部分树，称为图G的最小部分树（或称最小树），记作T*，即,39,1图的基本概念四、子图和树4最小部分树(2)求赋权连通图的最小部分树的方法,2有向图,（2）求赋权连通图的最小部分树的方法,（i）避圈法,先去掉图G的所有边，只留下点，然后每次放回一条与已经放回的边不构成圈（避圈）的边，反复进行，直到进行不下去为止（即继续放回任何边，都将构成圈）。,（ii）破圈法,在图G中任取一个圈，去掉圈上权值最大的一条边（破圈）。然后再取另一个圈，并破圈，直到图中没有圈为止。,请参考教材例3-8,在一个赋权连通图中，可能存在权值相等且最小的若干部分树，所以最小部分树可能不是唯一的。,40,主要内容,2有向图,第三章图与网络分析,1图的基本概念,一、图、连通图、赋权图,二、一笔画问题,三、中国邮路问题,四、子图和树,2有向图,4最短路问题,3图的矩阵表示,41,2有向图有向图的定义、基础图,有向图的环、链、路,2有向图,在前面讨论的图及赋权图中，涉及到的边都是无方向性的，即u，v=v，u，这种图称为无向图及赋权无向图。但在图论的应用中，经常遇到的情况是，不仅需要画出描述问题的图，而且需要指出图中每一条边的方向。这是因为，在有些问题中，一对顶点之间的关系往往不是对称的。例如，城市道路系统中的单行道、直流电路等；另一方面，有些关系仅用无方向性的边是反映不出来的，例如，一项工程中各工序之间的先后关系、竞赛中的胜负关系等。,我们将点与点之间有方向的边称为弧，在图上用前头标明方向。,定义3-13,基础图,42,2有向图有向图的环、链、路,链、路图示,环,链,路,注意链与路的区别。对于一条链，其各弧的方向与链的方向不一定一致；而对于路，其各弧的方向与路的方向一定是一致的。,回路,始点与终点相同的路称为回路。,43,2有向图有向图的环、链、路,3图的矩阵表示,v1,v2,v3,v4,v5,a1,a2,a3,a4,a6,a7,a5,链？路？,链？路？,链、路图示,图的矩阵表示的用途（1）对于复杂的图，用矩阵描述简单；（2）将优化算法在计算机上实现时，必须将图用矩阵来表示（如前述中国邮路问题）。,44,主要内容,3图的矩阵表示,第三章图与网络分析,1图的基本概念,一、图、连通图、赋权图,二、一笔画问题,三、中国邮路问题,四、子图和树,2有向图,4最短路问题,3图的矩阵表示,45,3图的矩阵表示一、边矩阵,二、邻接矩阵,一、边矩阵（弧矩阵）,3图的矩阵表示,定义3-14（边矩阵、弧矩阵）,设矩阵的行数为图的边（弧）数，列数为2，每行对应于图的一条边（弧），每行的两个元素为边（弧）的端点编号（对于有向图，规定第一列元素为弧的始点编号，第二列元素为弧的终点编号），这样的矩阵称为图的边（弧）矩阵。,邻接矩阵：最基本矩阵表示，可表示顶点之间的连通关系。本章求含负权弧网络最短路时须使用,（弧矩阵）,46,3图的矩阵表示二、邻接矩阵,定义（续）,二、邻接矩阵,定义3-15（邻接矩阵）,行、列数均等于图的顶点数，且矩阵元素aij符合下列规定的矩阵称为图的邻接矩阵：,（1）对于有向图D：,（2）对于无向图G：,47,3图的矩阵表示二、邻接矩阵,邻接矩阵（例）,（3）对于赋权有向图D：,（4）对于赋权无向图G：,48,3图的矩阵表示二、邻接矩阵,三、关联矩阵,有向图D,关联矩阵，也称连接矩阵，用来表示顶点与边的连接关系。,邻接矩阵,49,3图的矩阵表示三、关联矩阵,关联矩阵（例）,三、关联矩阵,定义3-16（关联矩阵）,（1）对于有向图D：,（2）对于无向图G：,50,3图的矩阵表示三、关联矩阵,关联矩阵（无向图例）,有向图,有向图的关联矩阵,51,3图的矩阵表示三、关联矩阵,4最短路问题,无向图,v1,v2,v3,v4,e1,e2,e3,e4,e6,e5,无向图的关联矩阵,显然，图的边（弧）矩阵形式上最简单，但图的邻接矩阵和关联矩阵在连通性判断和某些优化计算中更具实用价值。一般情况下，一个图可由它的邻接矩阵和关联矩阵来完全决定。,52,主要内容,4最短路问题,第三章图与网络分析,1图的基本概念,一、图、连通图、赋权图,二、一笔画问题,三、中国邮路问题,四、子图和树,2有向图,4最短路问题,3图的矩阵表示,53,4最短路问题一、定义,定义,4最短路问题,一、最短路问题的定义,例3-13,从油田v1到炼油厂v8铺设管道，管道路线限定范围如图3所示，弧的权代表路线长度，求使铺设路线长度最短的方案。,分析：,显然，在所给路线范围之内，从油田到炼油厂的铺设方案不止一个，且铺设路线长度不同，问题的要求是求铺设路线长度最短的方案。,（对于某些经过变形，可化为多阶段决策问题的最短路问题，可用动态规划方法求解）,54,4最短路问题一、定义,二、最短路算法,定义3-17（最短路问题）,这种问题称为最短路问题。,应用举例：,55,4最短路问题二、最短路算法,标号介绍,二、最短路算法,两种情况：,1.所有弧权为正狄克斯特拉（Dijkstra）算法,Dijkstra算法又称标号法，由E.W.Dijkstra于1959年首先提出。目前公认，在所有弧的权值均为非负（即）的情况下，这个算法是寻求最短路的最好算法。这个算法不仅能给出从始点到终点的最短路，而且在求解过程中，实际还给出了从始点到图中任意一点的最短路。,2.存在负弧权情况（自学）,1.所有弧权为正狄克斯特拉（Dijkstra）算法,（1）Dijkstra算法概述,从v1开始，给每一个顶点一个有值标号，标号分为T标号和P标号两种。,56,其值表示从始点v1到vj的最短路的总权值，称为固定标号。,4最短路问题二、最短路算法标号介绍,算法依据图示,T标号T（vj）:,P标号P（vj）:,其值表示从始点v1到vj的最短路总权值的上界，称为临时标号。,算法开始时，T(v1)=0,其余T(vj)=+。,凡是得到P标号的顶点，说明已经求出v1到该点的最短路及最短路权值，其标号不再改变。,算法目标:,逐步求出始点v1到各T标号顶点的最短路，并将其改为P标号。当所有顶点均为P标号时，算法结束。,算法依据:,57,4最短路问题二、最短路算法算法依据图示,（2）Dijkstra算法的求解步骤,反证法:,说明:,58,4最短路问题二、最短路算法（2）Dijkstra算法的求解步骤,最小T标号改P标号的解释,（i）,（2）Dijkstra算法的求解步骤,（ii）,（iii）,即现在vi到vj的最短路总权值上限有两个，选小者，向最短路总权值逼近,如已无T标号，结束，否则转（ii）,59,4最短路问题二、最短路算法（2）Dijkstra算法的求解步骤,例3-14,为什么只能将最小T标号的顶点改为P标号？,至于与P标号顶点不直接相邻的其他顶点，其最短路更无法确定。而最小T标号顶点则一定与P标号顶点相邻（？）。,60,4最短路问题二、最短路算法例3-14,例3-14,求右图v1到v8之间的最短路,v6,v1,v2,v3,v4,v5,v7,v8,3,7,7,6,1,6,2,2,1,4,3,解,（1）,列Dijkstra算法求解表。,单击,（2）,填写第一行。,单击,例3-14（续）,表头内容为定点名称,61,T=3,4最短路问题二、最短路算法例3-14（续）,例3-14（续）,v6,v1,v2,v3,v4,v5,v7,v8,3,7,7,6,1,6,2,2,1,4,3,（3）,修改v2，v4的T标号,例3-14（续）,62,4最短路问题二、最短路算法例3-14（续）,例3-14（续）,v6,v1,v2,v3,v4,v5,v7,v8,3,7,7,6,1,6,2,2,1,4,3,（4）,将v2改P标号并标路径,例3-14（续）,T=3,分析：能否将v4标为P标号？,63,T=7,4最短路问题二、最短路算法例3-14（续）,例3-14（续）,v6,v1,v2,v3,v4,v5,v7,v8,3,7,7,6,1,6,2,2,1,4,3,（5）,例3-14（续）,修改v3，v5的T标号,64,4最短路问题二、最短路算法例3-14（续）,例3-14（续）,v6,v1,v2,v3,v4,v5,v7,v8,3,7,7,6,1,6,2,2,1,4,3,（6）,例3-14（续）,T=7,分析：此次为何能将v4标为P标号？,将v4改P标号并标路径,65,T=8,4最短路问题二、最短路算法例3-14（续）,例3-14（续）,v6,v1,v2,v3,v4,v5,v7,v8,3,7,7,6,1,6,2,2,1,4,3,（7）,例3-14（续）,修改v5，v7的T标号,66,4最短路问题二、最短路算法例3-14（续）,例3-14（续）,v6,v1,v2,v3,v4,v5,v7,v8,3,7,7,6,1,6,2,2,1,4,3,（8）,例3-14（续）,T=8,将v5改P标号并标路径,67,4最短路问题二、最短路算法例3-14（续）,T=10,例3-14（续）,v6,v1,v2,v3,v4,v5,v7,v8,3,7,7,6,1,6,2,2,1,4,3,（9）,例3-14（续）,修改v6的T标号,68,4最短路问题二、最短路算法例3-14（续）,例3-14（续）,v6,v1,v2,v3,v4,v5,v7,v8,3,7,7,6,1,6,2,2,1,4,3,（10）,例3-14（续）,T=10,将v3改P标号并标路径,69,T=11,4最短路问题二、最短路算法例3-14（续）