最小路径覆盖在一个 N*N 的有向图中, 路径覆盖就是在图中找一些路经, 使之覆盖了图中的所有顶点, 且任何一个顶点有且只有一条路径与之关联 ( 如果把这些路径中的每条路径从它的起始点走到它的终点, 那么恰好可以经过图中的每个顶点一次且仅一次 ); 如果不考虑图中存在回路, 那么每条路径就是一个弱

Size: px

Start display at page:

Download "最小路径覆盖在一个 N*N 的有向图中, 路径覆盖就是在图中找一些路经, 使之覆盖了图中的所有顶点, 且任何一个顶点有且只有一条路径与之关联 ( 如果把这些路径中的每条路径从它的起始点走到它的终点, 那么恰好可以经过图中的每个顶点一次且仅一次 ); 如果不考虑图中存在回路, 那么每条路径就是一个弱"

颗植常
5 years ago
Views:

1 图论路晓娇

2 最小路径覆盖在一个 N*N 的有向图中, 路径覆盖就是在图中找一些路经, 使之覆盖了图中的所有顶点, 且任何一个顶点有且只有一条路径与之关联 ( 如果把这些路径中的每条路径从它的起始点走到它的终点, 那么恰好可以经过图中的每个顶点一次且仅一次 ); 如果不考虑图中存在回路, 那么每条路径就是一个弱连通子集由上面可以得出 : 1. 一个单独的顶点是一条路径 ; 2. 如果存在一路径 p1,p2,...pk, 其中 p1 为起点,pk 为终点, 那么在覆盖图中, 顶点 p1,p2,...pk 不再与其它的顶点之间存在有向边最小路径覆盖就是找出最小的路径条数, 使之成为 G 的一个路径覆盖路径覆盖与二分图匹配的关系 : 最小路径覆盖 = G - 最大匹配数

3 其中最大匹配数的求法是把 G 中的每个顶点 pi 分成两个顶点 pi' 与 pi", 如果在 p 中存在一条 pi 到 pj 的边, 那么在二分图 G' 中就有一条连接 pi' 与 pj" 的无向边 ; 这里 pi' 就是 p 中 pi 的出边,pj" 就是 p 中 pj 的一条入边 ; 对于公式 : 最小路径覆盖 = G - 最大匹配数 ; 可以这么来理解 ; 如果匹配数为零, 那么 G 中不存在有向边, 于是显然有 : 最小路径覆盖 = G - 最大匹配数 = G -0= G ; 即 G 的最小路径覆盖数为 G ; G' 中不在于匹配边时, 路径覆盖数为 G ; 如果在 P' 中增加一条匹配边 pi' >pj", 那么在图 P 的路径覆盖中就存在一条由 pi 连接 pj 的边, 也就是说 pi 与 pj 在一条路径上, 于是路径覆盖数就可以减少一个 ;

4 如此继续增加匹配边, 每增加一条, 路径覆盖数就减少一条 ; 直到匹配边不能继续增加时, 路径覆盖数也不能再减少了, 此时就有了前面的公式 ; 但是这里只是说明了每条匹配边对应于路径覆盖中的一条路径上的一条连接两个点之间的有向边 ; 下面来说明一个路径覆盖中的每条连接两个顶点之间的有向边对应于一条匹配边与前面类似, 对于路径覆盖中的每条连接两个顶点之间的每条有向边 pi >pj, 我们可以在匹配图中对应做一条连接 pi' 与 pj" 的边, 显然这样做出来图的是一个匹配图 ( 这一点用反证法很容易证明, 如果得到的图不是一个匹配图, 那么这个图中必定存在这样两条边 pi' pj" 及 pi' -pk",(j!=k), 那么在路径覆盖图中就存在了两条边 pi >pj, pi >pk, 那边从 pi 出发的路径就不止一条了, 这与路径覆盖图是矛盾的 ; 还有另外一种情况就是存在 pi' pj",pk' pj", 这种情况也类似可证 ) 至此, 就说明了匹配边与路径覆盖图中连接两顶点之间边的一一对应关系, 那么也就说明了前面的公式成立!

5 匈牙利算法的原理为 : 从当前匹配 ( 如果没有匹配, 则初始匹配为 0) 出发, 检查每一个未盖点, 然后从它出发寻找可增广路, 找到可增广路, 则沿着这条可增广路进行扩充, 直到不存在可增广路为止

6 算法模板 #include <iostream> #include <math.h> using namespace std; #define MAX 502 int map[max][max];//map[i][j] 表示 i 指向 j 的有向边 int n,k; int mk[max]; // 从 X 集合中的顶点 u 出发用深度优先的策略寻找增广路 //( 这种增广路只能使当前的匹配数增加 1) int nx,ny; //X 和 Y 集合中顶点的个数 int cx[max],cy[max]; //cx[i] 表示最终求得的最大匹配中与 Xi 匹配的 Y 顶点, cy[i] 同理

7 int path(int u) for(int v=1; v<=ny; v++) // 考虑所有 Yi 顶点 v if(map[u][v]&&!mk[v]) mk[v]=1; // 如果 v 没有匹配, 或者如果 v 已经匹配了, // 但从 y[v] 出发可以找到一条增广路 if(cy[v]==-1 path(cy[v])) cx[u] = v; // 把 v 匹配给 u cy[v] = u; // 把 u 匹配给 v return 1; // 找到可增广路 return 0 ; // 如果不存在从 u 出发的增广路

8 int MaxMatch() // 求二部图最大匹配的匈牙利算法 int res=0; memset(cx,0xff,sizeof(cx)); // 从 0 匹配开始增广 memset(cy,0xff,sizeof(cy)); for(int i=1; i<=nx; i++) if(cx[i]==-1) // 从每个未盖点出发进行寻找增广路 memset(mk,0,sizeof(mk)); res+=path(i); // 每找到一条增广路, 可使得匹配数加 1 return res;

9 int main() int i,j; int a,b; while(cin>>n>>k) nx=n;ny=n; memset(map,0,sizeof(map)); for(i=0;i<k;i++) cin>>a>>b; map[a][b]=1; int max=maxmatch(); cout<<max<<endl; return 0;

10 图论中的最短路问题路的定义设为无向标定图, 中顶点与边的交替序列称为到的通路, 其中, 为的端点, 分别称为始点与终点, 中的边的条数称为它的长度, 若又有, 则称为回路若的所有边各异, 则称为简单通路若又有, 则称为简单回路, 若所有的顶点 ( 除与可能相同外 ) 各异, 所有的边也各异, 则称为初级通路或路径, 若又有, 则为初级回路或圈, 将长度为奇数的圈成为奇圈, 长度为偶数的圈为偶圈

11 最短路问题是对任意给定的一个赋权图, 及中两个指点的顶点与, 求出其最短路径易见只要考虑简单连通图的情形就够了这里我们假设每边的权都是大于 0 的实数因为当一条边的权为 0 时我们可以把和合并成一个顶点又, 我们约定边当且仅当

12 Floyd 算法 Floyd 算法的基本思想 : 可以将问题分解, 先找出最短的距离, 然后在考虑如何找出对应的行进路线如何找出最短路径呢, 这里还是用到动态规划的知识, 对于任何一个地点而言,i 到 j 的最短距离不外乎存在经过 i 与 j 之间的 k 和不经过 k 两种可能, 所以可以令 k=1,2,3,...,n(n 是地点的数目 ), 在检查 d(ij) 与 d(ik)+d(kj) 的值 ; 在此 d(ik) 与 d(kj) 分别是目前为止所知道的 i 到 k 与 k 到 j 的最短距离, 因此 d(ik)+d(kj) 就是 i 到 j 经过 k 的最短距离所以, 若有 d(ij)>d(ik)+d(kj), 就表示从 i 出发经过 k 再到 j 的距离要比原来的 i 到 j 距离短, 自然把 i 到 j 的 d(ij) 重写为 d(ik)+d(kj), 每当一个 k 查完了,d(ij) 就是目前的 i 到 j 的最短距离重复这一过程, 最后当查完所有的 k 时,d(ij) 里面存放的就是 i 到 j 之间的最短距离了

13 Floyd 算法的基本步骤 : 定义 n n 的方阵序列 D-1, D0, Dn-1, 初始化 : D-1=C D-1[i][j]= 边 <i,j> 的长度, 表示初始的从 i 到 j 的最短路径长度, 即它是从 i 到 j 的中间不经过其他中间点的最短路径迭代 : 设 Dk-1 已求出, 如何得到 Dk(0 k n-1) Dk-1[i][j] 表示从 i 到 j 的中间点不大于 k-1 的最短路径 p: i j, 考虑将顶点 k 加入路径 p 得到顶点序列 q:i k j, 若 q 不是路径, 则当前的最短路径仍是上一步结果 : Dk[i][j]= Dk-1[i][j]; 否则若 q 的长度小于 p 的长度, 则用 q 取代 p 作为从 i 到 j 的最短路径因为 q 的两条子路径 i k 和 k j 皆是中间点不大于 k-1 的最短路径, 所以从 i 到 j 中间点不大于 k 的最短路径长度为 : Dk[i][j]=min Dk-1[i][j], Dk-1[i][k] +Dk-1[k][j]

14 For i 1to n do For j 1to n do dist(i,j) = weight(i,j) For k 1to n do// k 为媒介节点一定要先枚举媒介节点 For i 1to n do For j 1to n do if(dist(i,k) + dist(k,j) < dist(i,j))then// 是否是更短的路径? dist(i,j) = dist(i,k) + dist(k,j) 这个算法的效率是 O(V^3) 它需要邻接矩阵来储存图

15 设计公共汽车线路现有一张城市地图, 图中的顶点为城市, 有向边代表两个城市间的连通关系, 边上的权即为距离现在的问题是, 为每一对可达的城市间设计一条公共汽车线路, 要求线路的长度在所有可能的方案里是最短的输入 : 市数,1 n 20) e ( 有向边数 1 e 210) 以下 e 行, 每行为边 (i,j) 和该边的距离 wij(1 i,j n) 输出 : k 行, 每行为一条公共汽车线路

16 计算每一对顶点间最短路径的方法如下 : 首先枚举路径上的每一个中间顶点 k(1 k n); 然后枚举每一个顶点对 ( 顶点 i 和顶点 j,1 i,j n) 如果 i 顶点和 j 顶点间有一条途径顶点 k 的路径, 且该路径长度在目前 i 顶点和 j 顶点间的所有条途径中最短, 则该方案记入 adj[i,j] 和 path[i,j] adj 矩阵的每一个元素初始化为 ; for i 1 to n do 初始时 adj 为有向图的相邻矩阵,path 存储边信息 for j 1 to n do if wij<>0 then begin adj[i,j] wij;path[i,j] j;endthen else path[i,j] 0; for k 1 to n do 枚举每一个中间顶点 for i 1 to n do 枚举每一个顶点对 for j 1 to n do if adj[i,k]+adj[k,j]<adj[i,j] 记下 then begin adj[i,j] adj[i,k]+adj[k,j]; path[i,j] path[k,j]; end,then 若 vi 经由 vk 至 vj 的路径目前最优, 则

17 Procedure print(i,j); begin if i=j then 输出 i else if if path[i,j]=0 then 输出结点 i 与结点 j 之间不存在通路 else begin print (i,path[i,j]); 递归 i 顶点至 j 顶点的前趋顶点间的最短路径输出 j; end;else end;print

18 距离矩阵 w 初始化为 0; 输入城市地图信息 ( 顶点数边数和距离矩阵 w); 计算每一对顶点间最短路径的矩阵 path; for i 1 to n do 枚举每一个顶点对 for j 1 to n do if path[i,j]<>0 若顶点 i 可达顶点 j, 则输出最短路径方案 then begin print(i,j);writeln;end; then

中油海101船-锚缆冲洗方案 doc

中油海101船-锚缆冲洗方案 doc 最短路径的 Dijkstra 算法 The Dijkstra Algorithm eryar@163.com 摘要 : 本文用 C 实现了图的最短路径 Dijkstra 算法, 并将自己理解该算法的方式与大家分享下, 若有错误之处, 欢迎指正关键字 : 图最短路径 Graph Dijkstra 一引言 Introduction 对图 G 中的每一条边 e 都赋以一个实数 w(e), 则 G