什么是极大强连通子图?
一、极大强连通子图是什么
极大强连通子图
（1）极大连通子图是连通图的一个连通分量，连通分量本身是一个连通图。
（2）连通图的极大连通子图只有一个就是其本身，是少数的。
（3）非连通的极大连通子图有多个，每一个都是一个连通图。
为什么称为极大？如果将连通分量外的任意一个顶点添加进连通分量都会造成不连通。
极小连通子图
（1）一个连通图的生成树是该连通图的极小连通子图。同一个连通图可以有不同的生成树，所以生成树不是少数的。
（2）极小连通子图=生成树，则有n个顶点，必然有n-1条边。
（3）为什么称为最小？如果去极小连通子图的一条边就无法构成树，不满足树的定义。意味着在极小连通子图中每一条边都是必不可少的。如果给极小连通子图增加一条边，n个节点，n条边，则必然会构成环。意味只有能够连通图中所有顶点而又不会构成回路的任意的子图都是他的生成树。
延伸阅读：
二、强连通分量
强连通分量是有向图的极大的强连通子图，所谓“极大”意味着，把图划分为若干个强连通分量后，不存在两个强连通分量相互可达。处理强连通分量的一个有力的工具是dfs生成树：在dfs时，每当通过某条边e访问到一个新节点，就加入这个点和这条边，最后得到的便是dfs生成树。反向边和横叉边都有一个特点：起点的dfs序必然大于终点的dfs序。这可以导出一个有用的结论：对于每个强连通分量，存在一个点是其他所有点的祖先。若不然，则可以把强连通分量划成 n个分支，使各分支的祖先节点互相不为彼此的祖先。这些分支间不能通过树边相连，只能通过至少n条横叉边相连，但这必然会违背上一段讲的性质。
猜你喜欢LIKE
相关推荐HOT
更多>>
大数据具有哪些特点?
一、大数据的概念与内涵“大数据”的概念早已有之，1980年知名未来学家阿尔文•托夫勒便在《第三次浪潮》一书中,将大数据热情地赞颂为“第三次...详情>>
2023-10-11 21:54:13
JAVA里面表达式，关系式，条件表达式，逻辑表达式，四者有什么区别?
一、JAVA里面表达式，关系式，条件表达式，逻辑表达式，四者的区别区别是格式和优先级不同。关系表达式（左结合）优先级次于算述表达式（1）、=...详情>>
2023-10-11 21:29:45
计算机语言和高级语言的区别是什么?
一、计算机语言和高级语言的区别高级语言的源程序是可以用编译和解释联众方式执行的，而计算机机器语言源程序需要经过汇编生成目标文件执行。高...详情>>
2023-10-11 21:06:19
const int &const r2和const int &r2有什么区别?
一、const int &const r2和const int &r2const int &const 是不存在的，编译器会报错const int &const r2和const int &r2没有什...详情>>
2023-10-11 20:07:40热门推荐
uml图有哪些?
沸内联元素有哪些?
热常见的网络数据库有哪些?
热Python 在 Linux 里面有哪些应用?
新怎么做软件开发?
为什么函数式语言里有递归数据类型但没有递归函数类型?
大数据具有哪些特点?
python和java相比写app有什么区别?
JAVA里面表达式，关系式，条件表达式，逻辑表达式，四者有什么区别?
国内用户注册ChatGPT详细步骤及视频教程?
计算机语言和高级语言的区别是什么?
python 利用可变参数传入list并打印，与直接用for循环打印有什么区别?
大数据与深度学习有什么区别?
范畴论和类型论的区别和联系是什么?
京公网安备 11010802030320号