图与网络分析教学课件PPT.ppt

第七章 图与网络分析 1、经典的图论问题 n七桥问题 n哈密顿问题（12面体） n中国邮路问题 n迷宫问题 例1：北京 天津 济南 青岛 郑州 徐州 连云港 武汉 南京上海 图中点代表城市， 点和点之间的连线 代表城市间的铁路线 图1 n例2：有a、b、c、d、e五支球队，他们之间的 比赛情况可以用图表示出来。已知a队和其他各队 都比赛过一次，b队和a、c队比赛过，d队和e、 c队比赛过，e队和a、d队比赛过。 v1 v2 v3 v4 v5 v1v2v3v4v5 图2 图3 如果在比赛中： a胜e， b胜c， a胜d， c胜a， e胜d， a胜b， v1 v2 v3 v4 v5注：本章所研究的图与平面几何中的图不 同，这里我们只关心图有几个点，点与点 之间有无连线，两条线有无公共顶点，点 与线是否有关联，至于连线的方式是直线 还是曲线，点与点的相对位置如何都是无 关紧要的。 1 2 4 34 1 2 3 图4 几个概念 1、边和弧 两点之间不带箭头的连线称为边，带箭头的连线称为弧 2、无向图 由点及边所组成的图为无向图，记为：g=(v,e)，其中v是 g的点的集合，e为g的边的集合，连接vivj的边记为vi ，vj或vj，vi，如图1，2，3 3、有向图 由点及弧所组成的图为有向图，记为：d=(v,a)，其中v是 g的点的集合，a为g的弧的集合，一条方向为从vi指向vj 的弧记为(vi，vj)，如图4 图的其他概念 ： 相邻点：两点之间的边属于e 相邻边：如果两条边有一个公共端点 环：边的两个端点相同 多重边（平行边）：两个点之间有多于一条边（弧） 多重图，无环但允许有多重边的图 简单图：无环且无多重边的图 注:在有向图中，如果两点之间有不同方向的两条弧， 不是多重边 端点的次d(v)：点 v 作为端点的边的个数； 奇点：d(v)=奇数； 偶点：d(v)=偶数； 悬挂点：d(v)=1；悬挂边：与悬挂点连接的 边， 孤立点：d(v)=0；空图：e = ，无边图。 定理1：在任一图中，所有顶点次数之和等 于所有边数的2倍。 定理2：在任一图中，奇点的个数必为偶数 。 在有向图中，以vi为始点的边数称为vi的出 次，以vi为终点的边数称为vi的入次，入次 和出次的和称为该点的次。 有向图中所有顶点的入次之和等于所有顶点 的的出次之和。 n图的连通性： 链：由两两相邻的点及其相关联的边构成的点边序 列；如： v0 , e1 , v1 , e2 , v2 , e3 , v3 , , vn-1 , en , vn ； v0 , vn分别为链的起点和终点 简单链：链中所含的边均不相同； 初等链：链中所含的点均不相同，也称通路； 圈：起点和终点相同的链； e8 v2 v3 v1 v4 v 5 v6 e6e7 e9 是一条链，且是开链，也是简单 链，但不是初等链，因为v1出现 两次。 是一个圈。 道路：由两两相邻的点及其相关联的弧构成的点弧交 错序列；如： v0 , e1 , v1 , e2 , v2 , e3 , v3 , , vn-1 , en , vn ； v0 , vn分别为链的起点和终点 回路：道路的起点和终点相同 连通图：图中任意两点之间均至少有一条链相连，否 则称作不连通图。 任何一个不连通的图都可以分为若干个连同子图，每一 个都称为原图的一个分图 例如图中，v1和v6之间没有通路，因此它不是连通图， 而如果去掉v6，则构成一个连通图。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6e7 e8 e9 连通是一个很重要的概念，如 果一个问题所对应的图是一个 不连通图，则该问题一定可以 分解成互不相关的子问题来加 以研究，即可以把不连通图分 解成连通的子图来研究。 n子图 设 g1 = v1 , e1 , g2 = v2 , e2 子图定义：如果 v2 v1 , e2 e1 称 g2 是 g1 的子图； 真子图：如果 v2 v1 , e2 e1 称 g2 是 g1 的真子图； 部分图：如果 v2 = v1 , e2 e1 称 g2 是 g1 的部分图； v1 v2 v3 v4 v5 v6 v7 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 v1 v2 v3 v5 v6 v2 v1 v3 v4 v5 v6 v7 e4 e5 e6 e7 e8 e9 e10 部分图 子图 必须指出，并不是从图g1中任 选一些顶点和边在一起就组成 g1的子图g1，而只有在g1中的 一条边以及连接该边的两个端 点均选入g2时，g2才是g1的子 图。 e1 e2 e4 e5 v2 v3 v1 真子图 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6e7 e8 e9 v1 e1 e2 e3 e4 v2 v3 v4 v5 v6 e6e7 e9 部分图 图的概念 树 一个没有圈的图称为一个无圈图或称为林。 一个连通的无圈图则称为树，一个林的每个连通子图 都是一个树。 定理 以下关于树的六种不同描述是等价的： 无圈连通图。 无圈，q=p-1。 连通，q=p-1。 无圈，但若任意增加一条边，则可得到一个且仅一 个圈。 连通，但若任意舍弃一条边，图便不连通。 每一对顶点之间有一条且仅有一条链。 v1 v2 v3 v5 v6 若t是图g（v，e）的部分图，且t是树， 则称t为g的部分树。 若t是图g的部分树，则从g中去掉t中所有的 边，所得到的子图称为g中的t的余树，也称 为g的一个余树。 余数不一定是树！ 一个没有圈的图称为一个无圈图或称为林。 一个连通的无圈图则称为树，一个林的每个连 通子图都是一个树。 树与部分树 n网络 n点和边带有某种数量指标的图称为网络 ，或称为赋权图 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 网络最小树问题 最小树问题的一般提法是：选取网络中的部分图，使得网络 连通，且使总权数最小。 在实际应用中，经常碰到需要求一个赋权连通图的最小树的 问题。例如，用节点表示城市，用边表示可以在两个城市之 间架设光缆，边上的权表示光缆的长度，试求应如何架设光 缆，才能使任意两城市之间均由光缆相通，且使光缆的总长 度最短。 求最小树的方法，依据的是树的特点，即无圈和连通，加上 最短的要求，方法主要有两种：一种称为破圈法，一种称为 取边避圈法。 n取边避圈法 依次在图中取一个权值最小的边，或者是相对最 短的边，并且在每次取边时都不能与已取的边构 成圈。 1 4 3 2 1 6 7 2 2 5 3 1 4 3 2 1 6 7 2 2 5 3 1 4 3 2 1 6 7 2 2 5 3 1 4 3 2 1 6 7 2 2 5 3 1 4 3 2 1 6 7 2 2 5 3 1 4 3 2 1 6 7 2 2 5 3 1 4 3 2 1 6 7 2 2 5 3 破圈法 n方法步骤 n在网络图中寻找一个圈，若已经无圈 则转。 n在圈中选取权数最大的边，从网络图 中截去该边，对新的网络，转。 n若q=p-1，则已找到最小树，否则网 络图不连通，无最小树。 1 4 3 2 1 6 7 2 2 5 3 中国邮路问题 n问题：在一个赋权图上求一个圈，经过图中 每一条边至少一次，使圈中各边权值的总和 为最小。 n概念 n欧拉链与欧拉圈 经过且仅经过图中每一条边一次的链称为 欧拉链，经过且仅经过图中每一条边一次 的圈称为欧拉圈 n定理 n连通多重图中含有欧拉链的充分必要条 件是图中奇点的个数为0或2。且当且仅 当没有奇点时图中含有欧拉圈，即没有 奇点的连通图必含有欧拉圈。 v1 v2 v3 v4 v5 v6 e=v5，v2，v1，v3，v2，v4，v3，v5，v4，v6，v5 n 奇偶点表上作业法 （1）找出奇点（一定为偶数个），在每两个奇点之间找一条链，在这些链经 过的所有边上增加一条边，这样所有的奇点变为偶点，一定存在欧拉圈，但是 不一定是路线最短的，所以需要检验和调整。 （2）检验增加的边的权值是否是最小的。 假设m是使得图g中不含奇点的所有增加边，则m是权值总和为最小的增加边 的充分必要条件是： 1）图g中每条边上最多增加一条边； 2）在图g的每个圈上，增加的边的总权值不超过该圈总权值的一半。 如果上述两个条件都满足则已经找到权值最小的欧拉圈 否则转入3） 3）调整增加边。如果1）不满足，则从该条边的增加边中去掉偶数条； 如果2）不满足，则将这个圈上的增加边去掉，将该圈的其余边上添加增加边 ，转入（2） v1 v2v3 v4v5 v6 3 4 2 33 2 4 3 5 v1 v2v3 v4v5 v6 3 4 2 33 2 4 3 5 v1 v2v3 v4v5 v6 3 4 2 33 2 4 3 5 v1 v2v3 v4v5 v6 3 4 2 33 2 4 3 5 v1，v6，v5，v4，v6，v2，v6，v3，v4，v3，v2，v1 网络 对有向图d=(v,a)，如果对于有向图d中的每一条弧 (vi,vj) a，都有一个数c(vi,vj) 与它对应，此时称d为 一个网络，或称赋权有向图。 有向网络：网络中每个边都是有向边； 无向网络：网络中每个边都是无向边； 混合网络：网络中既有有向边，又有无向边； 网络最短路线问题：寻找网络中从起点 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到vt的距离，记为d(vs,vt)。 p有向图权值非负- dijkstra算法 dijkstra算法的基本步骤（权值非负） 1、给顶点v1标号（0），v1称为已标号点，记标号点集为 v1=v1 2、在未标号点集v2中找出与标号点集v1中的顶点vi有弧相连 （并且以vi为起点）的点vj， 3、在第2步选出的点中，选出满足下面条件的点vk，并给vk标 号（l,l1k），其中l为第一标号， l1k为第二标号 为从v1到vk的最短路的长度，l表示在从v1到vk的最短路上，与vk 相邻的点是vl 4、若最后一个顶点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注：在给顶点编号时，如果在多个为标号点均 取得最小值llk则对这多个点同时标号，这些点 的第二个标号相同，但是第一个标号不一定相 同 p有向图某些权值为负 1、先对图中各个点按照dijkstra算法标号，称之为第一次标号， 令m=1，转入第二步； 2、对图中除了v1以外的所有点进行m+1次标号，记l1k(m+1)为对顶点 vk的第m+1次标号的第二个标号值，计算公式如下： 3、如果对所有的点l1k(m)= l1k(m+1）都成立则逆向追踪，找出最短路， 算法终止；若存在l1k(m) l1k(m+1）,则令m=m+1，返回第2步 n例4求从v1到v4的最短路 v1 v2 v3 v4 3 2 -2 -1 4 5 (0 ) v1 v2 v3 v4 3 2 -2 -1 4 5 (1,2) (1,3) (2,1) (0 ) v1 v2 v3 v4 3 2 -2 -1 4 5 (3,1) (1,3) (2,0) p无向图 v1 v2 v3 v4 v5 2 3 1 4 1 5 3 将边vi，vj看作两条弧， (vi, vj)和(vj, vi) 4、网络最大流问题 例5：下图表示从产地v1到销地v6的交通网，弧旁边的数字表示 这条运输线的最大通过能力，产品经过这个交通网从v1运 到v6，要求制定一个运输方案使得从v1运到v6的产品数量 最多。 基本概念 n网络与流 对有向图d=(v,a)，如果其中指定某一点vs为发点， 另一点vt为收点，其他点则称为中间点。若对于有向 图d中的每一条弧(vi,vj) a，都有一个数c(vi,vj) 0与它对应，称c为弧的容量，记为d=(v,a ,c) 定义在弧集合a上的一个函数f=f(vi,vj)称为网络d 上的流，并称f(vi,vj)为弧(vi,vj)上的流量，简记为fij n可行流： 满足下述条件的流称为可行流： （1）容量限制：对于每一个弧(vi,vj) a， 0fij cij （2）平衡条件： 对于中间点：流出量等于流入量，即对于每个i(is,t)有 对于发点： 对于收点： 称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增广链（可扩充链） 4 0 0 2 1 n截集与截量 设s，t是v的子集，st=空集，通常将始点在s中，终 点在t中的所有弧构成的集合记为(s,t) n任何一个可行流的流量不会超过任何一个截集的容量， 即 定理：可行流f*是最大流，当且仅当不存在关于f*的增广链 n根据定理，对于给定的可行流f，要判断它是 不是最大流只需要判断d中有没有关于f的增广 链。 n如果有则需要对f进行改进；如果没有增广链 ，则已经得到最大流。 寻找最大流的标号法 n网络d中的点分为两类，一类是标号点（属于 v1* ），一类是非标号点（不属于v1* ） ； n标号点有两类一类是已检查的，一类是未检查 的。每个标号点有两个标号：第一个标号表示 这个点的标号是从哪一点得到的，以便进一步 找出增广链，第二个标号是用来表示方向 1.标号过程 从vi出发的弧 进入vi的弧 vi变为标号且已检查的点，在vi旁加上*以示区别 2、调整过程 例6：用标号法求如下图所示的网络最大流 (8，5) vs v2 v1 v4 v3 vt (2,2) (6,5) (10,4) (7,2) (9,5) (6,0) (3,2) (5,2) (5,3) (8，5) vs