强连通图的介绍

简介: 强连通图的介绍

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


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

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

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


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

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


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


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


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

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


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

           首先要明确,

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

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

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

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

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


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

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

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



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

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

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

相关文章
|
15天前
|
算法
二叉树刷题记(八-二叉树的最大深度-深度遍历)
二叉树刷题记(八-二叉树的最大深度-深度遍历)
|
15天前
将一个顺序表的前三个元素移到最后
将一个顺序表的前三个元素移到最后
|
15天前
实现array.slice()方法
实现array.slice()方法
|
15天前
## 标题: 求一元二次方程的根(25分)
## 标题: 求一元二次方程的根(25分)
|
15天前
|
C语言
PTA 浙大版《C语言程序设计(第3版)》题目集 习题8-4 报数 (20分)
PTA 浙大版《C语言程序设计(第3版)》题目集 习题8-4 报数 (20分)
|
15天前
|
C语言
C语言 浙大版《C语言程序设计(第3版)》题目集 练习8-8 移动字母 (10分)
C语言 浙大版《C语言程序设计(第3版)》题目集 练习8-8 移动字母 (10分)
|
15天前
|
C语言
浙大版《C语言程序设计(第3版)》题目集 练习8-2 计算两数的和与差 (10分)
浙大版《C语言程序设计(第3版)》题目集 练习8-2 计算两数的和与差 (10分)
|
15天前
链表之有头链表
链表之有头链表
|
15天前
|
开发工具 git
git上传和下拉远程仓库
git上传和下拉远程仓库
|
15天前
|
Windows
虚拟机内存越用越少,即使文件都永久删除了!!!
虚拟机内存越用越少,即使文件都永久删除了!!!