图的连通,连通图,连通分量,强连通分量

1.对于无向图而言,如果图中的某两个点,例如:存在W到V的路径,那么我们说w和v是连通的;进一步如果图中任意两点之间都是存在路径的,那么我们说这个是连通的,即可称为连通图

2.连通子图:设G=(V,E)和G`=(V`,E`),如果V`是V的子集,并且E`是E的子集,那么称G`是G的子图。如果子图是连通的,那么就是连通子图,这不难理解。(需要注意,并不是你随便从G=(V,E))中挑的V的子集V`跟E的子集E`,就能构成一个子图,因为有可能挑的边V跟顶点E没有关系,那也就构不成一个图了)

3.极大连通子图(连通分量)极小连通子图

a.极大连通子图就是连通分量

对于极大的理解是,极大针对的是,也就是边要越多越好,最后生成的子图中已经包含了原图G中的与子图G`中顶点相关的所有边。简单来说,凡是与G`中顶点有关的边,全都要(这也就隐含了,如果我们在一个极大连通子图中删去一些边,它依旧可能是连通的,可以与极小进行比较理解)。生成一个极大连通子图的过程可以理解为:从一个顶点出发,逐个添加所有与这个子图有边的顶点,直到将所有连通的顶点全都纳入这个图中,这时生成的子图就是极大的。

b.极小比较好理解,也是针对的,就是在保持子图中所有顶点连通的前提下,纳入最少的边,生成的图;也就是对于一个极小连通子图而言,再去掉任意一条边,那就非连通了。

4.强连通图强连通分量:

这两个是针对有向图而言的,有向图中,若W到V与V到W之间都有路径,那么就说这两个顶点是强连通的,如果图中每对顶点直接都是强连通的,那么这个图就是强连通图了。而有向图的极大强连通子图就是强连通分量。

注意:我们一般是在无向图中讨论连通性,在有向图中讨论强连通性

不知道有没有这样的困惑,既然包含了所有的边,那为什么不叫最大呢?极大本身已经要求包含所有的顶点了,那不就是原图G了吗?

关键在于,只考虑到了连通图G了,当原图G本身就是个连通图,那么极大连通子图就是原图了,此时也就是最大了。那如果G是非连通的呢?那就导致,上边那个生成极大连通子图的过程走一次,并不能将所有边纳进来,也就是说,一个非连通的图可能会有好几个极大连通子图(其实也就是好几个连通分量),此时也就不是最大了,而是极大。

 

    原文作者:阳ing
    原文地址: https://blog.csdn.net/main_double/article/details/109903887
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞