图与网路分析报告探讨.pptx

图与网路分析报告探讨图与网路分析报告探讨BACD图论图论 Graph Theory哥尼斯堡七桥问题哥尼斯堡七桥问题(Knigsberg Bridge Problem)Leonhard Euler(1707-1783)在在1736年发表第一篇图论年发表第一篇图论方面的论文，奠基了图论中的一些基本定理方面的论文，奠基了图论中的一些基本定理很多问题都可以用点和线来表示，一般点表示实体，很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联线表示实体间的关联26.1 图与网路的基本概念图与网路的基本概念 6.1.1图与网路图与网路节点节点(Vertex)物理实体、事物、概念物理实体、事物、概念一般用一般用 vi 表示表示边边(Edge)节点间的连线，表示有节点间的连线，表示有关系关系一般用一般用 eij 表示表示图图(Graph)节点和边的集合节点和边的集合一般用一般用 G(V,E)表示表示点集点集 V=v1,v2,vn边集边集E=eij 网路网路 (Network)边上具有表示连接强度边上具有表示连接强度的权值，如的权值，如 wij又称又称加权图加权图(Weighted graph)3 6.1.2 无向图与有向图无向图与有向图边都没有方向的图称为无向图，如图边都没有方向的图称为无向图，如图6.1在无向图中在无向图中 eij=eji，或，或(vi,vj)=(vj,vi)当边都有方向时，称为有向图，用当边都有方向时，称为有向图，用G(V,A)表示表示在有向图中，有向边又称为在有向图中，有向边又称为弧弧，用，用 aij表示，表示，i,j 的顺序的顺序是不能颠倒的，图中弧的方向用箭头标识是不能颠倒的，图中弧的方向用箭头标识图中既有边又有弧，称为混合图图中既有边又有弧，称为混合图4 6.1.3 端点，关联边，相邻，次端点，关联边，相邻，次图中可以只有点，而没有边；而有边必有点图中可以只有点，而没有边；而有边必有点若节点若节点vi,vj 之间有一条边之间有一条边 eij，则称，则称 vi,vj 是是 eij 的的端点端点(end vertex)，而，而 eij 是节点是节点 vi,vj 的的关联边关联边(incident edge)同一条边的两个端点称为同一条边的两个端点称为相邻相邻(adjacent)节点节点，具有共，具有共同端点的边称为同端点的边称为相邻边相邻边一条边的两个端点相同，称为一条边的两个端点相同，称为自环自环(self-loop)；具有两；具有两个共同端点的两条边称为个共同端点的两条边称为平行边平行边(parallel edges)既没有自环也没有平行边的图称为既没有自环也没有平行边的图称为简单图简单图(simple graph)在无向图中，与节点相关联边的数目，称为该节点的在无向图中，与节点相关联边的数目，称为该节点的“次次”(degree)，记为记为 d；次数为奇数的点称为；次数为奇数的点称为奇点奇点(odd),次数为偶数的点称为次数为偶数的点称为偶点偶点(even)；图中都是偶点；图中都是偶点的图称为偶图的图称为偶图(even graph)5 6.1.3 端点，关联边，相邻，次端点，关联边，相邻，次有向图中，由节点指向外的弧的数目称为正次数，记为有向图中，由节点指向外的弧的数目称为正次数，记为 d+，指向该节点的弧的数目称为负次数，记为，指向该节点的弧的数目称为负次数，记为 d次数为次数为 0 的点称为的点称为孤立点孤立点(isolated vertex)，次数为，次数为 1 的点称为的点称为悬挂点悬挂点(pendant vertex)定理定理 1：图中奇点的个数总是偶数个：图中奇点的个数总是偶数个 6.1.4 链，圈，路径，回路，欧拉回路链，圈，路径，回路，欧拉回路相邻节点的序列相邻节点的序列 v1 ,v2 ,vn 构成一条构成一条链链(link)，又称为，又称为行走行走(walk)；首尾相连的链称为；首尾相连的链称为圈圈(loop)，或，或闭行走闭行走在无向图中，节点不重复出现的链称为在无向图中，节点不重复出现的链称为路径路径(path)；在；在有向图中，节点不重复出现且链中所有弧的方向一致，有向图中，节点不重复出现且链中所有弧的方向一致，则称为有则称为有向路径向路径(directed path)首尾相连的路径称为首尾相连的路径称为回路回路(circuit)；6 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 graph)，若在平面上可以画出该图而没，若在平面上可以画出该图而没有任何边相交有任何边相交76.2 树树图与最小生成树图与最小生成树一般研究无向图一般研究无向图树图：倒置的树，树图：倒置的树，根根(root)在上，在上，树叶树叶(leaf)在下在下多级辐射制的电信网络、管理的指标体系、家谱、分多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图类学、组织结构等都是典型的树图8 6.2.1 树的定义及其性质树的定义及其性质任两点之间有且只有一条路径的图称为任两点之间有且只有一条路径的图称为树树(tree)，记为，记为T 树的性质树的性质：最少边的连通子图，树中必不存在回路最少边的连通子图，树中必不存在回路任何树必存在次数为任何树必存在次数为 1 的点的点具有具有 n 个节点的树个节点的树 T 的边恰好为的边恰好为 n 1 条，反之，任何有条，反之，任何有n 个节点，个节点，n 1 条边的连通图必是一棵树条边的连通图必是一棵树 6.2.2 图的生成树图的生成树树树 T 是连通图是连通图 G 的的生成树生成树(spanning tree)，若，若 T 是是 G的的子图且包含图子图且包含图 G 的所有的节点；包含图的所有的节点；包含图 G 中部分指定节中部分指定节点的树称为点的树称为 steiner tree每个节点有唯一标号的图称为标记图，标记图的生成树每个节点有唯一标号的图称为标记图，标记图的生成树称为称为标记树标记树(labeled tree)Caylay 定理定理：n(2)个节点，有个节点，有nn 2个不同的个不同的标记树标记树9 6.2.2 图的生成树图的生成树如何找到一棵生成树如何找到一棵生成树深探法深探法(depth first search)：任选一点标记为：任选一点标记为 0 点开始搜点开始搜索，选一条未标记的边走到下一点，该点标记为索，选一条未标记的边走到下一点，该点标记为 1，将，将走过的边标记；假设已标记到走过的边标记；假设已标记到 i 点，总是从最新标记的点，总是从最新标记的点向下搜索，若从点向下搜索，若从 i 点无法向下标记，即与点无法向下标记，即与 i 点相关联的点相关联的边都已标记或相邻节点都已标记，则退回到边都已标记或相邻节点都已标记，则退回到 i 1 点继续点继续搜索，直到所有点都被标记搜索，直到所有点都被标记广探法广探法(breadth first search)：是一种有层级结构的搜索，：是一种有层级结构的搜索，一般得到的是树形图一般得到的是树形图10 6.2.3 最小生成树最小生成树有有n 个乡村，各村间道路的长度是已知的，如何敷设光个乡村，各村间道路的长度是已知的，如何敷设光缆线路使缆线路使 n 个乡村连通且总长度最短个乡村连通且总长度最短显然，这要求在已知边长度的网路图中找最小生成树显然，这要求在已知边长度的网路图中找最小生成树 最小生成树的算法最小生成树的算法：Kruskal 算法：将图中所有边按权值从小到大排列，依次算法：将图中所有边按权值从小到大排列，依次选所剩最小的边加入边集选所剩最小的边加入边集 T，只要不和前面加入的边构，只要不和前面加入的边构成回路，直到成回路，直到 T 中有中有 n 1 条边，则条边，则 T 是最小生成树是最小生成树Kruskal 算法基于下述定理算法基于下述定理定理定理 3 指定图中任一点指定图中任一点vi，如果，如果 vj 是距是距 vi 最近的相邻节点，最近的相邻节点，则关联边则关联边 eij 必在某个最小生成树中。必在某个最小生成树中。推论推论 将网路中的节点划分为两个不相交的集合将网路中的节点划分为两个不相交的集合V1和和V2，V2=V V1，则，则V1和和V2间权值最小的边必定在某个最小生间权值最小的边必定在某个最小生成树中。成树中。11 6.2.3 最小生成树最小生成树最小生成树不一定唯一最小生成树不一定唯一定理定理 3 推论是一个构造性定理，它指示了找最小生成树推论是一个构造性定理，它指示了找最小生成树的有效算法的有效算法Prim 算法：不需要对边权排序，即可以直接在网路图上算法：不需要对边权排序，即可以直接在网路图上操作，也可以在边权矩阵上操作，后者适合计算机运算操作，也可以在边权矩阵上操作，后者适合计算机运算 边权矩阵上的边权矩阵上的 Prim 算法算法：1、根据网路写出边权矩阵，两点间若没有边，则用、根据网路写出边权矩阵，两点间若没有边，则用 表示；表示；2、从、从 v1 开始标记，在第一行打开始标记，在第一行打 ，划去第一列；，划去第一列；3、从所有打、从所有打 的行中找出尚未划掉的最小元素，对该元素画圈，的行中找出尚未划掉的最小元素，对该元素画圈，划掉该元素所在列，与该列数对应的行打划掉该元素所在列，与该列数对应的行打 ；4、若所有列都划掉，则已找到最小生成树、若所有列都划掉，则已找到最小生成树(所有画圈元素所对应所有画圈元素所对应的边的边)；否则，返回第；否则，返回第 3 步。步。该算法中，打该算法中，打 行对应的节点在行对应的节点在 V1中，未划去的列在中，未划去的列在 V2中中12 6.2.3 最小生成树最小生成树Prim算法是多项式算法算法是多项式算法Prim算法可以求最大生成树算法可以求最大生成树网路的边权可以有多种解释，如效率网路的边权可以有多种解释，如效率次数受限的最小生成树次数受限的最小生成树尚无有效算法尚无有效算法最小最小 Steiner 树树尚无有效算法尚无有效算法 136.3 最短路问题最短路问题 6.3.1 狄克斯特拉算法狄克斯特拉算法 (Dijkstra algorithm,1959)计算两节点之间或一个节点到所有节点之间的最短路计算两节点之间或一个节点到所有节点之间的最短路令令 dij 表示表示 vi 到到 vj 的直接距离的直接距离(两点之间有边两点之间有边)，若两点之间，若两点之间没有边，则令没有边，则令 dij=，若，若两点之间是有向边，则两点之间是有向边，则 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步。步。14例例1 1 狄克斯特拉算法狄克斯特拉算法 0 81510121511311315 Dijkstra最短路算法的最短路算法的特点特点和和适应范围适应范围一种隐阶段的动态规划方法一种隐阶段的动态规划方法每次迭代只有一个节点获得永久标记，若有两个或两个以上每次迭代只有一个节点获得永久标记，若有两个或两个以上节点的临时标记同时最小，可任选一个永久标记；总是从一节点的临时标记同时最小，可任选一个永久标记；总是从一个新的永久标记开始新一轮的临时标记，是一种个新的永久标记开始新一轮的临时标记，是一种深探法深探法被框住的永久标记被框住的永久标记 Tj 表示表示 vs 到到 vj 的最短路，因此的最短路，因此 要求要求 dij 0，第，第 k 次迭代得到的永久标记，其最短路中最多有次迭代得到的永久标记，其最短路中最多有 k 条边，条边，因此最多有因此最多有n 1 次迭代次迭代可以应用于可以应用于简单简单有向图和混合图，在临时标记时，所谓相邻有向图和混合图，在临时标记时，所谓相邻必须是箭头指向的节点；若第必须是箭头指向的节点；若第 n 1 次迭代后仍有节点的标记次迭代后仍有节点的标记为为 ，则表明，则表明 vs 到该节点无有向路径到该节点无有向路径如果只求如果只求 vs 到到 vt 的最短路，则当的最短路，则当 vt 得到永久标记算法就结束得到永久标记算法就结束了；但算法复杂度是一样的了；但算法复杂度是一样的应用应用 Dijkstra 算法算法 n 1 次次，可以求所有点间的最短路，可以求所有点间的最短路vs 到所有点的最短路也是一棵生成树，但不是最小生成树到所有点的最短路也是一棵生成树，但不是最小生成树16 6.3.2 Warshall-Floyd算法算法 (1962)Warshall-Floyd算法可以解决有算法可以解决有负权值负权值边边(弧弧)的最短路问题的最短路问题该算法是一种整体算法，一次求出所有点间的最短路该算法是一种整体算法，一次求出所有点间的最短路该算法不允许有该算法不允许有负权值回路负权值回路，但可以发现负权值回路，但可以发现负权值回路该算法基于基本的三角运算该算法基于基本的三角运算定义定义 对给定的点间初始距离矩阵对给定的点间初始距离矩阵dij，令，令dii=，对所有对所有 i。对一对一 个固定点个固定点 j，运算，运算 dik=mindik,dij+djk,对所有对所有 i,k j,称为称为 三角运算。三角运算。(注意，这里允许注意，这里允许 i=k)定理定理 依次对依次对 j=1,2,n 执行三角运算，则执行三角运算，则 dik 最终等于最终等于 i 到到 k 间最短路的长度。间最短路的长度。17 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 i j then for k=1 to n do if k j then begin dik=mindik,dij+djk;if dikdij+djk then eik=j end;若网路中存在负回路，则计算若网路中存在负回路，则计算中，某些中，某些 dii 会小于会小于0，此时应，此时应中断算法中断算法显然，显然，Floyd 算法要进行算法要进行 n(n-1)2 次加法和比较次加法和比较如何回溯找出任两点之间的最如何回溯找出任两点之间的最短路？短路？在在Floyd 算法中设一伴随矩阵算法中设一伴随矩阵E=eik，eik 记录了记录了 i 到到 k 最短路最短路中最后一个中间节点中最后一个中间节点18小结小结最短路有广泛的应用最短路有广泛的应用(6.3.4节节 市话局扩容方案市话局扩容方案)最短路的多种形式：无向图，有向图无循环圈，有向最短路的多种形式：无向图，有向图无循环圈，有向图，混合图，无负边权，有负边权，有负回路，图，混合图，无负边权，有负边权，有负回路，k-最最短路等短路等当存在负权值边时，当存在负权值边时，Floyd算法比算法比Dijkstra算法效率高，算法效率高，且程序极简单。但且程序极简单。但Dijkstra算法灵活算法灵活若图是前向的，则若图是前向的，则Dijkstra算法也可以求两点间最长路算法也可以求两点间最长路一般情况下，两点间最长路是一般情况下，两点间最长路是 NP-complete，但最短，但最短路是路是 P算法算法两点间两点间k-最短路：分为边不相交的和边相交的最短路：分为边不相交的和边相交的 求边求边不相交的不相交的k-最短路非常容易：先求最短路，将该最最短路非常容易：先求最短路，将该最短路中的边从网路删去，再用短路中的边从网路删去，再用Dijkstra算法可求次最短算法可求次最短路，以此类推路，以此类推196.4 网路的最大流和最小截网路的最大流和最小截 6.4.1 网路的最大流的概念网路的最大流的概念网路流一般在有向图上讨论网路流一般在有向图上讨论定义网路上支路的定义网路上支路的容量容量为其最大通过能力，记为为其最大通过能力，记为 cij，支路上的实际支路上的实际流量流量记为记为 fij 图中规定一个发点图中规定一个发点s s，一个收点，一个收点t t节点没有容量限制，流在节点不会存储节点没有容量限制，流在节点不会存储容量限制条件容量限制条件：0 fij cij 平衡条件平衡条件：满足上述条件的网路流称为满足上述条件的网路流称为可行流可行流，总存在，总存在最大可行流最大可行流 当支路上当支路上 fij=cij ，称为，称为饱和弧饱和弧 最大流问题也是一个线性规划问题最大流问题也是一个线性规划问题viA(vi)B(vi)20 6.4.2 截集与截集容量截集与截集容量定义定义：把网路分割为两个成分的弧的最小集合，其中一：把网路分割为两个成分的弧的最小集合，其中一 个成分包含个成分包含 s 点，另一个包含点，另一个包含 t 点点。一般包含一般包含 s 点的成分中的节点集合用点的成分中的节点集合用V表示，包含表示，包含 t 点点的成分中的节点集合用的成分中的节点集合用V表示表示截集容量截集容量是指截集中正向弧的容量之和是指截集中正向弧的容量之和 福特福特-富克森定理富克森定理：网路的最大流等于最小截集容量：网路的最大流等于最小截集容量21 6.4.3 确定网路最大流的标号法确定网路最大流的标号法从任一个初始可行流出发，如从任一个初始可行流出发，如 0 流流基本算法：找一条从基本算法：找一条从 s 到到 t 点的点的增广链增广链(augmenting path)若在当前可行流下找不到增广链，则已得到最大流若在当前可行流下找不到增广链，则已得到最大流增广链中与增广链中与 s 到到 t 方向一致的弧称为方向一致的弧称为前向弧前向弧，反之，反之后向弧后向弧 增广过程：前向弧增广过程：前向弧 f ij=fij+q q,后向弧后向弧 f ij=fij q q 增广后仍是可行流增广后仍是可行流 22 最大流最小截的标号法步骤最大流最小截的标号法步骤第一步：标号过程，找一条增广链第一步：标号过程，找一条增广链1、给源点给源点 s 标号标号s+,q q(s)=，表示从，表示从 s 点有无限流出潜力点有无限流出潜力2、找出与已标号节点找出与已标号节点 i 相邻的所有未标号节点相邻的所有未标号节点 j，若，若(1)(i,j)是前向弧且饱和，则节点是前向弧且饱和，则节点 j 不标号；不标号；(2)(i,j)是前向弧且未饱和，则节点是前向弧且未饱和，则节点 j 标号为标号为i+,q q(j)，表示从节点，表示从节点 i 正向正向流出，可增广流出，可增广 q q(j)=minq q(i),cij fij；(3)(j,i)是后向弧，若是后向弧，若 fji=0，则节点，则节点 j 不标号；不标号；(4)(j,i)是后向弧，若是后向弧，若 fji0，则节点，则节点 j 标号为标号为i,q q(j)，表示从节点，表示从节点 j 流向流向 i，可增广可增广 q q(j)=minq q(i),fji；3、重复步骤重复步骤 2，可能出现两种情况：，可能出现两种情况：(1)节点节点 t 尚未标号，但无法继续标记，说明网路中已不存在增广链，尚未标号，但无法继续标记，说明网路中已不存在增广链，当前流当前流 v(f)就是最大流；所有获标号的节点在就是最大流；所有获标号的节点在 V 中，未获标号节点中，未获标号节点在在 V 中，中，V 与与 V 间的弧即为最小截集；算法结束间的弧即为最小截集；算法结束(2)节点节点 t 获得标号，找到一条增广链，由节点获得标号，找到一条增广链，由节点 t 标号回溯可找出该增标号回溯可找出该增广链；到第二步广链；到第二步23 最大流最小截的标号法步骤最大流最小截的标号法步骤第二步：增广过程第二步：增广过程1、对、对增广链中的前向弧，令增广链中的前向弧，令 f=f+q q(t)，q q(t)为节点为节点 t 的标记的标记值值2、对对增广链中的后向弧，令增广链中的后向弧，令 f=f q q(t)3、非增广链上的所有支路流量保持不变、非增广链上的所有支路流量保持不变第三步：抹除图上所有标号，回到第一步第三步：抹除图上所有标号，回到第一步以上算法是按广探法描述的，但在实际图上作业时，按深以上算法是按广探法描述的，但在实际图上作业时，按深探法进行更快捷探法进行更快捷一次只找一条增广链，增广一次换一张图一次只找一条增广链，增广一次换一张图最后一次用广探法，以便找出最小截集最后一次用广探法，以便找出最小截集24最大流最小截集的标号法举例最大流最小截集的标号法举例(s+,)(s+,6)(2,6)(3+,1)(4+,1)(s+,)(s+,5)(2+,2)(5,2)(4+,2)25最大流最小截集的标号法举例最大流最小截集的标号法举例(s+,)(s+,3)(2,3)最小截集最小截集26 最大流标号法的复杂度讨论最大流标号法的复杂度讨论找一条增广链的计算量是容易估计的，不会超过找一条增广链的计算量是容易估计的，不会超过O(n2)但是最多迭代多少次但是最多迭代多少次(即增广的次数即增广的次数)就很难估计，在最坏就很难估计，在最坏情况下，与边的容量有关；如上图：先增广情况下，与边的容量有关；如上图：先增广 s u v t,然后增广然后增广 s v u t，每次只能增广，每次只能增广 1 个单位，故要增个单位，故要增广广4000次才能结束次才能结束克服这种缺点的经验方法：克服这种缺点的经验方法：尽量先用段数少的增广链尽量先用段数少的增广链尽量不重复前面出现过的增广链尽量不重复前面出现过的增广链27 6.4.4 多端网路问题多端网路问题28 6.4.5 最小费用最大流最小费用最大流双权网路双权网路：每条弧不但有容量，还有单位流量的通过费用：每条弧不但有容量，还有单位流量的通过费用两种解法：一种基于最小费用路径算法；一种基于可行弧集两种解法：一种基于最小费用路径算法；一种基于可行弧集的最大流算法的最大流算法基于最小费用路径算法基于最小费用路径算法：总是在当前找到的最小费用的路径：总是在当前找到的最小费用的路径上增广流；缺点是每次增广后要改变弧的费用，且出现负权上增广流；缺点是每次增广后要改变弧的费用，且出现负权值费用的弧值费用的弧基于可行弧集的最大流算法基于可行弧集的最大流算法：从：从 0 费用弧集开始应用最大流费用弧集开始应用最大流算法，然后根据计算信息提高费用的限界算法，然后根据计算信息提高费用的限界P，使可行弧集增，使可行弧集增大，再应用最大流算法，直至所有弧都进入可行弧集。这种大，再应用最大流算法，直至所有弧都进入可行弧集。这种算法是一种主算法是一种主-对偶规划的解法。使用这种方法的还有运输对偶规划的解法。使用这种方法的还有运输问题、匹配问题问题、匹配问题29 6.4.5 以最短路为基础汇总网路上的流以最短路为基础汇总网路上的流在电路网中每两点之间都有中继电路群需求，但并不是任在电路网中每两点之间都有中继电路群需求，但并不是任两点都有物理传输链路两点都有物理传输链路根据两点间最短传输路径将该两点间的电路需求量加载到根据两点间最短传输路径将该两点间的电路需求量加载到这条传输路径上去：设这条传输路径上去：设 a25=10 是节点是节点2 和和 5 之间的电路需求，之间的电路需求，节点节点2 和和 5 之间的最短传输路径为之间的最短传输路径为 2 1 3 5，则加载过，则加载过程为程为:T21=T21+10,T13=T13+10,T35=T35+10；Tij 是传输链路是传输链路 i j 上加载的电路数；当所有点间电路都加载完则算法结上加载的电路数；当所有点间电路都加载完则算法结束束306.5 欧拉回路和中国邮递员问题欧拉回路和中国邮递员问题中国邮递员问题中国邮递员问题(Chinese Postman Problem,CPP)是由我国是由我国管梅谷教授于管梅谷教授于1962年首先提出并发表的年首先提出并发表的问题是从邮局出发，走遍邮区的所有街道至少一次再回到问题是从邮局出发，走遍邮区的所有街道至少一次再回到邮局，走什么路由才能使总的路程最短？邮局，走什么路由才能使总的路程最短？如果街区图是一个偶图，根据定理如果街区图是一个偶图，根据定理 3，一定有欧拉回路，一定有欧拉回路，CPP 问题也就迎刃而解了问题也就迎刃而解了若街区图不是偶图，则必然有一些街道要被重复走过才能若街区图不是偶图，则必然有一些街道要被重复走过才能回到原出发点回到原出发点显然要在奇次点间加重复边显然要在奇次点间加重复边如何使所加的边长度最少如何使所加的边长度最少归结为求奇次点间的最小归结为求奇次点间的最小 匹配匹配(minimum weighted match)由由Edmons 给出给出 多项式算法多项式算法(1965)31 解中国邮递员问题的步骤解中国邮递员问题的步骤0、将图中的所有悬挂点依次摘去、将图中的所有悬挂点依次摘去1、求所有奇次点间的最短距离和最短路径、求所有奇次点间的最短距离和最短路径2、根据奇次点间的最短距离求最小完全匹配、根据奇次点间的最短距离求最小完全匹配3、根据最小完全匹配和最短路径添加重复边、根据最小完全匹配和最短路径添加重复边4、将悬挂点逐一恢复，并加重复边、将悬挂点逐一恢复，并加重复边5、根据得到的偶图，给出欧拉回路的若干种走法、根据得到的偶图，给出欧拉回路的若干种走法32 解中国邮递员问题的步骤解中国邮递员问题的步骤336.6 哈密尔顿回路及旅行推销员问题哈密尔顿回路及旅行推销员问题 6.6.1 哈密尔顿回路哈密尔顿回路(Hamiltonian circuit)连通图连通图G(V,E)中的回路称为中的回路称为哈密尔顿回路哈密尔顿回路，若该回路包括图中，若该回路包括图中所有的点。显然哈密尔顿回路有且只有所有的点。显然哈密尔顿回路有且只有 n 条边，若条边，若|V|=n连通图具有哈密尔顿回路的充分必要条件是什么？这个问题是连通图具有哈密尔顿回路的充分必要条件是什么？这个问题是由爱尔兰数学家由爱尔兰数学家哈密尔顿哈密尔顿1859年年提出的，但至今仍未解决提出的，但至今仍未解决欧拉回路是对边进行访问的问题，哈密尔顿回路是对点进行访欧拉回路是对边进行访问的问题，哈密尔顿回路是对点进行访问的问题问的问题搜索哈密尔顿回路的难度是搜索哈密尔顿回路的难度是 NP-complete任两点间都有边的图称为任两点间都有边的图称为完全图完全图(或全连接图或全连接图)完全图中有多少个不同的哈密尔顿回路？完全图中有多少个不同的哈密尔顿回路？完全图中有多少个边不相交的哈密尔顿回路？完全图中有多少个边不相交的哈密尔顿回路？最小哈密尔顿回路问题最小哈密尔顿回路问题(NP-complete)哈密尔顿路径哈密尔顿路径：包含图中所有点的路径：包含图中所有点的路径为什么说找两点间的最长路是非常困难的问题？为什么说找两点间的最长路是非常困难的问题？(n 1)!/2(n 1)/234 6.6.2 旅行推销员问题旅行推销员问题(Traveling Salesman Problem)旅行推销员问题旅行推销员问题(TSP)：设：设v1,v2,.,vn 为为 n 个已知城市，城个已知城市，城市之间的旅程也是已知的，要求推销员从市之间的旅程也是已知的，要求推销员从 v1出发，走遍所有出发，走遍所有城市一次且仅一次又回到出发点，并使总旅程最短城市一次且仅一次又回到出发点，并使总旅程最短这种不允许点重复的旅行推销员问题就是最小哈密尔顿回路这种不允许点重复的旅行推销员问题就是最小哈密尔顿回路问题问题一般旅行推销员问题一般旅行推销员问题(GTSP)：允许点重复的：允许点重复的TSP当网路边权满足三角不等式时，一般旅行推销员问题就等价当网路边权满足三角不等式时，一般旅行推销员问题就等价于最小哈密尔顿回路问题于最小哈密尔顿回路问题当网路边权不满足三角不等式时，只要用两点间最短路的距当网路边权不满足三角不等式时，只要用两点间最短路的距离代替原来的边权，就可以满足三角不等式，在此基础上求离代替原来的边权，就可以满足三角不等式，在此基础上求最小哈密尔顿回路最小哈密尔顿回路 典型的应用典型的应用：乡邮员的投递路线乡邮员的投递路线邮递员开邮箱取信的路线问题邮递员开邮箱取信的路线问题邮车到各支局的转趟问题邮车到各支局的转趟问题35 TSP 的启发式算法的启发式算法(Heuristic algorithm)穷举法穷举法：指数算法：指数算法分支定界法分支定界法：隐枚举法：隐枚举法二交换法二交换法(two-option,Lins algorithm)哈密尔顿回路可以用点的序列表示哈密尔顿回路可以用点的序列表示从任一个哈密尔顿回路从任一个哈密尔顿回路(即任何一个序列即任何一个序列)出发出发按照一定顺序试图交换相邻两个点的顺序，若路程减少则完按照一定顺序试图交换相邻两个点的顺序，若路程减少则完成交换，继续下一个交换；若没有改善，则不进行本次交换，成交换，继续下一个交换；若没有改善，则不进行本次交换，尝试下一个交换；若所有的相临交换都试过而不能改善，则尝试下一个交换；若所有的相临交换都试过而不能改善，则算法结束，得到一个局部最优点算法结束，得到一个局部最优点模拟退火模拟退火(Simulated Annealing)随机地采用二交换法随机地采用二交换法当交换后没有使目标函数改善，也可能以玻尔兹曼分布概率当交换后没有使目标函数改善，也可能以玻尔兹曼分布概率被接受，但这种概率是随模拟的温度下降而减少的被接受，但这种概率是随模拟的温度下降而减少的发挥了计算机的优点，尽量减少陷入局部极值点发挥了计算机的优点，尽量减少陷入局部极值点模拟物理机制模拟物理机制36 二交换法举例二交换法举例初始解：初始解：1-2-3-4-5 1-3-2-4-51-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-4-2-5 37 算法复杂度算法复杂度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 次比较和赋值次比较和赋值38 Prim算法的改进算法的改进增加一个辅助记录型数组，用以记录当前增加一个辅助记录型数组，用以记录当前 V 中各节点到中各节点到 V 的最小边，的最小边，minedgei.cost 记录该边的权值，记录该边的权值，minedgei.vex 记录该边记录该边 V 中的中的顶点。若顶点。若 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)39 匹配问题匹配问题(Matching Problem)定义定义：图中一组边的集合，当图中的每个节点最多只与：图中一组边的集合，当图中的每个节点最多只与该集合中的一条边相关联，则该边集就成为该集合中的一条边相关联，则该边集就成为匹配匹配。1、两部图两部图的匹配问题的匹配问题图中的节点可分为两个集合，图中的节点可分为两个集合，X,Y，X 与与 Y 之间有边相连，之间有边相连，但但 X 内部和内部和 Y 内部无关联边，称为两部图内部无关联边，称为两部图运输问题实际上是两部图的最小费用最大流问题运输问题实际上是两部图的最小费用最大流问题任务分配问题实际上是两部图的最小完全匹配问题任务分配问题实际上是两部图的最小完全匹配问题2、非非两部图两部图的匹配问题的匹配问题(1)最大基数匹配最大基数匹配(maximum cardinality matching)(2)最大权匹配最大权匹配(maximum weight matching)(3)最小完全匹配最小完全匹配(minimum weight perfect matching)(4)最优分数匹配最优分数匹配(optimal fractional matching)40 任务分配问题、匹配问题和任务分配问题、匹配问题和TSP的关系的关系三个问题都有一个三个问题都有一个 n n 正权值的边权矩阵正权值的边权矩阵三个问题的解都可以用代数置换三个问题的解都可以用代数置换(permutation)表示表示i1,i2,i3,i4,i5 是是 1,2,3,4,5 的任一排列，表示元素位置的任一排列，表示元素位置的交换的交换轮换，全轮换，对换轮换，全轮换，对换TSP的解必须是一个全轮换的解必须是一个全轮换任务分配问题的解可以是任一个置换任务分配问题的解可以是任一个置换匹配的解必须是匹配的解必须是 n/2 个对换个对换任务分配问题是匹配问题的松弛问题任务分配问题是匹配问题的松弛问题41 6.7 选址问题选址问题使所选地址到最远的服务对象距离尽可能小使所选地址到最远的服务对象距离尽可能小 中心点中心点使所选地址到各服务对象的总距离最小使所选地址到各服务对象的总距离最小中位点中位点有时间限制的多用中心点，如乡邮局有时间限制的多用中心点，如乡邮局总资源约束的多用中位点，如电话交换局总资源约束的多用中位点，如电话交换局 6.7.1 各点之间的距离各点之间的距离节点到节点间的最短距离，称为节点节点到节点间的最短距离，称为节点节点距离节点距离边上某点到节点的最短距离，称为点边上某点到节点的最短距离，称为点节点距离节点距离节点到某边上最远一点的距离，称为节点节点到某边上最远一点的距离，称为节点边距离边距离边上一点到另一边上最远点的距离，称为点边上一点到另一边上最远点的距离，称为点边距离边距离421、边上某点到节点的最短距离边上某点到节点的最短距离dij 代表代表 vi 与与 vj 间的最短距离，间的最短距离，ars 代表边代表边(r,s)的边长，的边长，令令 h 为边为边(r,s)上一点的上一点的百分位百分位，0 h 1边上对应边上对应 h 的一点到的一点到 vj 的最短距离为的最短距离为 dh(r,s),j=minh ars+drj,(1 h)ars+dsj2、节点到某边