强连通图的介绍

简介: 强连通图的介绍

注:强连通图说的是有向图,连通图说的是无向图,路径的意思是能到就行,其中间可以有中转站,也就是允许经过其他结点


问题一:强连通图任意两个顶点存在一条有向路径还是a到b到a都得互相有路径?

             解:互相有路径,也就是顺着箭头的方向走,

                    既可以从a走到b,也可以从b走到a


问题二:啥是极大强连通子图 ?

             解:1.为什么叫做极大?


                      极大是因为如果此时加入任何一个不在图的点集中的点都会导致它不再连通。


                    2.就是能连通的一个最大的有向图


                    3.强连通图的极大强连通子图为其本身。(是唯一的)

问题三:还有啥是强连通分量 ?


 解:极大强连通子图 叫做强连通分量,看下边这个例子

           首先要明确,

                   1. 极大强连通子图肯定是连通的,

                   2.若在增加一个结点,他们所构成的图将不是连通的

.若该有向图是强连通图,那么其极大强连通子图就是他本身

                       (那么其强连通分量就为一,也就是说有几个极大强连通子图就有几个强连通分量)

                   4.非强连通图有多个极大强连通子图


首先这个有向图不是一个强连通图

例如(D->C But C!->D)  

那么它就有多个极大强连通子图



经过计算,你就知道它有3个极大强连通子图就等价它有3强连通分量

问题四:非强连通图是不是没有强连通分量 ?

               解:非强连通图有多个极大强连通子图

相关文章
|
存储 Python
海明距离(Hamming Distance)
海明距离(Hamming Distance)是用来衡量两个二进制数之间差异程度的指标,它表示两个二进制数之间最多有多少个比特的差异。海明距离可以用于衡量数据传输或存储中的错误率,以及检测噪声干扰。 海明距离的计算方法是:对于两个 n 位二进制数,将它们进行逐位比较,如果对应位上的数字不同,则计算距离时增加 1。然后将所有位上的距离加在一起,得到海明距离。
1689 1
|
6月前
|
安全 数据挖掘 API
《区块链公链数据分析简易速速上手小册》第4章:交易数据分析(2024 最新版)(下)
《区块链公链数据分析简易速速上手小册》第4章:交易数据分析(2024 最新版)(下)
143 1
|
6月前
|
Python
判断闰年
判断闰年
|
存储
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强,强强在哪里?
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强,强强在哪里?
3785 1
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强,强强在哪里?
|
6月前
|
数据可视化 数据挖掘 区块链
《区块链公链数据分析简易速速上手小册》第4章:交易数据分析(2024 最新版)(上)
《区块链公链数据分析简易速速上手小册》第4章:交易数据分析(2024 最新版)(上)
295 0
|
5月前
|
数据可视化 算法 JavaScript
使用Python进行网络数据可视化的多种方法与技巧
在当今信息爆炸的时代,网络数据量呈指数级增长,了解和分析这些数据对于许多领域的决策制定至关重要。可视化是理解和解释大量数据的强大工具之一,而Python作为一种流行的编程语言,提供了丰富的库和工具来进行网络数据可视化。本文将介绍一些使用Python进行网络数据可视化的方法与技巧,并提供相应的代码实例。
|
6月前
|
Python
pycharm使用Anaconda中的虚拟环境【我的入门困惑二】
pycharm使用Anaconda中的虚拟环境【我的入门困惑二】
|
6月前
|
C语言
pta浙大版《C语言程序设计(第3版)》 习题6-4 使用函数输出指定范围内的Fibonacci数 (20分)
pta浙大版《C语言程序设计(第3版)》 习题6-4 使用函数输出指定范围内的Fibonacci数 (20分)
|
6月前
|
编译器 数据安全/隐私保护
PTA 线性表 7-1 约瑟夫环(Josephus)问题(by Yan) (100分) 按出列次序输出每个人的编号
PTA 线性表 7-1 约瑟夫环(Josephus)问题(by Yan) (100分) 按出列次序输出每个人的编号
|
6月前
|
C语言
PTA 浙大版《C语言程序设计(第3版)》题目集 习题8-4 报数 (20分)
PTA 浙大版《C语言程序设计(第3版)》题目集 习题8-4 报数 (20分)