双连通图和关节点

本文阅读 1 分钟
首页 知识库 正文

若从一个连通图中删去任何一个顶点及其相关联的边,它仍为一个连通图的话,则该连通图被称为重(双)连通图。

若连通图中的某个顶点和其相关联的边被删去之后,该连通图被分割成两个或两个以上的连通分量,则称此顶点为关节点。

没有关节点的连通图为双连通图

若生成树的根结点,有两个或两个以上的分支,则此顶点(生成树的根)必为关节点;
对生成树上的任意一个非叶“顶点”,若其某棵子树中的所有“顶点”没有和其祖先相通的回边,则该“顶点”必为关节点。

解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

生成树和最小生成树
« 上一篇 01-21
有向无环图及其应用
下一篇 » 01-21

发表评论