割点桥双连通分量课件.ppt

上传人(卖家):晟晟文业 文档编号:5014724 上传时间:2023-02-02 格式:PPT 页数:41 大小:913KB
下载 相关 举报
割点桥双连通分量课件.ppt_第1页
第1页 / 共41页
割点桥双连通分量课件.ppt_第2页
第2页 / 共41页
割点桥双连通分量课件.ppt_第3页
第3页 / 共41页
割点桥双连通分量课件.ppt_第4页
第4页 / 共41页
割点桥双连通分量课件.ppt_第5页
第5页 / 共41页
点击查看更多>>
资源描述

1、图论图论1 1江川七桥问题七桥问题七桥问题七桥问题七桥问题七桥问题 图、点、边 G=(V,E)V 顶点集 E 边集图的基本概念图的基本概念 G=(V,E)有向图、无向图 无向图 V&V e=a,b 有向图 VxV e=a,a,b图的基本概念图的基本概念 G=(V,E)度(入度、出度)环 路径 割图的基本概念图的基本概念 G=(V,E)简单图 完全图 二分图 平面图图的基本概念图的基本概念 邻接矩阵图的表示图的表示 邻接表(边表)图的表示图的表示 判定 连通 度数平衡(有向、无向)欧拉环欧拉环 求解 “有边就走”回溯欧拉环欧拉环 其他 欧拉路 混合图欧拉环欧拉环汉密尔顿回路汉密尔顿回路 NP-C

2、omplete 对于顶点个数大于2的图,如果图中任意两点度的和大于或等于顶点总数,那这个图一定是哈密顿图。汉密尔顿回路 vs 欧拉回路汉密尔顿回路汉密尔顿回路 如果一个问题不是多项式时间可解的 1、加强条件,针对特定情况 2、减弱要求,求近似解 3、降低问题规模汉密尔顿回路汉密尔顿回路 O(n!*n)?状态压缩动态规划 要考虑的状态:已经经过哪些点?2n 经过点的顺序?n!n*n n汉密尔顿回路汉密尔顿回路 例:1,0,1,1,03 表示经过了1、3和4,并停在3 状态数:2n*n 转移:n 复杂度:O(2n*n2)POJ 3311 汉密尔顿回路汉密尔顿回路 Floyd 点对间的距离 O(n3

3、)动态规划的思想 Fi,j,kFi,j最短路最短路 Dijkstra 单源最短路径 贪心算法 寻找未处理的最小的点更新其他点 不能有负权边 O(V2)O(VlogV+E)最短路最短路 有效的程序员不应该浪费很多时间用于程序调试,他们应该一开始就不要把故障引入。Bellman-Ford 对每一条边进行松弛操作,重复V次:for each edge(u,v)if dv du+w(u,v)dv=du+w(u,v)允许负权边,可判断负权圈 O(VE)最短路最短路 SPFA Shortest Path Faster Algorithm Bellman-Ford的优化 用一个队列存储被更新的点 期望复杂度

4、:O(kE)最短路最短路 特殊的图 连通性 结构实用 序 层次树树 最小生成树 Prim算法 两个点集(加入生成树和未加入生成树)O(V2)Kruscal算法 按边权顺序从小到大枚举 O(E log E)生成树生成树 次小生成树 在最小生成树上添边 生成环 删边 新的生成树 在最小生成树上求两点路径上最大的边 poj1679生成树生成树 拓扑排序 1、选择入度为0的点v 2、删除v和从v出发的所有边拓扑排序与强连通分量拓扑排序与强连通分量 强连通分量 Tarjan算法 基于对图深度优先搜索的算法 DFN(u):u搜索到的次序编号(时间戳)Low(u):u或者u的子树能够追溯到的最早的搜索栈中的

5、节点的次序号。DFN(u)=Low(u)时,以u为根的搜索子树上所有节点是一个强连通分量。拓扑排序与强连通分量拓扑排序与强连通分量拓扑排序与强连通分量拓扑排序与强连通分量拓扑排序与强连通分量拓扑排序与强连通分量拓扑排序与强连通分量拓扑排序与强连通分量拓扑排序与强连通分量拓扑排序与强连通分量拓扑排序与强连通分量拓扑排序与强连通分量拓扑排序与强连通分量拓扑排序与强连通分量 O(V+E)POJ 2762 割点v:去掉点v后图不连通 桥/割边e:去掉边e后图不连通 双连通分量:1、(边)任意去掉一条边,图仍连通 2、(点)任意去掉一个点,图仍连通割点、桥、双连通分量割点、桥、双连通分量 Tarjan算

6、法求割点 在图的搜索树中,如果u为割点,当且仅当满足下面的条件:1、如果u为树根,那么u必须有多于1棵子树 2、如果u不为树根,那么(u,v)为树枝边,当Lowv=DFNu时。割点、桥、双联通分量割点、桥、双联通分量割点、桥、双联通分量割点、桥、双联通分量 在一个网络中,某些点之间可以接发信息(单向)。问至少增加多少条边可以使从任一点发送的信息可以到达其他所有点?例题例题1 强连通分量 看做一个点 观察入度为0的点和出度为0的点 poj1236 例题例题1 给定一个有向无环图,n个点,m条边(1=n=100000,0=m=1000000),每个点有点权。要求选择一条从某个入度为0的点到某个出度为0的点的路径,使得整个路径上点的权值之和最大。例题例题2 有向无环图 拓扑排序 图DP poj3249例题例题2谢谢!

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 办公、行业 > 各类PPT课件(模板)
版权提示 | 免责声明

1,本文(割点桥双连通分量课件.ppt)为本站会员(晟晟文业)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!


侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|