文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 建筑/土木 > 图的割点、桥与双连通分支
侵权投诉

图的割点、桥与双连通分支

图的割点、桥与双连通分支

[点连通度与边连通度]

在一个无向连通图中,如果有一个顶点集合,删除这个顶点集合,以及这个集合中所有顶点相关联的边以后,原图变成多个连通块,就称这个点集为割点集合。一个图的点连通度的定义为,最小割点集合中的顶点数。

类似的,如果有一个边集合,删除这个边集合以后,原图变成多个连通块,就称这个点集为割边集合。一个图的边连通度的定义为,最小割边集合中的边数。

[双连通图、割点与桥]

如果一个无向连通图的点连通度大于1,则称该图是点双连通的(point biconnected),简称双连通或重连通。一个图有割点,当且仅当这个图的点连通度为1,则割点集合的唯一元素被称为割点(cut point),又叫关节点(articulation point)。

如果一个无向连通图的边连通度大于1,则称该图是边双连通的(edge biconnected),简称双连通或重连通。一个图有桥,当且仅当这个图的边连通度为1,则割边集合的唯一元素被称为桥(bridge),又叫关节边(articulation edge)。

可以看出,点双连通与边双连通都可以简称为双连通,它们之间是有着某种联系的,下文中提到的双连通,均既可指点双连通,又可指边双连通。

[双连通分支]

在图G的所有子图G’中,如果G’是双连通的,则称G’为双连通子图。如果一个双连通子图G’它不是任何一个双连通子图的真子集,则G’为极大双连通子图。双连通分支(biconnected component),或重连通分支,就是图的极大双连通子图。特殊的,点双连通分支又叫做块。

[求割点与桥]

该算法是R.Tarjan发明的。对图深度优先搜索,定义DFS(u)为u在搜索树(以下简称为树)中被遍历到的次序号。定义Low(u)为u或u的子树中能通过非父子边追溯到的最早的节点,即DFS序号最小的节点。根据定义,则有:

Low(u)=Min

{

DFS(u)

DFS(v) (u,v)为后向边(返祖边) 等价于 DFS(v)<DFS(u)且v不为u的父亲节点

Low(v) (u,v)为树枝边(父子边)

}

一个顶点u是割点,当且仅当满足(1)或(2)

(1) u为树根,且u有多于一个子树。

(2) u不为树根,且满足存在(u,v)为树枝边(或称父子边,即u为v在搜索树中的父亲),使得DFS(u)<=Low(v)。

第1页

你可能喜欢

热门文档

相关文档

  • 算法学习:图论之图的割点,桥,双连通分支

    图的割点、 图的割点、桥与双连通分支 [点连通度与边连通度 点连通度与边连通度] 点连通度与边连通度在一个无向连通图中,如果有一个顶点集合,删除这个顶点...

  • 强连通分支、桥和割点

    强连通分支、桥和割点_生物学_自然科学_专业资料。有向图的强连通分支 本讲义部分内容引用北京大学信息学院实验班袁洋、陈科吉同学讲义, 特此致谢 定义 ? 在有...

  • 连通图的割点、割边(桥)、块、缩点,有向图的强连通分量

    连通图的割点、割边(桥)、块、缩点,有向图的强连通分量_IT/计算机_专业...为是双连通的,因 为任何一条电线出问题都不会破坏 A 和 B 之间的连通性,...

  • 强连通分支

    割点可以属于多个点双连通分 支,其余点和每条边只属于且属于一个点双 连通分支。 求无向连通图边双连通分支( 求无向连通图边双连通分支(不包 含桥的极大...

  • 连通控制数与2-分支控制数相等的图

    图的割点、桥与双连通分支 2页 免费 图的割点、桥与双连通分支 2页 免费... 如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击...

  • 连通图的割点、割边(桥)、块、缩点,有向图的强连通分量

    图的割点、桥与双连通分支 2页 免费 有向图的强连通分量 5页 免费... 连通图的割点、割边 桥、 缩点, 连通图的割点、割边(桥)、块、缩点,...

  • 3.3 图的连通性

    图的连通性一、 求一个图的连通分支 1 设图 G=(V,E)是一个无向图,G ...4 双连通图 双连通图:一个没有割点的图或说 k 不小于 2 的图。即移去...

  • 图连通性若干拓展问题探讨

    无向图的割点、割点集合与点连通度 ? 无向图的桥、割边集合与边连通度 ? 无向图的割点与点双连通分量的求法 ? 无向图的桥与边双连通分量的求法、边双...

  • 强连通分量

    求桥和割点的Tarjan算法思路和有向图求强连通分量类似 在深度优先遍历整个图...(); return 0; } 求无向图连通图点双连通分支(不 包含割点的极大连通子图...

  • 图的连通性

    缩点, 双连通分支, 割点,割边,欧拉路径,拓扑排序,2-sat 以下是一些较为...图的 割 顶与 桥图的割顶即删掉之后图就不连通的顶点,桥即删掉之后图就不...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email