图与网路分析报告探讨(ppt 45页).ppt

1、图与网路分析,图是最直观的模型,2,图论 Graph Theory,哥尼斯堡七桥问题 (Knigsberg Bridge Problem) Leonhard Euler (1707-1783) 在1736年发表第一篇图论方面的论文，奠基了图论中的一些基本定理 很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联,3,6.1 图与网路的基本概念,6.1.1图与网路 节点 (Vertex) 物理实体、事物、概念 一般用 vi 表示 边 (Edge) 节点间的连线，表示有关系 一般用 eij 表示 图 (Graph) 节点和边的集合 一般用 G(V,E) 表示 点集 V=v1,v2, v

2、n 边集E=eij ,网路 (Network) 边上具有表示连接强度的权值，如 wij 又称加权图(Weighted graph),4,6.1.2 无向图与有向图,边都没有方向的图称为无向图，如图6.1 在无向图中 eij=eji，或 (vi, vj)=(vj, vi) 当边都有方向时，称为有向图，用G(V,A)表示 在有向图中，有向边又称为弧，用 aij表示，i, j 的顺序是不能颠倒的，图中弧的方向用箭头标识 图中既有边又有弧，称为混合图,6.1.3 端点，关联边，相邻，次,图中可以只有点，而没有边；而有边必有点 若节点vi, vj 之间有一条边 eij，则称 vi, vj 是 eij 的

3、端点(end vertex)，而 eij 是节点 vi, vj 的关联边(incident edge) 同一条边的两个端点称为相邻(adjacent)节点，具有共同端点的边称为相邻边 一条边的两个端点相同，称为自环(self-loop)；具有两个共同端点的两条边称为平行边(parallel edges) 既没有自环也没有平行边的图称为简单图(simple graph) 在无向图中，与节点相关联边的数目，称为该节点的“次”(degree)，记为 d ；次数为奇数的点称为奇点(odd),次数为偶数的点称为偶点(even)；图中都是偶点的图称为偶图(even graph),6,6.1.3 端点，关联

4、边，相邻，次,有向图中，由节点指向外的弧的数目称为正次数，记为 d+，指向该节点的弧的数目称为负次数，记为 d 次数为 0 的点称为孤立点(isolated vertex) ，次数为 1 的点称为悬挂点(pendant vertex) 定理 1：图中奇点的个数总是偶数个 6.1.4 链，圈，路径，回路，欧拉回路 相邻节点的序列 v1 ,v2 , vn 构成一条链(link)，又称为行走(walk)；首尾相连的链称为圈(loop)，或闭行走 在无向图中，节点不重复出现的链称为路径(path)；在有向图中，节点不重复出现且链中所有弧的方向一致，则称为有向路径(directed path) 首尾相连

5、的路径称为回路(circuit)；,7,6.1.4 链，圈，路径，回路，连通图,走过图中所有边且每条边仅走一次的闭行走称为欧拉回路 定理 2：偶图一定存在欧拉回路(一笔画定理) 6.1.4 连通图，子图，成分 设有两个图 G1(V1, E1), G2(V2, E2), 若V2 V1, E2 E1， 则 G2 是 G1 的子图 无向图中，若任意两点间至少存在一条路径，则称为连通图(connected graph)，否则为非连通图( discon-nected graph)；非连通图中的每个连通子图称为成分 (component) 链，圈，路径(简称路)，回路都是原图的子图 平面图(planar

6、graph)，若在平面上可以画出该图而没有任何边相交,8,6.2 树图与最小生成树,一般研究无向图 树图：倒置的树，根(root)在上，树叶(leaf)在下 多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图,9,6.2.1 树的定义及其性质,任两点之间有且只有一条路径的图称为树(tree)，记为T 树的性质： 最少边的连通子图，树中必不存在回路 任何树必存在次数为 1 的点 具有 n 个节点的树 T 的边恰好为 n1 条，反之，任何有n 个节点， n1 条边的连通图必是一棵树 6.2.2 图的生成树 树 T 是连通图 G 的生成树(spanning tree)，若

7、T 是 G的子图且包含图 G 的所有的节点；包含图 G 中部分指定节点的树称为 steiner tree 每个节点有唯一标号的图称为标记图，标记图的生成树称为标记树(labeled tree) Caylay 定理：n (2)个节点，有nn2个不同的标记树,10,6.2.2 图的生成树,如何找到一棵生成树 深探法(depth first search)：任选一点标记为 0 点开始搜索，选一条未标记的边走到下一点，该点标记为 1，将走过的边标记；假设已标记到 i 点，总是从最新标记的点向下搜索，若从 i 点无法向下标记，即与 i 点相关联的边都已标记或相邻节点都已标记，则退回到 i 1 点继续搜索

8、，直到所有点都被标记 广探法(breadth first search)：是一种有层级结构的搜索，一般得到的是树形图,11,6.2.3 最小生成树,有n 个乡村，各村间道路的长度是已知的，如何敷设光缆线路使 n 个乡村连通且总长度最短 显然，这要求在已知边长度的网路图中找最小生成树 最小生成树的算法： Kruskal 算法：将图中所有边按权值从小到大排列，依次选所剩最小的边加入边集 T，只要不和前面加入的边构成回路，直到 T 中有 n1 条边，则 T 是最小生成树 Kruskal 算法基于下述定理 定理 3 指定图中任一点vi，如果 vj 是距 vi 最近的相邻节点，则关联边 eij 必在某个

9、最小生成树中。 推论 将网路中的节点划分为两个不相交的集合V1和V2，V2=VV1，则V1和V2间权值最小的边必定在某个最小生成树中。,12,6.2.3 最小生成树,最小生成树不一定唯一 定理 3 推论是一个构造性定理，它指示了找最小生成树的有效算法 Prim 算法：不需要对边权排序，即可以直接在网路图上操作，也可以在边权矩阵上操作，后者适合计算机运算 边权矩阵上的 Prim 算法： 1、根据网路写出边权矩阵，两点间若没有边，则用表示； 2、从 v1 开始标记，在第一行打 ，划去第一列； 3、从所有打 的行中找出尚未划掉的最小元素，对该元素画圈，划掉该元素所在列，与该列数对应的行打 ； 4、若

10、所有列都划掉，则已找到最小生成树(所有画圈元素所对应的边)；否则，返回第 3 步。 该算法中，打 行对应的节点在 V1中，未划去的列在 V2中,13,6.2.3 最小生成树,Prim算法是多项式算法 Prim算法可以求最大生成树 网路的边权可以有多种解释，如效率 次数受限的最小生成树尚无有效算法 最小 Steiner 树尚无有效算法,14,6.3 最短路问题,6.3.1 狄克斯特拉算法 (Dijkstra algorithm, 1959) 计算两节点之间或一个节点到所有节点之间的最短路 令 dij 表示 vi 到 vj 的直接距离(两点之间有边)，若两点之间没有边，则令 dij = ，若两点之

11、间是有向边，则 dji = ；令 dii = 0，s 表示始点，t 表示终点 0、令始点Ts=0，并用框住，所有其它节点临时标记 Tj= ； 1、从 vs 出发，对其相邻节点 vj1 进行临时标记，有 Tj1=ds,j1 ； 2、在所有临时标记中找出最小者，并用框住，设其为 vr 。若此时全部节点都永久标记，算法结束；否则到下一步； 3、从新的永久标记节点 vr 出发，对其相邻的临时标记节点进行再标记，设 vj2 为其相邻节点，则 Tj2=minTj2, Tr+dr,j2 ，返回第2步。,15,例1 狄克斯特拉算法,0,8,15,10,12,15,11,31,13,16,Dijkstra最短路

12、算法的特点和适应范围,一种隐阶段的动态规划方法 每次迭代只有一个节点获得永久标记，若有两个或两个以上节点的临时标记同时最小，可任选一个永久标记；总是从一个新的永久标记开始新一轮的临时标记，是一种深探法 被框住的永久标记 Tj 表示 vs 到 vj 的最短路，因此 要求 dij0，第 k 次迭代得到的永久标记，其最短路中最多有 k 条边，因此最多有n1 次迭代 可以应用于简单有向图和混合图，在临时标记时，所谓相邻必须是箭头指向的节点；若第 n1 次迭代后仍有节点的标记为 ，则表明 vs 到该节点无有向路径 如果只求 vs 到 vt 的最短路，则当 vt 得到永久标记算法就结束了；但算法复杂度是一

13、样的 应用 Dijkstra 算法 n1 次 ，可以求所有点间的最短路 vs 到所有点的最短路也是一棵生成树，但不是最小生成树,17,6.3.2 Warshall-Floyd算法 (1962),Warshall-Floyd算法可以解决有负权值边(弧)的最短路问题 该算法是一种整体算法，一次求出所有点间的最短路 该算法不允许有负权值回路，但可以发现负权值回路 该算法基于基本的三角运算 定义 对给定的点间初始距离矩阵dij，令dii=，对所有 i。对一 个固定点 j，运算 dik=mindik, dij+djk, 对所有 i, k j , 称为 三角运算。(注意，这里允许 i=k) 定理 依次对

14、j=1,2,n 执行三角运算，则 dik 最终等于 i 到 k 间最短路的长度。,18,6.3.2 Floyd-Warshall 算法 (1962),for i=1 to n do dii=; for all eij=0; for j=1 to n do for i=1 to n do if ij then for k=1 to n do if kj then begin dik=mindik, dij+djk; if dikdij+djk then eik=j end;,若网路中存在负回路，则计算中，某些 dii 会小于0，此时应中断算法 显然，Floyd 算法要进行 n(n-1)2 次加法

15、和比较 如何回溯找出任两点之间的最短路？ 在Floyd 算法中设一伴随矩阵E=eik， eik 记录了 i 到 k 最短路中最后一个中间节点,19,小结,最短路有广泛的应用 (6.3.4节 市话局扩容方案) 最短路的多种形式：无向图，有向图无循环圈，有向图，混合图，无负边权，有负边权，有负回路，k-最短路等 当存在负权值边时，Floyd算法比Dijkstra算法效率高，且程序极简单。但Dijkstra算法灵活 若图是前向的，则Dijkstra算法也可以求两点间最长路 一般情况下，两点间最长路是 NP-complete，但最短路是 P算法 两点间k-最短路：分为边不相交的和边相交的 求边不相交的

16、k-最短路非常容易：先求最短路，将该最短路中的边从网路删去，再用Dijkstra算法可求次最短路，以此类推,20,6.4 网路的最大流和最小截,6.4.1 网路的最大流的概念 网路流一般在有向图上讨论 定义网路上支路的容量为其最大通过能力，记为 cij ，支路上的实际流量记为 fij 图中规定一个发点s，一个收点t 节点没有容量限制，流在节点不会存储 容量限制条件：0 fij cij 平衡条件：,满足上述条件的网路流称为可行流，总存在最大可行流 当支路上 fij = cij ，称为饱和弧 最大流问题也是一个线性规划问题,21,6.4.2 截集与截集容量,定义：把网路分割为两个成分的弧的最小集合

17、，其中一 个成分包含 s 点，另一个包含 t 点 。 一般包含 s 点的成分中的节点集合用V表示，包含 t 点的成分中的节点集合用V表示 截集容量是指截集中正向弧的容量之和,福特-富克森定理：网路的最大流等于最小截集容量,22,6.4.3 确定网路最大流的标号法,从任一个初始可行流出发，如 0 流 基本算法：找一条从 s 到 t 点的增广链(augmenting path) 若在当前可行流下找不到增广链，则已得到最大流 增广链中与 s 到 t 方向一致的弧称为前向弧，反之后向弧,增广过程：前向弧 fij=fij +q , 后向弧 fij=fij q 增广后仍是可行流,23,最大流最小截的标号法

18、步骤,第一步：标号过程，找一条增广链 1、给源点 s 标号s+,q(s)=，表示从 s 点有无限流出潜力 2、找出与已标号节点 i 相邻的所有未标号节点 j，若 (1) (i, j)是前向弧且饱和，则节点 j 不标号； (2) (i, j)是前向弧且未饱和，则节点 j 标号为i+,q(j)，表示从节点 i 正向流出，可增广 q(j)=minq(i), cijfij ； (3) (j, i)是后向弧，若 fji=0，则节点 j 不标号； (4) (j, i)是后向弧，若 fji0，则节点 j 标号为i,q(j)，表示从节点 j 流向 i，可增广 q(j)=minq(i), fji ； 3、重复步

19、骤 2，可能出现两种情况： (1) 节点 t 尚未标号，但无法继续标记，说明网路中已不存在增广链，当前流 v(f) 就是最大流；所有获标号的节点在 V 中，未获标号节点在 V 中，V 与 V 间的弧即为最小截集；算法结束 (2)节点 t 获得标号，找到一条增广链，由节点 t 标号回溯可找出该增广链；到第二步,24,最大流最小截的标号法步骤,第二步：增广过程 1、对增广链中的前向弧，令 f=f+q(t)，q(t) 为节点 t 的标记值 2、对增广链中的后向弧，令 f=fq(t) 3、非增广链上的所有支路流量保持不变 第三步：抹除图上所有标号，回到第一步 以上算法是按广探法描述的，但在实际图上作业

20、时，按深探法进行更快捷 一次只找一条增广链，增广一次换一张图 最后一次用广探法，以便找出最小截集,25,最大流最小截集的标号法举例,(s+,),(s+,6),(2,6),(3+,1),(4+,1),(s+,),(s+,5),(2+,2),(5,2),(4+,2),26,最大流最小截集的标号法举例,(s+,),(s+,3),(2,3),最小截集,27,最大流标号法的复杂度讨论,找一条增广链的计算量是容易估计的，不会超过O(n2) 但是最多迭代多少次(即增广的次数)就很难估计，在最坏情况下，与边的容量有关；如上图：先增广 s u v t , 然后增广 s v u t，每次只能增广 1 个单位，故要

21、增广4000次才能结束 克服这种缺点的经验方法： 尽量先用段数少的增广链 尽量不重复前面出现过的增广链,28,6.4.4 多端网路问题,29,6.4.5 最小费用最大流,双权网路：每条弧不但有容量，还有单位流量的通过费用 两种解法：一种基于最小费用路径算法；一种基于可行弧集的最大流算法 基于最小费用路径算法：总是在当前找到的最小费用的路径上增广流；缺点是每次增广后要改变弧的费用，且出现负权值费用的弧 基于可行弧集的最大流算法：从 0 费用弧集开始应用最大流算法，然后根据计算信息提高费用的限界P，使可行弧集增大，再应用最大流算法，直至所有弧都进入可行弧集。这种算法是一种主-对偶规划的解法。使用这

22、种方法的还有运输问题、匹配问题,30,6.4.5 以最短路为基础汇总网路上的流,在电路网中每两点之间都有中继电路群需求，但并不是任两点都有物理传输链路 根据两点间最短传输路径将该两点间的电路需求量加载到这条传输路径上去：设 a25=10 是节点2 和 5 之间的电路需求，节点2 和 5 之间的最短传输路径为 2135，则加载过程为: T21=T21+10, T13=T13+10, T35=T35+10； Tij 是传输链路 ij 上加载的电路数；当所有点间电路都加载完则算法结束,31,6.5 欧拉回路和中国邮递员问题,中国邮递员问题(Chinese Postman Problem, CPP)是

23、由我国管梅谷教授于1962年首先提出并发表的 问题是从邮局出发，走遍邮区的所有街道至少一次再回到邮局，走什么路由才能使总的路程最短？ 如果街区图是一个偶图，根据定理 3，一定有欧拉回路，CPP 问题也就迎刃而解了 若街区图不是偶图，则必然有一些街道要被重复走过才能回到原出发点 显然要在奇次点间加重复边 如何使所加的边长度最少 归结为求奇次点间的最小 匹配( minimum weighted match) 由Edmons 给出 多项式算法(1965),32,解中国邮递员问题的步骤,0、将图中的所有悬挂点依次摘去 1、求所有奇次点间的最短距离和最短路径 2、根据奇次点间的最短距离求最小完全匹配 3

24、、根据最小完全匹配和最短路径添加重复边 4、将悬挂点逐一恢复，并加重复边 5、根据得到的偶图，给出欧拉回路的若干种走法,33,解中国邮递员问题的步骤,34,6.6 哈密尔顿回路及旅行推销员问题,6.6.1 哈密尔顿回路( Hamiltonian circuit) 连通图G(V,E)中的回路称为哈密尔顿回路，若该回路包括图中所有的点。显然哈密尔顿回路有且只有 n 条边，若|V|=n 连通图具有哈密尔顿回路的充分必要条件是什么？这个问题是由爱尔兰数学家哈密尔顿1859年提出的，但至今仍未解决 欧拉回路是对边进行访问的问题，哈密尔顿回路是对点进行访问的问题 搜索哈密尔顿回路的难度是 NP-compl

25、ete 任两点间都有边的图称为完全图(或全连接图) 完全图中有多少个不同的哈密尔顿回路？ 完全图中有多少个边不相交的哈密尔顿回路？ 最小哈密尔顿回路问题 (NP-complete) 哈密尔顿路径：包含图中所有点的路径 为什么说找两点间的最长路是非常困难的问题？,(n1)!/2,(n1)/2,35,6.6.2 旅行推销员问题(Traveling Salesman Problem),旅行推销员问题(TSP)：设v1, v2, .,vn 为 n 个已知城市，城市之间的旅程也是已知的，要求推销员从 v1出发，走遍所有城市一次且仅一次又回到出发点，并使总旅程最短 这种不允许点重复的旅行推销员问题就是最小

26、哈密尔顿回路问题 一般旅行推销员问题(GTSP)：允许点重复的TSP 当网路边权满足三角不等式时，一般旅行推销员问题就等价于最小哈密尔顿回路问题 当网路边权不满足三角不等式时，只要用两点间最短路的距离代替原来的边权，就可以满足三角不等式，在此基础上求最小哈密尔顿回路 典型的应用： 乡邮员的投递路线 邮递员开邮箱取信的路线问题 邮车到各支局的转趟问题,36,TSP 的启发式算法(Heuristic algorithm),穷举法：指数算法 分支定界法：隐枚举法 二交换法 (two-option, Lins algorithm) 哈密尔顿回路可以用点的序列表示 从任一个哈密尔顿回路(即任何一个序列)

27、出发 按照一定顺序试图交换相邻两个点的顺序，若路程减少则完成交换，继续下一个交换；若没有改善，则不进行本次交换，尝试下一个交换；若所有的相临交换都试过而不能改善，则算法结束，得到一个局部最优点 模拟退火 (Simulated Annealing) 随机地采用二交换法 当交换后没有使目标函数改善，也可能以玻尔兹曼分布概率被接受，但这种概率是随模拟的温度下降而减少的 发挥了计算机的优点，尽量减少陷入局部极值点 模拟物理机制,37,二交换法举例,初始解：1-2-3-4-5 1-3-2-4-5,1-3-2-4-5 1-3-4-2-5,1-3-4-2-5 1-3-4-5-2 5-3-4-2-1 3-1-

28、4-2-5 ,38,算法复杂度,Prim算法 i=1 n 1 次比较，最多 n 1 次赋值 i=2 2(n 2) 次比较，最多 2(n 2) 次赋值 i=k k(n k) 次比较，最多 k(n k) 次赋值,Dijkstra算法 i=1 n 1 次临时标记，永久标记 n 1 次比较和赋值 i=2 n 2 次临时标记，永久标记 n 2 次比较和赋值 i=k n k 次临时标记，永久标记 n k 次比较和赋值,39,Prim算法的改进,增加一个辅助记录型数组，用以记录当前 V 中各节点到 V 的最小边， minedgei.cost 记录该边的权值， minedgei.vex 记录该边 V 中的顶点

29、。若 minedgei.cost0) and (minedgej.costmi) then begin k:=j; mi:=minedgej.cost end; minedgek.cost:= minedgek.cost; 找到 k，将 k 加入集合 V for j:=2 to n do if (wk,jminedgej.cost) then begin minedgej.cost:=wk,j; minedgej.vex:=k; end; end; 该算法复杂度 约为 5n(n-1) ,40,匹配问题 (Matching Problem),定义：图中一组边的集合，当图中的每个节点最多只与该集合中的一条边相关联，则该边集就成为匹配。 1、两部图的匹配问题 图中的节点可分为两个集合，X, Y，X 与 Y 之间有边相连，但 X 内部和 Y 内部无关联边，称为两部图 运输问题实际上是两部图的最小费用最大流问题 任务分配问题实际上是两部图的最小完全匹配问题 2、非两部图的匹配问题 (1) 最大基数匹配(maximum cardinality matching) (2) 最大权匹配(maximum weight matching) (3) 最小完全匹配(minimu