图论与网络分析课件

1、图论与网络分析 图论与网络分析图论与网络分析 （Graph Theory and Network Analysis）教学要求教学要求：了解了解图论的基本概念，理论和方法以及应用掌握掌握最小树以及最短路问题等模型及其基本算法。掌握掌握欧拉道路、回路的判断和构造方法图论与网络分析1818世纪，哥尼斯堡城中有一条普雷格尔河，河上有七座桥将河中的世纪，哥尼斯堡城中有一条普雷格尔河，河上有七座桥将河中的两个小岛与河岸连接起来。人们提出了这样的问题：一个散步者能否两个小岛与河岸连接起来。人们提出了这样的问题：一个散步者能否从某地出发，走遍七桥且每座桥恰好经过一次，最后回到原地？从某地出发，走遍七桥且每座桥

2、恰好经过一次，最后回到原地？ 陆地A陆地B岛D岛CAD B C 17361736年瑞士数学家欧拉将两岸和小岛抽象为四个点，年瑞士数学家欧拉将两岸和小岛抽象为四个点，将桥抽象为七条边，此问题归结为一笔画问题。将桥抽象为七条边，此问题归结为一笔画问题。图论起源图论起源图论与网络分析第一节第一节 图论的概念图论的概念图论的图与一般几何图形或函数图形是完全不同的图论的图与一般几何图形或函数图形是完全不同的n图论中的图图论中的图:由一些点和连接点的线所组成的由一些点和连接点的线所组成的“图形图形”n点和线的位置是任意的点和线的位置是任意的n线的曲直、长短与实际无关，代表的只是点与点之线的曲直、长短与实际

3、无关，代表的只是点与点之间的相互关系间的相互关系v1v2v3 v4v1v2v3 v4图论与网络分析34512无向图的基本概念无向图的基本概念 G=(V,E)V=viG的顶点集合的顶点集合E=ek G的边集合的边集合，且且ek=（vi,vj）为无序二元组）为无序二元组,表示表示ek连接连接vi,vjn(G)=|V|=nG的顶点数的顶点数m(G)=|E|=mG的边数的边数顶点相邻顶点相邻 两顶点之间有一条边，两顶点之间有一条边，顶点为该边的端点，边顶点为该边的端点，边与其端点关联。与其端点关联。边相邻边相邻e1e2e3e4e5e6e7 两边与同一顶点关联，两边与同一顶点关联，即两边有共同的端点。即

4、两边有共同的端点。环环两端点重合为一点的边，两端点重合为一点的边，如如e1多重边多重边两点之间多于一条边，如两点之间多于一条边，如e6，e7简单图简单图不含环和多重边的图，去不含环和多重边的图，去掉掉e1和和e7.（不特指（不特指都是简单图）都是简单图）完全图完全图每对顶点之间都有边相连每对顶点之间都有边相连的无向简单图，的无向简单图，n个顶点个顶点的无向完全图记为的无向完全图记为Kn次次与顶点与顶点v相关联的边数，即相关联的边数，即以以v为顶点的边数记为为顶点的边数记为d(v),环记环记2次。次。d(1)=4.奇点，偶点奇点，偶点次为奇数的点为奇点，次为次为奇数的点为奇点，次为偶数的点为偶点

5、。偶数的点为偶点。次为次为1的点为悬挂点。的点为悬挂点。若若4，5之间有一条边，则之间有一条边，则5为悬挂点。为悬挂点。孤立点孤立点次为次为0的点为孤立点，的点为孤立点，5为孤为孤立点。立点。Kn有边有边 条条2nC悬挂点悬挂点图论与网络分析无向图的基本概念无向图的基本概念 二部图：图G=(V,E)，顶点集合V可分为两个非空子集X,Y，知XY=V，XY=，E中每条边的两个端点，一个在X中，一个在Y中，则称G为二部图，记为G=（X,Y,E）v1v2v3 v4v2v4v3 v1图论与网络分析有向图的基本概念有向图的基本概念 G=(V,E)V=vi：G的顶点集合的顶点集合E=ek：G的有向边的有向边

6、(弧弧)集合集合，且且ek=（vi,vj）为有序二元组）为有序二元组,表示弧表示弧ek从从vi（始点）（始点）指向指向vj（终点）（终点）环环有向图中，始点、终点重有向图中，始点、终点重合的弧为环，如合的弧为环，如e1多重边多重边始点和终点都相同的弧为始点和终点都相同的弧为多重边，如多重边，如e6，e7非多非多重边。重边。简单有向图简单有向图不含环和多重边的有向图，不含环和多重边的有向图，去掉去掉e1有向完全图有向完全图以任意点为始点，另一点为以任意点为始点，另一点为终点都有一条弧的简单有终点都有一条弧的简单有向图，向图，n个顶点的有向完个顶点的有向完全图有弧全图有弧n(n-1)条条出次，入次

7、，次出次，入次，次34512e1e2e3e4e5e6e7以顶点以顶点v为始点的弧数为为始点的弧数为v的出次，记的出次，记为为 ；以顶点；以顶点v为终点的弧数为为终点的弧数为v的入次，记为的入次，记为 ；顶点；顶点v的出次的出次与入次之和为点与入次之和为点v的次。的次。( )dv( )dv图论与网络分析网络（赋权图）网络（赋权图）在无向图的边（或有向图的弧）上标上实数，在无向图的边（或有向图的弧）上标上实数，称为该边（或弧）的权，无向（有向）图连称为该边（或弧）的权，无向（有向）图连同它边上的权称为一个网络赋权图，简称网同它边上的权称为一个网络赋权图，简称网络。（无向网络，有向网络）络。（无向网

8、络，有向网络）图论与网络分析子图子图( ,),(,),GV EEE VVEVGV EGVVGG若且 中的边仅与中的顶点关联，称为 的一个子图。特别，若则为 的生成子图(支撑子图)34512e1e2e3e4e5e6e7412e2e3e4e53412e2e3e4e5图论与网络分析道路，回路道路，回路34512e1e2e3e4e5e6e711011200(,)(,)ktiiiiiikikitiitiikiikGve v evevevvvvvv图 中的一个点边交替序列（其中）为连接与 的一条链。该链中点不重，边不重为初等链；该链中与为同一点时为圈；圈中点边不重为初等圈；无向图链和圈也称为道路和回路。G

9、有向图 不考虑方向，同样定义链和圈，若链、圈上弧方向相同时，称为道路、回路。34512e1e2e3e4e5e6e7图论与网络分析连通图连通图p点点i和和j点是连通的：点是连通的：i,j之间存在一条链之间存在一条链pG是连通的：是连通的：G中任意两点都是连通的中任意两点都是连通的 p不连通图可以分为若干连通子图，每个称不连通图可以分为若干连通子图，每个称为原图的分图。为原图的分图。图论与网络分析关联矩阵关联矩阵图的矩阵表示图的矩阵表示图论与网络分析关联矩阵示例关联矩阵示例右图的关联矩阵是右图的关联矩阵是 右图的关联矩阵是右图的关联矩阵是 134521342 1101000010100100011

10、01010000110010000011154321 110001011001101000114321e1e2e4e7e6e5e8e3e1e2e3e4e5图论与网络分析邻接矩阵邻接矩阵图论与网络分析邻接矩阵示例右图的邻接矩阵是右图的邻接矩阵是 右图的邻接矩阵是右图的邻接矩阵是 134521342 01110101011101110101011105432154321 010000001100011043214321图论与网络分析主要结论主要结论1:( )22v VThd vEm2:Th图中奇点必为偶数个。3:( )( )v Vv VThdvdv图论与网络分析图论基本概念应用图论基本概念应用p例

11、例1：证明在：证明在9座工厂之间，不可能每座工厂只与其他座工厂之间，不可能每座工厂只与其他3座座工厂有业务联系，也不可能只有工厂有业务联系，也不可能只有4座工厂与偶数个工厂有座工厂与偶数个工厂有业务联系。业务联系。将将9座工厂看做座工厂看做9个点，他们有联系用边相连，若每座工厂个点，他们有联系用边相连，若每座工厂只与其他只与其他3座工厂有业务联系，则每个点的次都为座工厂有业务联系，则每个点的次都为3，从而，从而总次为总次为27，非偶数，与总次为边的，非偶数，与总次为边的2倍矛盾。从而得证。倍矛盾。从而得证。若只有若只有4座工厂与偶数个工厂有业务联系，则其余座工厂与偶数个工厂有业务联系，则其余5

12、座与奇座与奇数个工厂有业务联系，从而总次为数个工厂有业务联系，从而总次为 4*偶偶+5*奇奇=奇数奇数非偶数，矛盾。从而得证。非偶数，矛盾。从而得证。图论与网络分析例例2：6个人围成圆圈就座，每个人恰好只与相邻者不认识，个人围成圆圈就座，每个人恰好只与相邻者不认识，是否可以重新就座，使每个人都与邻座认识？是否可以重新就座，使每个人都与邻座认识？将将6个人看做个人看做6个点，相互认识用边表示个点，相互认识用边表示162345要求重排之后每个人与邻座认识要求重排之后每个人与邻座认识只需找到一个序列，该序列中前只需找到一个序列，该序列中前后两个点是相邻的就可以了。如后两个点是相邻的就可以了。如1-3

13、-5-2-6-4-1143526图论与网络分析例例3 甲、乙、丙、丁、戊甲、乙、丙、丁、戊5个运动员报名参加个运动员报名参加A,B,C,D,E，F六个项目比赛，报名情况见下表（打六个项目比赛，报名情况见下表（打*表示各运动员报名表示各运动员报名参加的比赛项目）。问如何安排项目，使每名运动员不连续参加的比赛项目）。问如何安排项目，使每名运动员不连续参加两项比赛？参加两项比赛？将将6个项目看做个项目看做6个点，同一个人参加的项目之间有边个点，同一个人参加的项目之间有边要求安排项目，每名运动员不连要求安排项目，每名运动员不连续参加两项比赛，只需找到一个续参加两项比赛，只需找到一个遍历点的序列，该序列

14、中前后两遍历点的序列，该序列中前后两个点是不相邻的就可以了。如个点是不相邻的就可以了。如A-C-D-E-F-BA AB BC CD DE EF F甲甲* * *乙乙* * * *丙丙* * *丁丁* * *戊戊* * *ABCDEF图论与网络分析练习练习 10个研究生参加个研究生参加6门课考试，每个研究生考试课程见门课考试，每个研究生考试课程见下表，要求上下午各排一门课，每人每天最多考一门，且下表，要求上下午各排一门课，每人每天最多考一门，且A必须第一天上午，必须第一天上午，F必须最后考，必须最后考，B要安排在下午考，试给要安排在下午考，试给出一个考试安排表。出一个考试安排表。A AB BC

15、CD DE EF F1 1* *2 2* *3 3*4 4* * *5*6*7*8*9*10*AECBDF图论与网络分析欧拉回路欧拉回路n连通图连通图G中若存在一条道路，经每边一次且仅一中若存在一条道路，经每边一次且仅一次，则该道路为欧拉道路次，则该道路为欧拉道路n若存在一条回路，经每边一次且仅一次，该回路若存在一条回路，经每边一次且仅一次，该回路为欧拉回路。为欧拉回路。n有欧拉回路的图称为欧拉图。有欧拉回路的图称为欧拉图。图论与网络分析结论：结论：pTh1：无向连通图无向连通图G为欧拉图充要条件是为欧拉图充要条件是G中无奇点。中无奇点。pTh2：无向连通图无向连通图G为欧拉图充要条件是为欧拉

16、图充要条件是G的边集可分为的边集可分为若干初等回路。若干初等回路。pTh3：无相连通图无相连通图G为欧拉道路充要条件是为欧拉道路充要条件是G中恰有中恰有2个个奇点。奇点。pTh4：连通有向图连通有向图G为欧拉图充要条件是他每个顶点的出为欧拉图充要条件是他每个顶点的出次等于入次。次等于入次。pTh5：连通有向图连通有向图G为欧拉道路充要条件是这个图中除了为欧拉道路充要条件是这个图中除了两个顶点之外，其余每个顶点出次等于入次，且这两顶点两个顶点之外，其余每个顶点出次等于入次，且这两顶点中，一个顶点入次比出次多中，一个顶点入次比出次多1，另一个出次比入次多，另一个出次比入次多1.图论与网络分析一个散

17、步者能否从某地出发，走遍七桥且每座桥恰好经一个散步者能否从某地出发，走遍七桥且每座桥恰好经过一次，最后回到原地？过一次，最后回到原地？ 即是否存在欧拉回路？即是否存在欧拉回路？陆地A陆地B岛D岛CAD B C每点都是奇点，所以不是欧拉图，即不存在欧拉回路。每点都是奇点，所以不是欧拉图，即不存在欧拉回路。如果存在欧拉回路，如何找到该回路？如果存在欧拉回路，如何找到该回路？图论与网络分析欧拉回路的构造方法欧拉回路的构造方法p从从G中任意点中任意点v1出发找到一个初等回路出发找到一个初等回路c1，再从，再从图中去掉图中去掉c1，在剩余的图中再找初等回路，在剩余的图中再找初等回路c2，一直找到图中所有

18、的边都被包含在这，一直找到图中所有的边都被包含在这些初等回路中为止，最后把这些回路连续起来即些初等回路中为止，最后把这些回路连续起来即得该图的欧拉回路。得该图的欧拉回路。图论与网络分析下面两个图是否可以一笔画出？下面两个图是否可以一笔画出？V3V1V2V6V5V412345678910(2，e23,3,e34,4,e41,1,e12,2,e27,7,e75,5,e56,6,e67,7,e79,9,e910,10,e108,8,e89,9,e93,3,e310,10,e104,4,e48,8,e86,6,e61,1,e15,5)图论与网络分析第二节第二节 最小树问题最小树问题1v 一、树的定义与

19、树的特征一、树的定义与树的特征定义定义 连通且不含圈的无向图称为连通且不含圈的无向图称为树树常用常用T表示表示. 树中的边称为树中的边称为树枝树枝. 树中次为树中次为1的顶点称为的顶点称为树叶树叶，次大于次大于1的点为的点为分枝点分枝点。2v3v4v5v图论与网络分析定理定理 设设T是具有是具有n个顶点的图，则下述命题等价：个顶点的图，则下述命题等价：1) T是树（是树（ T无圈且连通）；无圈且连通）；2) T无圈，且有无圈，且有n-1条边；条边；3) T连通，且有连通，且有n-1条边；条边；4) T无圈，但添加任一条新边恰好产生一个圈无圈，但添加任一条新边恰好产生一个圈; 5) T连通，且删

20、去一条边就不连通了连通，且删去一条边就不连通了6) T中任意两顶点间有唯一一条路中任意两顶点间有唯一一条路.图论与网络分析二、图的生成树二、图的生成树定义定义 若若T是包含图是包含图G的全部顶点的子图的全部顶点的子图,它又是树它又是树,则称则称T是是G的的生成树生成树. 图图G中不在生成树的边叫做中不在生成树的边叫做弦弦.定理定理 图图G=(V,E)有生成树的充要条件是图有生成树的充要条件是图G是连是连 通的通的.找图中生成树的方法找图中生成树的方法可分为两种：避圈法和破圈法可分为两种：避圈法和破圈法 A 避圈法避圈法 : 深探法和广探法深探法和广探法 B 破圈法破圈法 图论与网络分析A 避圈

21、法避圈法 这种方法就是在已给的图这种方法就是在已给的图G中，每步选出一条边使中，每步选出一条边使它与已选边不构成圈，直到选够它与已选边不构成圈，直到选够n-1条边为止条边为止. 这这种方法可称为种方法可称为“避圈法避圈法”或或“加边法加边法”在避圈法中，按照边的选法不同，找图中生成树在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：的方法可分为两种：深探法深探法和和广探法广探法.图论与网络分析a) 深探法深探法 若这样的边的另一端均已有标号，就退到标号为若这样的边的另一端均已有标号，就退到标号为步骤如下：步骤如下：i) 在点集在点集V中任取一点中任取一点u,ii) 若某点若某点v已得

22、标号，检已得标号，检端是否均已标号端是否均已标号. 若有边若有边(v,w)之之w未标号未标号,则给则给w代代v，重复，重复ii).i-1的的r点点,以以r代代v,重复重复ii),直到全部点得到标号为止直到全部点得到标号为止.给以标号给以标号0.查一端点为查一端点为v的各边，另一的各边，另一w以标号以标号i+1，记下边，记下边(v,w).令令例用深探法求出下图的一棵生成树例用深探法求出下图的一棵生成树 012345678910111213图论与网络分析13a) 深探法深探法0123456789101112例用深探法求出下图的一棵生成树例用深探法求出下图的一棵生成树 012345789101112

23、136图论与网络分析3b)广探法广探法步骤如下：步骤如下：i) 在点集在点集V中任取一点中任取一点u,ii) 令所有标号令所有标号i的点集为的点集为是否均已标号是否均已标号. 对所有未标对所有未标号之点均标以号之点均标以i+1,记下这些记下这些 iii) 对标号对标号i+1的点重复步的点重复步步骤步骤ii)，直到全部点得到，直到全部点得到给给u以标号以标号0.Vi,检查检查Vi,VVi中的边端点中的边端点边边.例用广探法求出下图的一棵生成树例用广探法求出下图的一棵生成树 1012213212234标号为止标号为止.图论与网络分析3b)广探法广探法 例用广探法求出下图的一棵生成树例用广探法求出下

24、图的一棵生成树 1012213212234显然图的生成树不唯一显然图的生成树不唯一.04321111222233图论与网络分析B 破圈法 相对于避圈法，还有一种求生成树的方法叫做相对于避圈法，还有一种求生成树的方法叫做“破圈法破圈法”. 这种方法就是在图这种方法就是在图G中任取一个圈，中任取一个圈，任意舍弃一条边，将这个圈破掉，重复这个步骤任意舍弃一条边，将这个圈破掉，重复这个步骤直到图直到图G中没有圈为止中没有圈为止.例例 用破圈法求出用破圈法求出下图的一棵生成树下图的一棵生成树.图论与网络分析B 破圈法例例 用破圈法求出下图的另一棵生成树用破圈法求出下图的另一棵生成树.不难发现，图不难发现

25、，图的生成树不是的生成树不是唯一的唯一的 .图论与网络分析三、三、 最小生成树与算法最小生成树与算法 介绍最小树的两种算法：介绍最小树的两种算法：Kruskal算法算法（或（或避圈法避圈法）和）和破圈法破圈法. 图论与网络分析A Kruskal算法（或避圈法）算法（或避圈法）步骤如下：步骤如下： 1) 选择边选择边e1，使得，使得w(e1)尽可能小；尽可能小；2) 若已选定边若已选定边 ，则从，则从ieee,.,21,.,21ieeeE中选取中选取 ，使得，使得:1iei) 为无圈图，为无圈图，,.,121ieeeG ii) 是满足是满足i)的尽可能小的权，的尽可能小的权，)(1iew 3)

26、重复步骤重复步骤2），直至选够），直至选够n-1条边条边.定理定理 由由Kruskal算法构作的任何生成树算法构作的任何生成树*121 ,.,nTG e ee都是最小树都是最小树.图论与网络分析,876432eeeeee例例用用Kruskal算法求下图的最小树算法求下图的最小树.在左图中在左图中 权值权值,.,821eee最小的边有最小的边有 任取一条任取一条 ,51ee,1e 在在 中选取权值中选取权值,.,832eee,5e最小的边最小的边 中权值最小边有中权值最小边有 , 从中选从中选：73,ee;3e任取一条边任取一条边,87642eeeee中选取在中选取中选取在中选取,7e已经选够已

27、经选够5-1条边，从而最小树条边，从而最小树构造结束。构造结束。图论与网络分析B破圈法算法算法2 步骤如下：步骤如下： 1) 从图从图G中任选一棵树中任选一棵树T1.2) 加上一条弦加上一条弦e1，T1+e1中中 立即生成一个圈立即生成一个圈. 去掉此去掉此 圈中最大权边，得到新圈中最大权边，得到新树树T2,以以T2代代T1,重复重复2)再再检查剩余的弦，直到全检查剩余的弦，直到全部弦检查完毕为止部弦检查完毕为止.例例用破圈法求下图的最小树用破圈法求下图的最小树.先求出上图的一棵生成树先求出上图的一棵生成树. 加以弦加以弦 e2,得到的圈得到的圈v1v3v2v1,去掉最大的权边去掉最大的权边e

28、2,得到一棵新得到一棵新树仍是原来的树；树仍是原来的树；2e 再加上弦再加上弦e7，得到圈，得到圈 v4v5v2v4,27e去掉最大的权边去掉最大的权边e6，得到一棵，得到一棵新树；如此重复进行，直到全新树；如此重复进行，直到全部的弦均已试过部的弦均已试过,得得最小树最小树.图论与网络分析例：一家企业分别要在例：一家企业分别要在6 6间办公室铺设网线接入口，间办公室铺设网线接入口，网线的可行走线方式如下图所示，如何铺设网线网线的可行走线方式如下图所示，如何铺设网线才能使网线总长为最短？才能使网线总长为最短？ 最短网线总长度为最小树权之和最短网线总长度为最小树权之和2+3+4+6+6=21 8

29、2 3 546 6 6 8v1v4v2v3v5v6图论与网络分析第三节第三节 最短路问题最短路问题 狄克斯特拉狄克斯特拉(Dijkstra)算法算法u路权：弧路权：弧(vi, vj)的权为的权为lij；路权是路；路权是路p中各条弧权之中各条弧权之 和和u最短路：在所有从最短路：在所有从vs到到vt 的路的路p中，求一条路权最短中，求一条路权最短的路的路u算法说明：算法说明：n1959年提出，目前公认的最短路算法年提出，目前公认的最短路算法n适合于求解所有弧权适合于求解所有弧权wij 0的最短路问题的最短路问题图论与网络分析第三节第三节 最短有向路问题最短有向路问题u基本思路基本思路: :n从始

30、点从始点v vs s 出发，逐步探寻，给每个点标号；出发，逐步探寻，给每个点标号；n标号分永久标号标号分永久标号P(vP(vk k) )和临时标号和临时标号T(vT(vk k) ) 两种：两种：p永久标号永久标号P(vk) 是从点是从点 vs vk 的最短路权的最短路权p临时标号临时标号T(vk) 是从点是从点 vs vk 最短路权的上最短路权的上界界n算法的每一步从临时标号集中选最小者变为永久标算法的每一步从临时标号集中选最小者变为永久标号；号；n经过逐次改变，就可以得到从点经过逐次改变，就可以得到从点v vs s 到各点的最短路到各点的最短路p标号形式：n单标号法是对每一点赋予一个路权标号

31、单标号法是对每一点赋予一个路权标号n双标号法是对每一点赋予两个标号：路标、路权双标号法是对每一点赋予两个标号：路标、路权。 图论与网络分析狄克斯特拉(Dijkstra)算法步骤1)( )0,( )2):( ,),( )min( ), ( )3)( )min( )ssiijijjjjjiijiiivPP vTT vvPvv vEvTvTT vT vP vlTPP vT vPPvv给 以 标号，其余各点均给 标号，若 为刚得到的 标号的点，考虑这样的点且为 标号。对 的 标号进行如下修改：比较所有具有 标号的点，把最小者改为 标号，即：当存在两个以上最小者时，可同时改为 标号，若全部点均为标号，则停止。否则，用 代2i转回 ）图论与网络分析 例：从发电厂（记为节点1）向某城市（记为节点6）输送电，必须通过中转站（记为节点2，3，4，5）转送。图给出了两节点间的距离。电力公司希望选择合适的中转站，使从电厂到城市的传输路线最短。即从节点1到节点6的最短路径。这就是一个最短路问题。 图论与网络分析单标号求最短路单标号求最短路13