当前位置:   article > 正文

无向图,有向图,连通图,强连通图概念笔记_连通图 csdn

连通图 csdn

无向图

边没有箭头的图,即边是无向边(简称边)的图

有向图

边有箭头的图,即边是有向边(简称弧)的图

连通图

此概念仅在无向图中讨论

所有的边是否能将所有顶点串在一块,也就是从一个顶点单次顺着路径随意爬是否能爬到任意另一个顶点,如果能,则是连通图

        极大连通子图

                首先了解子图的概念

                part1 子图——在原图中任割取一部分,将其变成图,即是子图,意味着子图的顶点数量,边,都是不确定的

                part2 连通子图则是带有连通图属性的子图,即通过尽可能少的,原图上即有的边,去连通尽可能多的顶点

                而极大连通子图,其“极大”就是两个极大

                                1.顶点极大——顶点的数量拉满

                                2.边极大——边的数量拉满

                也就是在连通的前提上,通过尽可能多的原图上即有的边,连接尽可能多的顶点,这声明了极大连通子图子图(part1)和连通图(part2)最大的区别,抑或是更高的要求。

        连通分量

                极大连通子图称为连通分量

强连通图

此概念仅在有向图中讨论

看我从一个点出发,能否再次回到这个点,即教科书所谓“是否能形成回路

        极大强连通子图

                前面讨论了何为极大,即顶点和边拉满,这里在有向图中,即顶点和弧的数量拉满

                总之就是寻找最大的子回路(强连通的基础上顶点拉满),然后将其把原图中应该有的弧都画上(弧的数量拉满)

        强连通分量

                极大强连通子图成为强连通分量

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/代码探险家/article/detail/891169
推荐阅读
相关标签
  

闽ICP备14008679号