《图与网络分析教学课件PPT》由会员分享，可在线阅读，更多相关《图与网络分析教学课件PPT（71页珍藏版）》请在金锄头文库上搜索。
1、第七章 图与网络分析1、经典的图论问题n七桥问题n哈密顿问题（12面体）n中国邮路问题n迷宫问题例1：北京天津济南青岛郑州徐州连云港武汉南京上海图中点代表城市，图中点代表城市，点和点之间的连线点和点之间的连线代表城市间的铁路线代表城市间的铁路线图1n例例2：有：有A、B、C、D、E五支球队，他们之间的五支球队，他们之间的比赛情况可以用图表示出来。已知比赛情况可以用图表示出来。已知A队和其他各队队和其他各队都比赛过一次，都比赛过一次，B队和队和A、C队比赛过，队比赛过，D队和队和E、C队比赛过，队比赛过，E队和队和A、D队比赛过。队比赛过。v1v2v3v4v5v1v2v3v4v5图2图3如果在比
2、赛中：A胜E， B胜C， A胜D， C胜A， E胜D， A胜B，v1v2v3v4v5注：本章所研究的图与平面几何中的图不同，这里我们只关心图有几个点，点与点之间有无连线，两条线有无公共顶点，点与线是否有关联，至于连线的方式是直线还是曲线，点与点的相对位置如何都是无关紧要的。12434123图4几个概念1、边和弧、边和弧两点之间不带箭头的连线称为边，带箭头的连线称为弧两点之间不带箭头的连线称为边，带箭头的连线称为弧2、无向图、无向图由点及边所组成的图为无向图，记为：由点及边所组成的图为无向图，记为：G=(V,E)，其中，其中V是是G的点的集合，的点的集合，E为为G的边的集合，连接的边的集合，连接
3、ViVj的边记为的边记为Vi，Vj或或Vj，Vi，如图，如图1，2，33、有向图、有向图由点及弧所组成的图为有向图，记为：由点及弧所组成的图为有向图，记为：D=(V,A)，其中，其中V是是G的点的集合，的点的集合，A为为G的弧的集合，一条方向为从的弧的集合，一条方向为从Vi指向指向Vj的弧记为的弧记为(Vi，Vj)，如图，如图4图的其他概念 ： 相邻点：两点之间的边属于E相邻边：如果两条边有一个公共端点环：边的两个端点相同多重边（平行边）：两个点之间有多于一条边（弧）多重图，无环但允许有多重边的图简单图：无环且无多重边的图注:在有向图中，如果两点之间有不同方向的两条弧，不是多重边端点的次端点的
4、次d(v)：点 v 作为端点的边的个数；奇点：奇点：d(v)=奇数； 偶点：偶点：d(v)=偶数；悬挂点：悬挂点：d(v)=1；悬挂边：悬挂边：与悬挂点连接的边，孤立点：孤立点：d(v)=0；空图空图：E = ，无边图。定理定理1：在任一图中，在任一图中，所有顶点次数之和等所有顶点次数之和等于所有边数的于所有边数的2 2倍。倍。定理定理2：在任一图中，奇点的个数必为偶数。在任一图中，奇点的个数必为偶数。在有向图中，以在有向图中，以Vi为始点的边数称为为始点的边数称为Vi的的出出次次，以，以Vi为终点的边数称为为终点的边数称为Vi的的入次入次，入次，入次和出次的和称为该点的次。和出次的和称为该点
5、的次。有向图中所有顶点的入次之和等于所有顶点有向图中所有顶点的入次之和等于所有顶点的的出次之和。的的出次之和。n图的连通性：图的连通性：链：链：由两两相邻的点及其相关联的边构成的点边序由两两相邻的点及其相关联的边构成的点边序列；如：列；如： v0 , e1 , v1 , e2 , v2 , e3 , v3 , , vn-1 , en , vn ； v0 , vn分别为链的起点和终点分别为链的起点和终点 简单链：简单链：链中所含的边均不相同；链中所含的边均不相同；初等链：初等链：链中所含的点均不相同，也称通路；链中所含的点均不相同，也称通路；圈：圈：起点和终点相同的链；起点和终点相同的链；e8v
6、2 v3v1v4v5v6e6e7e9是一条链，且是开链，也是简单是一条链，且是开链，也是简单链，但不是初等链，因为链，但不是初等链，因为v1出现出现两次。两次。是一个圈。是一个圈。道路：道路：由两两相邻的点及其相关联的弧构成的点弧交错序列；如： v0 , e1 , v1 , e2 , v2 , e3 , v3 , , vn-1 , en , vn ； v0 , vn分别为链的起点起点和终点终点 回路：回路：道路的起点和终点相同连通图连通图：图中任意两点之间均至少有一条链相连，否则称作不连通图。任何一个不连通的图都可以分为若干个连同子图，每一个都称为原图的一个分图例如图中，例如图中，v1和和v6
7、之间没有通路，因此它不是连通图，之间没有通路，因此它不是连通图，而如果去掉而如果去掉v6，则构成一个连通图。，则构成一个连通图。 e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9连通是一个很重要的概念，如连通是一个很重要的概念，如果一个问题所对应的图是一个果一个问题所对应的图是一个不连通图，则该问题一定可以不连通图，则该问题一定可以分解成互不相关的子问题来加分解成互不相关的子问题来加以研究，即可以把不连通图分以研究，即可以把不连通图分解成连通的子图来研究。解成连通的子图来研究。n子图子图 设设 G1 = V1 , E1 , G2 = V2 , E2 子图定义：子图定义：如
8、果 V2 V1 , E2 E1 称 G2 是 G1 的子图；真子图：真子图：如果 V2 V1 , E2 E1 称 G2 是 G1 的真子图；部分图：部分图：如果 V2 = V1 , E2 E1 称 G2 是 G1 的部分图；v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10v1v2v3v5v6v2v1v3v4v5v6v7e4e5e6e7e8e9e10部分图子图必须指出，并不是从图必须指出，并不是从图G1中任中任选一些顶点和边在一起就组成选一些顶点和边在一起就组成G1的子图的子图G1，而只有在，而只有在G1中的中的一条边以及连接该边的两个端一条边以及连接该边的两个端点均选入点
9、均选入G2时，时，G2才是才是G1的子的子图。图。e1 e2 e4 e5v2 v3v1真子图e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9v1e1 e2 e3 e4v2 v3v4v5v6e6e7e9部分图图的概念 树 一个没有圈的图称为一个一个没有圈的图称为一个无圈图无圈图或称为或称为林林。一一个个连连通通的的无无圈圈图图则则称称为为树树，一一个个林林的的每每个个连连通通子子图图都是一个树。都是一个树。定理定理 以下关于树的六种不同描述是等价的：以下关于树的六种不同描述是等价的：无圈连通图。无圈连通图。无圈，无圈，q=p-1。连通，连通，q=p-1。无无圈圈，但但若若任
10、任意意增增加加一一条条边边，则则可可得得到到一一个个且且仅仅一一个圈。个圈。连通，但若任意舍弃一条边，图便不连通。连通，但若任意舍弃一条边，图便不连通。 每一对顶点之间有一条且仅有一条链。每一对顶点之间有一条且仅有一条链。v1v2v3v5v6若若T是是图图G（V，E）的的部部分分图图，且且T是是树树，则则称称T为为G的的部分树部分树。若若T是是图图G的的部部分分树树，则则从从G中中去去掉掉T中中所所有有的的边边，所所得得到到的的子子图图称称为为G中中的的T的的余余树树，也也称称为为G的一个余树。的一个余树。余数不一定是树！余数不一定是树！ 一个没有圈的图称为一个一个没有圈的图称为一个无圈图无圈
11、图或称为或称为林林。一个连通的无圈图则称为一个连通的无圈图则称为树树，一个林的每个连，一个林的每个连通子图都是一个树。通子图都是一个树。树与部分树 n网络网络n点和边带有某种数量指标的图称为网络，点和边带有某种数量指标的图称为网络，或称为赋权图或称为赋权图 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2网络最小树问题 最最小小树树问问题题的的一一般般提提法法是是：选选取取网网络络中中的的部部分分图图，使使得得网网络络连通，且使总权数最小。连通，且使总权数最小。在在实实际际应应用用中中，经经常常碰碰到到需需要要求求一一个个赋赋权权连连通通图图的的最最小小树树的的问问题题。例例
12、如如，用用节节点点表表示示城城市市，用用边边表表示示可可以以在在两两个个城城市市之之间间架架设设光光缆缆，边边上上的的权权表表示示光光缆缆的的长长度度，试试求求应应如如何何架架设设光光缆缆，才才能能使使任任意意两两城城市市之之间间均均由由光光缆缆相相通通，且且使使光光缆缆的的总总长长度最短。度最短。求求最最小小树树的的方方法法，依依据据的的是是树树的的特特点点，即即无无圈圈和和连连通通，加加上上最最短短的的要要求求，方方法法主主要要有有两两种种：一一种种称称为为破破圈圈法法，一一种种称称为为取边避圈法。取边避圈法。 n取边避圈法依次在图中取一个权值最小的边，或者是相对最短的边，并且在每次取边时
13、都不能与已取的边构成圈。14321672253143216722531432167225314321672253143216722531432167225314321672253破圈法n方法步骤方法步骤n在网络图中寻找一个圈，若已经无圈在网络图中寻找一个圈，若已经无圈则转则转。n在圈中选取权数最大的边，从网络图在圈中选取权数最大的边，从网络图中截去该边，对新的网络，转中截去该边，对新的网络，转。n若若q=p-1，则已找到最小树，否则网，则已找到最小树，否则网络图不连通，无最小树。络图不连通，无最小树。14321672253中国邮路问题n问题：在一个赋权图上求一个圈，经过图中每一条边至少一次，使
14、圈中各边权值的总和为最小。n概念概念n欧拉链与欧拉圈欧拉链与欧拉圈经过且仅经过图中每一条边一次的链称为经过且仅经过图中每一条边一次的链称为欧拉链，经过且仅经过图中每一条边一次欧拉链，经过且仅经过图中每一条边一次的圈称为欧拉圈的圈称为欧拉圈n定理定理n连通多重图中含有欧拉链的充分必要条连通多重图中含有欧拉链的充分必要条件是图中奇点的个数为件是图中奇点的个数为0或或2。且当且仅。且当且仅当没有奇点时图中含有欧拉圈，即没有当没有奇点时图中含有欧拉圈，即没有奇点的连通图必含有欧拉圈。奇点的连通图必含有欧拉圈。v1v2v3v4v5v6E=v5，v2，v1，v3，v2，v4，v3，v5，v4，v6，v5n
15、 奇偶点表上作业法奇偶点表上作业法（1）找出奇点（一定为偶数个），在每两个奇点之间找一条链，在这些链经）找出奇点（一定为偶数个），在每两个奇点之间找一条链，在这些链经过的所有边上增加一条边，这样所有的奇点变为偶点，一定存在欧拉圈，但是过的所有边上增加一条边，这样所有的奇点变为偶点，一定存在欧拉圈，但是不一定是路线最短的，所以需要检验和调整。不一定是路线最短的，所以需要检验和调整。（2）检验增加的边的权值是否是最小的。）检验增加的边的权值是否是最小的。假设假设M是使得图是使得图G中不含奇点的所有增加边，则中不含奇点的所有增加边，则M是权值总和为最小的增加边是权值总和为最小的增加边的充分必要条件是
16、：的充分必要条件是：1）图）图G中每条边上最多增加一条边；中每条边上最多增加一条边；2）在图）在图G的每个圈上，增加的边的总权值不超过该圈总权值的一半。的每个圈上，增加的边的总权值不超过该圈总权值的一半。如果上述两个条件都满足则已经找到权值最小的欧拉圈如果上述两个条件都满足则已经找到权值最小的欧拉圈否则转入否则转入3）3）调整增加边。如果）调整增加边。如果1）不满足，则从该条边的增加边中去掉偶数条；）不满足，则从该条边的增加边中去掉偶数条；如果如果2）不满足，则将这个圈上的增加边去掉，将该圈的其余边上添加增加边，）不满足，则将这个圈上的增加边去掉，将该圈的其余边上添加增加边，转入（转入（2）v
17、1v2v3v4v5v6342332435v1v2v3v4v5v6342332435v1v2v3v4v5v6342332435v1v2v3v4v5v6342332435V1，v6，v5，v4，v6，v2，v6，v3，v4，v3，v2，v1网络网络对有向图对有向图D=(V,A)，如果对于有向图，如果对于有向图D中的每一条弧中的每一条弧(vi,vj) A，都有一个数，都有一个数c(vi,vj) 与它对应，此时称与它对应，此时称D为一为一个网络，或称赋权有向图。个网络，或称赋权有向图。有向网络：网络中每个边都是有向边；有向网络：网络中每个边都是有向边；无向网络：网络中每个边都是无向边；无向网络：网络中
18、每个边都是无向边；混合网络：网络中既有有向边，又有无向边；混合网络：网络中既有有向边，又有无向边；网络最短路线问题：寻找网络中从起点网络最短路线问题：寻找网络中从起点 v1 到终点到终点 vn 的最的最短路线。短路线。3、网络最短路问题、网络最短路问题n一般的最短路问题描述：给定一个赋权有向图D=(V,A)，对每一个弧a=(vi,vj)，相应地有权w(a)=wij，又给定D中的任何两个顶点vs和vt ，设P是从vs到vt的路，定义路P的权是P中所有弧之和，记为w(P)，最短路问题就是要在所有从vs到vt的路中，求一条权最小的路，即一条从vs到vt的路P0使得：路路P0的权称为从的权称为从vs到
19、到vt的距离，记为的距离，记为d(vs,vt)。p有向图权值非负- Dijkstra算法Dijkstra算法的基本步骤（权值非负）算法的基本步骤（权值非负）1、给顶点、给顶点v1标号（标号（0），），v1称为已标号点，记标号点集为称为已标号点，记标号点集为V1=v12、在未标号点集、在未标号点集V2中找出与标号点集中找出与标号点集V1中的顶点中的顶点vi有弧相连有弧相连（并且以（并且以vi为起点）的点为起点）的点vj，3、在第、在第2步选出的点中，选出满足下面条件的点步选出的点中，选出满足下面条件的点vk，并给，并给vk标标号（号（l,L1k），其中），其中l为第一标号，为第一标号， L1k为
20、第二标号为第二标号为从为从v1到到vk的最短路的长度，的最短路的长度，l表示在从表示在从v1到到vk的最短路上，与的最短路上，与vk相邻的点是相邻的点是vl4、若最后一个顶点、若最后一个顶点vn未标号，则转回第未标号，则转回第2步；若步；若vn已标号，则已标号，则从从vn开始，按照第一个标号逆向追踪，直到开始，按照第一个标号逆向追踪，直到v1，就得到从，就得到从v1到到vn的最短路，的最短路，vn的第二个标号表示最短路的长度。的第二个标号表示最短路的长度。n例3求从v1到v8的最短路(0)(1,1)(1,3)(3,5)(2,6)(5,10)(5,9)(5,12)n注：在给顶点编号时，如果在多个
21、为标号点均取得最小值Llk则对这多个点同时标号，这些点的第二个标号相同，但是第一个标号不一定相同p有向图某些权值为负有向图某些权值为负1 1、先对图中各个点按照、先对图中各个点按照DijkstraDijkstra算法标号，称之为第一次标号，算法标号，称之为第一次标号，令令m=1m=1，转入第二步；，转入第二步；2 2、对图中除了、对图中除了v v1 1以外的所有点进行以外的所有点进行m+1m+1次标号，记次标号，记L L1k1k(m+1)(m+1)为对顶点为对顶点v vk k的第的第m+1m+1次标号的第二个标号值，计算公式如下：次标号的第二个标号值，计算公式如下：3 3、如果对所有的点、如果
22、对所有的点L L1k1k(m)(m)= L= L1k1k(m+1(m+1）都成立则逆向追踪，找出最短路，都成立则逆向追踪，找出最短路，算法终止；若存在算法终止；若存在L L1k1k(m)(m) L L1k1k(m+1(m+1）, ,则令则令m=m+1m=m+1，返回第，返回第2 2步步n例4求从v1到v4的最短路v1v2v3v432-2-145(0)v1v2v3v432-2-145(1,2)(1,3)(2,1)(0)v1v2v3v432-2-145(3,1)(1,3)(2,0)p无向图v1v2v3v4v52314153将边vi，vj看作两条弧，(vi, vj)和(vj, vi)4、网络最大流问
23、题例例5：下图表示从产地：下图表示从产地v1到销地到销地v6的交通网，弧旁边的数字表示的交通网，弧旁边的数字表示这条运输线的最大通过能力，产品经过这个交通网从这条运输线的最大通过能力，产品经过这个交通网从v1运运到到v6，要求制定一个运输方案使得从，要求制定一个运输方案使得从v1运到运到v6的产品数量的产品数量最多。最多。基本概念基本概念n网络与流网络与流对有向图对有向图D=(V,A)，如果其中指定某一点，如果其中指定某一点vs为发点，为发点，另一点另一点vt为收点，其他点则称为中间点。若对于有向为收点，其他点则称为中间点。若对于有向图图D中的每一条弧中的每一条弧(vi,vj) A，都有一个数
24、，都有一个数c(vi,vj) 0与它对应，称与它对应，称c为弧的容量，记为为弧的容量，记为D=(V,A ,C)定义在弧集合定义在弧集合A上的一个函数上的一个函数f=f(vi,vj)称为网络称为网络D上的流，并称上的流，并称f(vi,vj)为弧为弧(vi,vj)上的流量，简记为上的流量，简记为fijn可行流：可行流：满足下述条件的流称为可行流：满足下述条件的流称为可行流：（1）容量限制：对于每一个弧）容量限制：对于每一个弧(vi,vj) A， 0fij cij （2）平衡条件：）平衡条件：对于中间点：流出量等于流入量，即对于每个对于中间点：流出量等于流入量，即对于每个i(is,t)有有对于发点：
25、对于收点：称称v(f)为可行流的流量，发点的净输出量等于收点的净输入量。为可行流的流量，发点的净输出量等于收点的净输入量。最大流问题就是要找出一个可行流使得最大流问题就是要找出一个可行流使得v(f)达到最大达到最大n饱和弧和非饱和弧网络D=(V,A ,C)，f=f(vi,vj)是D的可行流，则如果某一条弧(vi,vj) A满足（1）fij = cij ，则称(vi,vj)为饱和弧；（2） fij 0 ， 则称(vi,vj)为非零流弧；n前向弧和后向弧网络D中与给定的链 方向一致的弧 称为前向弧，记作 ；与给定的链方向相反的弧称为后向弧，记作 ；n增广链（可扩充链）40021n截集与截量设S，T
26、是V的子集，ST=空集，通常将始点在S中，终点在T中的所有弧构成的集合记为(S,T)n任何一个可行流的流量不会超过任何一个截集的容量，任何一个可行流的流量不会超过任何一个截集的容量，即即定理：可行流f*是最大流，当且仅当不存在关于f*的增广链n根据定理，对于给定的可行流f，要判断它是不是最大流只需要判断D中有没有关于f的增广链。n如果有则需要对f进行改进；如果没有增广链，则已经得到最大流。寻找最大流的标号法n网络D中的点分为两类，一类是标号点（属于V1* ），一类是非标号点（不属于V1* ） ；n标号点有两类一类是已检查的，一类是未检查的。每个标号点有两个标号：第一个标号表示这个点的标号是从哪
27、一点得到的，以便进一步找出增广链，第二个标号是用来表示方向1.标号过程从vi出发的弧进入vi的弧vi变为标号且已检查的点，在变为标号且已检查的点，在vi旁加上旁加上*以示区别以示区别2、调整过程例6：用标号法求如下图所示的网络最大流(8，5)vsv2v1v4v3vt(2,2)(6,5)(10,4)(7,2)(9,5)(6,0)(3,2)(5,2)(5,3)(8，5)vsv2v1v4v3vt(2,2)(6,5)(10,4)(7,2)(9,5)(6,0)(3,2)(5,2)(5,3)(0,+)(s,+)*(1,+)(1,-)(1,+)*(4,+)(3,+)(vs, v1, v4, vt)*(8，7
28、)vsv2v1v4v3vt(2,2)(6,5)(10,4)(7,4)(9,5)(6,0)(3,0)(5,2)(5,3)(0,+)(s,+)*(1,+)(1,+)*(3,+)(4+)(vs, v1, v3, vt)(2,+)(8，8)vsv2v1v4v3vt(2,2)(6,5)(10,4)(7,4)(9,6)(6,0)(3,0)(5,3)(5,3)(0,+)*无法再标号最小费用最大流n最小费用最大流问题：(1,2)(5,6)(3,1)(3,3)(1,2)(1,3)(3,4)vsvt(dij,cij)1533113vsvt(2,0)(6,0)(1,0)(3,0)(2,0)(3,0)(4,0)vsvt(2,0)(6,0)(1,1)(3,0)(2,0)(3,1)(4,0)vsvt15-33113vsvt-1(Cij, fij)(2,2)(6,0)(1,1)(3,2)(2,0)(3,3)(4,0)vsvt-15-3213vsvt-1-2
