欢迎来到天天文库!上传客服QQ1290478887点击这里,给天天文库发消息,QQ:1290478887 | 帮助中心 分享价值,快乐你我!
天天文库
全部分类
  • 学术论文 >
    毕业论文 毕业设计 临时分类
    学术论文
    毕业论文 毕业设计 临时分类 土木工程毕业设计 asp毕业设计 安卓毕业设计 php毕业设计 文献综述 其他论文 外文翻译 Java毕业设计 asp.net论文 英语论文 机械毕业设计 船舶工程毕业论文 法学专业毕业论文 工商管理毕业论文 汉语言文学毕业论文 行政管理毕业论文 护理学毕业论文 化学专业毕业论文 会计学毕业论文 计算机论文 教育学论文 金融管理论文 景观设计毕业论文 旅游管理毕业论文 文秘秘书毕业论文 人力资源管理毕业论 期刊论文 数学专业毕业论文 心理学毕业论文 平面艺术设计论文 开题报告 音乐专业毕业论文 市场营销论文 装修毕业论文
  • 应用文档 >
    商业计划 设计方案 施工方案
    应用文档
    商业计划 设计方案 施工方案 事迹材料 使用与维护手册 工作思想汇报 表格清单 应急预案 调研报告 策划书 项目建议书 技术措施与指南 可行性研究报告 分析报告 演讲稿 自查报告 党校课件 党校讲课稿 合同协议范本 ppt模板 工作总结 工作计划 工作报告 讲话稿 心得体会 活动方案 规章制度 读后感 汇报材料 其他办公文档
  • 行业资料 >
    专业技术 解决措施 指导说明书
    行业资料
    专业技术 解决措施 指导说明书 组织施工设计 技术规范 国家标准 行业标准 经营营销
  • 教育资源 >
    课后答案 笔记讲义 主题班会
    教育资源
    课后答案 笔记讲义 主题班会 医学课件 PDF书籍 商业培训 优质公开课课件 考试资料 教学课件 职业培训课件 大学学习资料 高中学习资料 初中学习资料 小学学习资料 其他学习资料 练习与试题 英语资料 课程设计 临时分类
  • 其他资料 >
    其他文档 免费文档
    其他资料
    其他文档 免费文档
  • 首页 天天文库 > 资源分类 > DOC文档下载
     

    图结构和基本问题

    • 资源ID:18800147       资源大小:88.50KB        全文页数:52页
    • 资源格式: DOC        下载权限:游客/注册会员    下载费用:20积分 【人民币20元】
    游客快捷下载 游客一键下载
    会员登录下载
    下载资源需要20积分 【人民币20元】

    邮箱/QQ:
    温馨提示:
    支付成功后,系统会根据您填写的邮箱或者QQ号作为您下次登录的用户名和密码(如填写的是QQ,那登陆用户名和密码就是QQ号),方便下次登录下载和查询订单;
    特别说明:
    付款后即可正常下载,下载内容为可编辑文档格式,推荐使用支付宝;
    支付方式: 支付宝    微信支付   
    验证码:   换一换

     
    1、本站资源不支持迅雷下载,请使用浏览器直接下载(不支持QQ浏览器);
    2、文档下载后都不会有天天文库的水印,预览文档经过压缩,下载后原文更清晰;
    3、所有的PPT和DOC文档都被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;下载前须认真查看,确认无误后再购买;
    4、所有文档都是可以预览的,天天文库作为内容存储提供商,无法对各卖家所售文档的真实性、完整性、准确性以及专业性等问题提供保证;
    5、文档的总页数、文档格式和文档大小以系统显示为准(不同办公软件显示的页数偶尔有区别),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据;
    6、如果您还有什么不清楚的,可以点击右侧栏的客服对话;
    下载须知 | 常见问题汇总

    图结构和基本问题

    图结构和基本问题图结构和基本问题 ----------------------- 页面 1----------------------- 图结构和基本问题 刘汝佳 ----------------------- 页面 2----------------------- 目录 一、预备知识 二、图的遍历及其应用 三、有向图强连通分量和传递闭包 四、无向图割顶、桥和双连通分量 五、强连通化和支配点 六、特殊图类介绍 七、经典问题列表 ----------------------- 页面 3----------------------- 1 预备知识 1.1 图的基本概念 1.2 路径、圈和连通性 1.3 生成树、完全图和补图 1.4 特殊图类 1.5 有向图和带权图 1.6 图的 ADT 1.7 邻接矩阵 1.8 邻接表和前向星 ----------------------- 页面 4----------------------- 图的基本概念 * 图 GV, E, 即顶点集和边集组成的二元组, 它 描述了顶点集的相互关系 * 本文只考虑简单图 – 边的两端不是同一个顶点没有自环 self-loops – 一对结点最多被一条边连接没有重边 parallel edges * 注意 自环和重边在有些情况见后很有用 * 图的数学表示 – 点 用整数 0, 1, 2, , V-1 表示 – 边 用无序数对u, v表示, 或者表示成 u-v * 边数 E 不超过 VV-1/2 ----------------------- 页面 5----------------------- 图形表示 * 此二图是同一个图的 不同表示. 图中并不定 义各个结点的位置以 及边的形态直线曲 线, 关键是有哪些 点,哪些点相连 * 所有边如下表 ----------------------- 页面 6----------------------- 其他术语 * 其他名称 – 结点顶点 vertex, node – 边弧 edge, arc, link * 对于边 eu, v – u 和 v 邻接adjacent – e 和 u、v 关联incident – 点的度数degree是与它关联的边的数目 * 子图 – 子图subgraph 边的子集和相关联的点集 – 导出子图induced graph 点的子集和相关联的边集 ----------------------- 页面 7----------------------- 图绘制 * 图绘制Graph Drawing 顶点赋予几何坐标, 边绘制成直线或者曲线 * 平面图planar graph 可以绘制成边不相交 的形式 * 欧几里得图euclidean graph的绘制中,顶 点的位置和边是有意义的, 例如地图或者电 路图 * 本文的多数算法不使用几何信息 ----------------------- 页面 8----------------------- 同构 * 上面两个图同构, 但不和下面的图同构 ----------------------- 页面 9----------------------- 路径和圈 * 一条路径path是一个结点序列, 路上的相邻结点 在图上是邻接的. * 如果结点和边都不重复出现, 则称为简单路径 simple path. 如果除了起点和终点相同外没有重 复顶点和边, 称为圈cycle. * 不相交路disjoint path表示没有除了起点和终点 没有公共点的路. 更严格地 – 任意点都不相同的叫严格不相交路vertex-disjoint path – 同理定义边不相交edge-disjoint path路 * 注意 汉语中圈和环经常混用包括一些固定术语. 由于一般不讨论自环self-loop, 所以以后假设二 者等价而不会引起混淆 ----------------------- 页面 10----------------------- 连通性 * 如果任意两点都有路径, 则称图是连通 connected的, 否则称图是非连通的. * 非连通图有多个连通分量connected component, cc, 每个连通分量是一个极大 连通子图maximal connected subgraph, 因为任意加一个结点以后将成为非连通图 ----------------------- 页面 11----------------------- 生成树 * 连通去圈图成为树tree * 树的集合称为森林forest * 生成树 包含某图 G 所有点的树 * 生成森林 包含某图 G 所有点的森林 * 一个图 G 是树当且仅当以下任意一个条件成立 – G 有 V-1 条边, 无圈 – G 有 V-1 条边, 连通 – 任意两点只有唯一的简单路径 – G 连通, 但任意删除一条边后不连通 * 还有其他条件,可类似定义 ----------------------- 页面 12----------------------- 完全图和补图 * 如果 V 个点的图有 VV-1/2 图, 称为完全图 * 对于u,v, 若邻接则改为非邻接, 若非邻接则改 为邻接, 得到的图为原图的补图 * 原图和补图complement graph的并union为 完全图 * 完全子图称为团clique ----------------------- 页面 13----------------------- 术语示意 ----------------------- 页面 14----------------------- 稀疏图和稠密图 * 边和 VV-1/2 相比非常少的称为稀疏图 sparse graph, 它的补图为稠密图dense graph * 时间复杂度为 ElogE 的算法和 V2 的算法对于 稀疏图来说前者好, 稠密图来说后者好 * 一般来说, 即使对于稀疏图, V 和 E 相比都很 小, 可以用 E 来代替 VE, 因此 OVVE可 以简写为 OVE ----------------------- 页面 15----------------------- 二分图 * 可以把结点分成两部 分, 每部分之间没有边. 这样的图只有奇圈 odd-cycle, 即包含奇 数条边的圈 * 许多困难问题在二分 图上有有效算法 ----------------------- 页面 16----------------------- 相交图、区间图 * 交图 把物体看作顶点, 相交关系看为边 * 特殊情况 区间图interval graph. 很多困难问 题在区间图上有有效算法 ----------------------- 页面 17----------------------- 有向图 * 边都是单向unidirectional的, 因此边u,v是有序数对. 有 时用弧arc专指有向边 * 在有向边u, v中, u 和 v 分别叫 – 源source和目的destination – 尾tail和头head, 不过和数据结构有冲突 * 有向无环图directed acyclic graph, DAG不是树, 它的基 图underlying undirected graph也不一定是树 ----------------------- 页面 18----------------------- 带权图 * 可以给边加权weight, 成为带权图, 或加权图 weighted graph. 权通常代表费用、距离等, 可 以是正数, 也可以是负数 * 也可以给点加权, 或者边上加多种权 * 带权有向图一般也称为网络network * 带权图的问题多为组合优化问题, 在运筹学中有 广泛应用 ----------------------- 页面 19----------------------- 图的 ADT * 图的 ADT 如下 – V, E 返回顶点数和边数 – bool directed 当且仅当有向图返回真 – insertEdge / removeedge 增加/删除边 – bool edgeint, int 邻接测试 – AdjList getAdjListint 返回邻居列表 * Edge 包含 u, v 两个成员 * AdjList 支持取 beg, nxt 和 end 测试 ----------------------- 页面 20----------------------- 图 IO 的 ADT * 当图需要进行 IO 的时候,通常需要支持以 下操作 – scanEZ 读入边列表顶点用 0,1,V-1 表示 – scan 读入边列表顶点用符号表示 – show 输出边列表 ----------------------- 页面 21----------------------- 基本图问题 * 和图有关的问题通常有三种 – 计算图的某种度量值 – 计算某个子图边的子集 – 回答关于图属性的询问 * 动态问题 插入/删除边和询问交替 ----------------------- 页面 22----------------------- 基本表示方法 * 邻接矩阵adjacency-matrix * 邻接表adjacency-list * 前向星forward star ----------------------- 页面 23----------------------- 基本概念 * A[i,j]0 表示u,v不邻接, 1 表示邻接 ----------------------- 页面 24----------------------- 相关问题 * 如何处理重边和自环 * 如何用位存储节省空间 * 如果用上三角法储存无向图 * 如何用边测试函数而非完整的邻接矩阵储 存隐式图 * 如何修改 A 的元素类型以储存边的附加信息 ----------------------- 页面 25----------------------- 邻接表 * 每个结点的邻居形成一个链表 ----------------------- 页面 26----------------------- 相关问题 * 邻居排序方式可能影响结果 * 查找/删除边不是常数时间 * 邻接表的空间 OVE, 对于稀疏图优于邻接 矩阵 * 可以用编号代替指针, 加快速度并节省空间 ----------------------- 页面 27----------------------- 前向星表示 * 把所有边u, v按 u 的主关键字, v 为次关键字 排序, 并记录每个结点 u 的邻居列表的开始 位置 start[u]则 start[u1]是结束位置 * 紧凑存储, 不需要使用指针, 但边的插入和 删除操作可能引起大幅度变化. * 一般用于静态图. 可以方便的遍历一个点的 所有邻居并通过可以储存”当前弧”提高某些 图算法的效率 ----------------------- 页面 28----------------------- 练习 * 给定邻接表, 如何统计每个点的出度和入度 * 对于有向图的邻接表和邻接矩阵, 分别如何计算图 的转置转置即把所有有向边u,v变成v,u * 对于邻接表和邻接矩阵, 设计算法计算图 G 的平方 G2 2 . 如果 G 有边u, v和v, w, 则 G 中有边u, w, 即 G2 中的边对应于 G 中恰走两步可以到达的点对 * 给出有向图的邻接矩阵, 判断是否存在汇sink, 即 入度为|V|-1, 出度为 0. 时间复杂度应为 OV * 关联矩阵 B 是一个|V|*|E|的矩阵, 若 j 是 i 的出边, 则 b T -1, 若为入边, b 1, 否则为 0. 解释 BB 的含义 ij ij ----------------------- 页面 29----------------------- 2 图的遍历及其应用 2.1 宽度优先遍历 2.2 深度优先遍历和边分类 2.3 拓扑排序 2.4 欧拉回路 ----------------------- 页面 30----------------------- BFS 基本算法 * 由 Moore 和 Lee 独立提出 * 给定图 G 和一个源点 s, 宽度优先遍历按照从近到 远的顺序考虑各条边. 算法求出从 s 到各点的距离 * 宽度优先的过程对结点着色. – 白色 没有考虑过的点 – 黑色 已经完全考虑过的点 – 灰色 发现过, 但没有处理过, 是遍历边界 * 依次处理每个灰色结点 u, 对于邻接边u, v, 把 v 着 成灰色并加入树中, 在树中 u 是 v 的父亲parent或 称前驱predecessor. 距离 d[v] d[u] 1 * 整棵树的根为 s ----------------------- 页面 31----------------------- ----------------------- 页面 32----------------------- 用 BFS 求最短路 * 定理 对于无权图每条边的长度为 1, BFS 算法计算出的 d[i]是从 s 到 i 的最短路 * 满足 d[i]1 的点一定是正确的因为长度至少 为 1, 并且其他点都满足 d[i]1. 容易证明对 于任意距离值 x, d[i]x 的点一定是正确的, 而且白色点没有计算出距离的点的距离一 定至少为 x1 * 更进一步, 根据每个点的 parent 值, 可以计算 出它到 s 的一条最短路 ----------------------- 页面 33----------------------- 练习 * 给出判断图是否为二分图的线性时间算法 * 一棵树 T 的直径定义为结点两两间距离的最 大值. 给出求树直径的线性时间算法 * 对无向图 G, 给出一个路径, 经过每条边恰好 两次一个方向一次. 如何利用这条路径来 走迷宫 ----------------------- 页面 34----------------------- DFS 基本算法 * 新发现的结点先扩展 * 得到的可能不是一棵树而是森林, 即深度优先森林 Depth-first forest * 特别之处 引入时间戳timestamp – 发现时间 d[v] 变灰的时间 – 结束时间 f[v] 变黑的时间 – 1d[v] f[v] 2|V| * 初始化 time 为 0, 所有点为白色, dfs 森林为空 * 对每个白色点 u 执行一次 DFS-VISITu ----------------------- 页面 35----------------------- DFS-VISIT 算法 * 初始化 time 为 0, 所有点为白色, dfs 森林为空 * 对每个白色点 u 执行一次 DFS-VISITu * 时间复杂度为 Onm ----------------------- 页面 36----------------------- ----------------------- 页面 37----------------------- DFS 树的性质 * 括号结构性质 * 对于任意结点对u, v, 考虑区间[d[u], f[u]] 和[d[v], f[v]], 以下三个性质恰有一个成立 – 完全分离 – u 的区间完全包含在 v 的区间内, 则在 dfs 树上 u 是 v 的后代 – v 的区间完全包含在 u 的区间内, 则在 dfs 树上 v 是 u 的后代 * 三个条件非常直观 ----------------------- 页面 38----------------------- DFS 树的性质 * 定理 1嵌套区间定理 在 DFS 森林中 v 是 u 的 后代当且仅当 d[u]d[v]f[v]f[u], 即区间包 含关系. 由区间性质立即得到. * 定理 2 白色路径定理 在 DFS 森林中 v 是 u 的 后代当且仅当在 d[u]时刻u 刚刚被发现, v 可 以由 u 出发只经过白色结点到达. 证明 由嵌 套区间定理可以证明 ----------------------- 页面 39----------------------- 边分类规则 * 一条边u, v可以按如下规则分类 – 树边Tree Edges, T v 通过边u, v发现 – 后向边Back Edges, B u 是 v 的后代 – 前向边Forward Edges, F v 是 u 的后代 – 交叉边Cross Edges, C 其他边,可以连接同 一个 DFS 树中没有后代关系的两个结点, 也可 以连接不同 DFS 树中的结点 * 判断后代关系可以借助定理 1 ----------------------- 页面 40----------------------- 边分类算法 * 当u, v第一次被遍历, 考虑 v 的颜色 – 白色, u,v为 T 边 – 灰色, u,v为 B 边只有它的祖先是灰色 – 黑色 u,v为 F 边或 C 边. 此时需要进一步判断 * d[u]d[v] F 边v 是 u 的后代, 因此为 F 边 * d[u]d[v] C 边v 早就被发现了, 为另一 DFS 树中 * 时间复杂度 Onm * 定理 无向图只有 T 边和 B 边易证 ----------------------- 页面 41----------------------- DFS 树的性质演示 * 图 a DFS 森林 * 图 b 括号性质 * 图 c 重画以后的 DFS 森林, 边的分类更形象 ----------------------- 页面 42----------------------- 实现细节 * 颜色值以及时间戳可以省略, 用意义更加明 确的 pre 数组和 post 代替 d 和 f 数组, pre[u]和 post[u]代表点 u 的先序/后序编号, 则检查 u,v可以写为 – if pre[v] -1 dfsv; //树边, 递归遍历 – else if post[v] -1 show“B”; //后向边 – else if pre[v] pre[u] show“F”; // 前向边 – else show“C”; // 交叉边 * pre 和 post 的初值均为-1, 方便了判断 ----------------------- 页面 43----------------------- 使用 pre 和 post 的 DFS ----------------------- 页面 44----------------------- 练习 * 对于三种颜色 WHITE, GRAY 和 BLACK, 作一个 3*3 表格, 判断一种颜色到另一种颜色是否可能有 边, 如有可能, 边的类型如何 * 对于边u,v, 证明它是 – T 或 F 边当且仅当 d[u]d[v]f[v]f[u] – B 边当且仅当 d[v]d[u]f[u]f[v] – C 边当且仅当 d[v]f[v]d[u]f[u] – 如何区分 T 边和 F 边 * 修改 DFS 算法, 使得对于无向图, 可以求出每个点 i 所处的连通分量编号 cc[i] ----------------------- 页面 45----------------------- 练习 * 考虑无向图的边分类. – 证明只有 T 边和 B 边 – 两次分类有可能是不一样的. 一种方案是只取 第一次分类的结果, 另一种方案是按照类型优 先级T 先于 B. 证明两种方案等价 * 一个有向图是单连通的, 如果 u 可达 v, 则 u 到 v 只有唯一一条简单路径. 设计一个判断一 个图是否为单连通的算法 ----------------------- 页面 46----------------------- 参考资料 * CLRS 22.3 Depth-first Search * Algorithms in Java, Third Edition, 19.2 Anatomy of DFS in Digraphs ----------------------- 页面 47----------------------- 拓扑顺序 * 穿衣服的顺序 ----------------------- 页面 48----------------------- 拓扑排序算法 * 对图 G 使用 DFS 算法, 每次把一个结点变黑 的同时加到链表首部 * 定理 1 有向图是 DAG 当且仅当没有 B 边 – 如果有 B 边, 有环易证 – 如果有环 c, 考虑其中第一个被发现的结点 v, 环 中 v 的上一个结点为 u, 则沿环的路径 vu 是白 色路径, 有白色路径定理, u 是 v 的后代, 因此u, v是 B 边 * 定理 2 该算法正确的得到了一个拓扑顺序 ----------------------- 页面 49----------------------- 练习 * 举例说明存在一个图 G 和它的一个拓扑顺序, 拓扑排序算法无法得到此序不管结点排列 顺序如何 * 设计一个算法判断无向图是否含圈. 时间复 杂度应为 OV, 和 E 无关 * 每次找 0 度点, 用队列设计一个 OVE时间 的算法 ----------------------- 页面 50----------------------- 欧拉回路 * 如下图, 每条边经过一次且仅一次的称为欧拉回 路euler cycle, euler circuit. ----------------------- 页面 51----------------------- 欧拉回路 * 存在欧拉回路的充要 条件 每个点的度数都 是偶数, 且图连通 * 算法 套圈 – 删除一个圈后, 剩下的 图每个连通分量都有欧 拉回路 – 至少有一个公共点的圈 可以合并 ----------------------- 页面 52----------------------- 算法 * 算法 找一个圈用 DFS, 然后把边上的边都 删除, 求剩下各连通分量的欧拉回路, 最后 合并起来 ----------------------- 页面 53----------------------- 3 有向图强连通分量和传递闭包 3.1 SCC 的概念 3.2 Kosaraju 算法 3.3 Tarjan 和 Gabow 算法 ----------------------- 页面 54----------------------- SCC 的概念 * 有向图中, u 可达 v 不一 定意味着 v 可达 u. 相互 可达则属于同一个强连 通分量Strongly Connected Component, SCC * 有向图和它的转置的强 连通分量相同 * 所有 SCC 构成一个 DAG ----------------------- 页面 55----------------------- Kosaraju 算法 * 算法步骤 – 调用 DFSG, 计算出每个结点的 f[u] – 计算 GT T – 调用 DFSG , 在主循环中按照 f[u]递减的顺序 执行 DFS-VISIT, 则得到的每个 DFS 树恰好对应 于一个 SCC * 运行时间Onm * 算法示例 先把 f[u]排序成 postI 数组, 然而在 GT 上 DFS ----------------------- 页面 56----------------------- ----------------------- 页面 57----------------------- Kosaraju 算法的正确性 * 当按照 f 值排序以后, 第二次 DFS 是按照 SCC 的拓 扑顺序进行以后所指 d[u]和 f[u]都是第一次 DFS 所 得到的值 * 记 dC和 fC分别表示集合 U 所有元素的最早发现 时间和最晚完成时间, 有如下定理 * 定理 对于两个 SCC C 和 C’, 如果 C 到 C’有边, 则 fCfC’ – 情况一 dC dC’, 考虑 C 中第一个被发现的点 x, 则 C’全为白色, 而 C 到 C’有边, 故 x 到 C’中每个点都有白 色 路径. 这样, C 和 C’全是 x 的后代, 因此 fC fC’ – 情况二 dC dC’. 由于从 C’不可到达 C, 因此必须 等 C’全部访问完毕才能访问 C. 因此 fC fC’ T * 推论对于两个 SCC C 和 C’, 如果在 G 中 C 到 C’有 边, 则 fCfC’ ----------------------- 页面 58----------------------- Kosaraju 算法的正确性 * 首先考虑 fC最大的强连通分量. 显然, 此次 DFS 将访问 C 的所有点, 问题是是否可能访 问其他连通分量的点 答案是否定的, 因为 根据推论, 如果在 GT 中 C 到另外某个 C’存在 边, 一定有 fCfC’, 因此第一棵 DFS 恰好 包含 C. 由数学归纳法可知, 每次从当前强连 通分量出发的边一定连到 f 值更大的强连通 分量, 而它们是已经被遍历过的, 不会在 DFS 树形成多余结点 ----------------------- 页面 59----------------------- SCC 图 * 把 SCC 看成点, 则 DFS 的同时可以得到 SCC 图. 在第二次 DFS 中, 每新开始一次 DFS- VISIT, 即新找到一个 SCC, 当前编号加 1. * DFS-VISIT 某个 SCC C 时, 如果出现了指向 一个已访问过的 SCC C’的交叉边, 则在 SCC 图中设置边C’, C, 因为在转置图中存 在 C 到 C’的边 ----------------------- 页面 60----------------------- 局限性 * SCC 算法的简单历史 – 第一个 SCC 算法 Tarjan 1972 经典算法 – 80 年代 精美的 Kosaraju 算法后来发现和 1972 年苏联发现的算法本质相同 – 1999 Gabow 在 60 年代的思想上提出了第三个 线性算法 * 局限性 Kosaraju 算法需要计算图的转置和 两次 DFS, 时间效率不如 Tarjan 算法和 Gabow 算法 ----------------------- 页面 61----------------------- 基于 DFS 的 SCC 算法 * 结点放在栈 S 中 – 当一个点结束后,它所在的 SCC 就访问完成了 – 但是若任意点都可以输出 SCC, 会引起重复 – 我们把输出任务交给 SCC 中 pre 最小的一个 * 如何判断输出任务由谁完成呢 – 条件 如果 u 或者 u 的后代存在一条反向边w, v 到达 u 的祖先 v, 那么 u 和父亲属于同一个 SCC, 且由于 pre[v]pre[u], 任务不可能需要 u 完成 – Tarjan 算法 使用 LOW 函数测试该条件 – Gawbow 算法 使用另一个栈 ----------------------- 页面 62----------------------- Tarjan 算法 * Tarjan 算法 定义辅助函数 low[u]为 u 及其的 后代所能追溯到的最早最先被发现祖先点 v 的 pre[v]值, 则可以在计算 low 的同时完成 SCC 计算 * 检查完儿子和检查反向边时更新 low 函数, 交叉边可以通过特殊手段避免 ----------------------- 页面 63----------------------- LOW 函数的计算 min low[u] pre[u] cnt; //初始为 pre[u] S.pushu; for u 的邻居 v { //计算 min if pre[v] -1 dfs-visitv; if low[v] min min low[v]; } if min low[u] { low[u] min; return; } //任务不用 u 完成 do { id[v S.pop] scnt; low[v] n; } while v u; scnt; * 注意 输出 SCC 后需要设置 low 值均为最大值 n 以 防止交叉边影响结果 ----------------------- 页面 64----------------------- LOW 函数的计算 ----------------------- 页面 65----------------------- Gabow 算法 * Gabow 算法使用另一个栈 P 保留当前路径中的结 点, 发现反向边u,v后不断出栈, 只保留 v pre[u] cnt; S.pushu; P.pushu; For u 的每个邻居 v if pre[v] -1 dfs-visitv; else if id[v] -1 while pre[P.top] pre[v] P.pop; if P.top u P.pop; else return; do { id[v S.pop] scnt; } while v u; scnt; ----------------------- 页面 66----------------------- Tarjan 和 Gabow 算法过程 ----------------------- 页面 67----------------------- 应用 传递闭包 * 对于图 G 的任意一个结点 u, u 可达的结点集 合称为 u 的传递闭包 * 无向图 u 的传递闭包为和 u 处于同一连通分 量的点集 * 有向图 先求 SCC 图, 则 u 的传递闭包为 u 所 处 SCC 和它的所有后代 SCC 中的结点 ----------------------- 页面 68----------------------- 参考资料 * CLRS 22.5 Strongly connected components * Algorithms in Java, Third Edition, 19.8 Strong Components in Digraphs ----------------------- 页面 69----------------------- 4 无向图割顶、桥和双连通分量 4.1 割顶和桥 4.2 连通性和双连通分量 ----------------------- 页面 70----------------------- 割顶和桥 * 对于无向连通图 G – 割顶是去掉以后让图不连通的点 – 桥是去掉以后让图不连通的边 ----------------------- 页面 71----------------------- 无向图的 LOW 函数 * 定义辅助函数 low[u]为 u 及其的后代所能追溯到的 最早最先被发现祖先点 v 的 pre[v]值 * 类似有向图的计算方式, 注意无向图只有 T 和 B 边 low[u] pre[u] cnt; for u 的不等于 u 的邻居 v{ //不考虑自环 if pre[v] -1 { // 白色点 dfs-visitv; if low[u] low[v] low[u] low[v]; } else if low[u] pre[v] low[u] pre[v]; } ----------------------- 页面 72----------------------- 割顶的判定 * 在一棵 DFS 树中 – 根 root 是割顶当且仅当它至少有两个儿子 – 其他点 v 是割顶当且仅当它有一个儿子 u, 从 u 或 者 u 的后代出发没有指向 v 祖先不含 v的 B 边, 则 删除 v 以后 u 和 v 的父亲不连通, 故为割顶 * 割顶判定算法 – 对于 DFS 树根, 判断度数是否大于 1 – 对于其他点 u, 如果不是根的直接儿子, 且 LOW[u] d[P[u]], 则它的父亲 vP[u]是割点 ----------------------- 页面 73----------------------- 桥的判定 * 边u,v为桥当且仅当它不在任何一个简单 回路中 * 发现 T 边u,v时若发现 v 和它的后代不存在 一条连接 u 或其祖先的 B 边, 则删除u,v后 u 和 v 不连通, 因此u,v为桥 * 桥的判定算法 发现 T 边u, v时若 LOW[v]d[u]注意不能取等号, 则u,v为桥 * 实现 用 pre 数组代替 d 数组, 取消 f 数组. 实际 代码是测试若 low[v]pre[v]则u,v是桥 ----------------------- 页面 74----------------------- 桥判定举例 ----------------------- 页面 75----------------------- 参考资料 * Algorithms in Java, Third Edition, 18.6 Separability and Biconnectivity ----------------------- 页面 76----------------------- 连通性定义 * 点连通度等价性 Whitney 定理 – 定义 1 把图变非连通所需删除的最少点数 * 1-连通 一般连通 * 2-连通 双连通, 删除一个点后仍连通无割顶 – 定义 2 任意两个点至少有 k 个不含相同结点的 路vertex-disjoint path. * 边连通度等价性 Menger 定理 – 定义 1 把图变非连通所需删除的最小边数 – 定义 2 任意两个点至少有 k 个不含相同边的路 edge-disjoint path. ----------------------- 页面 77----------------------- BCC * 一个图的块biconnected component, bcc是双连 通的极大子图 * 块间没有公共边, 以割顶相连 ----------------------- 页面 78----------------------- BCC 的性质 * 性质 1. 每条边都包含在某个 BCC 中. 证明 对于u, v, {u, v}是双连通的, 这是某 BCC 的 一部分 * 性质 2. 不同的两个 BCC 最多有一个公共结 点, 此结点是原图的割顶 * 性质 3. 不同的两个 BCC 不含公共边. 证明 如果有相同边, 则含有两个公共结点. * 根据性质 2 和性质 3 可知 BCC 是 G 的边划分 ----------------------- 页面 79----------------------- BCC 算法 * 对于点 v, 考虑 v 的父亲 u – u 是根, u,v是新 BCC 的第一条边 – 否则设 u 的父亲为 f. 若删除 u 后, v 和 f 不连通, 则{f, u, v}不是双连通的, 因此u, v是新 BCC 的第一 条边, 否则u, v和f, u处于同一个 BCC 中 * 实现 可以用栈, 类似于 SCC 的 Tarjan 算法 * 注意 自环没有编号, 因为在无向图中自环 被忽略 ----------------------- 页面 80----------------------- 收缩图 * 把每个 BCC 看成点 b, 每个割顶 a 也看成点. 则 b 和 a 相连当且仅当 b 包含 a. 这样得到的图 叫 BCC 收缩图 * BCC 收缩图是一棵树 ----------------------- 页面 81----------------------- 其他算法 * 修改的 Gabow 算法可以计算无向图的桥、 割顶、块和边连通分量 * 最大流可以用来计算任意图的点连通度和 边连通度

    注意事项

    本文(图结构和基本问题)为本站会员(hyngb9260)主动上传,收益归上传者所有,天天文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知天天文库(发送邮件至[email protected]或直接QQ联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服点击这里,给天天文库发消息,QQ:1290478887 - 联系我们

    网站客服QQ:1290478887        微信公众号:iwenku365

    [email protected] 2017-2027 wenku365.com 网站版权所有   聚力网络工作室

    经营许可证编号:鄂ICP备17008239号-1 

    收起
    展开