图的基本概念辨析,包括连通图、极大连通子图、连通分量、强连通图、极大强连通子图等

这篇具有很好参考价值的文章主要介绍了图的基本概念辨析,包括连通图、极大连通子图、连通分量、强连通图、极大强连通子图等。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

概念(1-4)都是针对无向图的

1.连通图

  图中从一个顶点到达另一顶点,若存在至少一条路径,则称这两个顶点是连通着的。例如图 1 中,虽然 V1 和 V3 没有直接关联,但从 V1 到 V3 存在两条路径,分别是 V1-›V2-›V3 和 V1-›V4-›V3,因此称 V1 和 V3 之间是连通的。
连通子图,算法,图论

图 1 顶点之间的连通状态示意图

  无向图中,如果任意两个顶点之间都能够连通,则称此无向图为连通图。

2.极大连通子图

  子图:设G = <V,E>, G’ = <V’,E’>为两个图(同为无向图或同为有向图),若V’ ∈ \in V 且 E’ ∈ \in E,则称G’是G的子图,G是G’的母图。
  极大连通子图:对于图的某一子图,它包含了图中尽可能多的顶点以及尽可能多的边,以至于它再加上一个点或者边之后它就不连通了,此时这个图就是极大连通子图。
  对于连通无向图:只有一个连通分量也就是只有一个极大连通子图,就是它本身。
  非连通图:有多个极大连通子图,也就是有多个连通分量。

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

  无向图G的极大连通子图称为G的连通分量。
  如图 2所示,虽然图 2 a) 中的无向图不是连通图,但可以将其分解为3个“ 最大子图”(图2 b)),它们都满足极大连通子图的性质,因此都是连通分量,也都是极大连通子图。
连通子图,算法,图论

图 2 连通分量示意图

  所以,连通分量和极大连通子图是同一个概念,连通分量主要是对非连通图来说的,因为连通图是一个整体,分量是对非整体来说的,对于连通图其连通分量和极大连通子图都是连通图本身。
  理解了极大连通子图的概念就不会误以为极大连通子图是最大的那一个子图,其含义是大到再加边或者点之后就不能连通的子图。因此图2 b)中的3个子图都是极大连通子图。

4.极小连通子图(只存在于连通图中,对于非连通图的意义不大)

生成树:对一个具有 n 个点的连通图进行遍历,对于遍历后的子图,其包含原图中所有的点且保持图连通,最后的结构一定是一个具有 n-1 条边的树,通常称为生成树。(所以生成树是对于连通图来说的)
极小连通子图:“极小”是指边最少的连通子图,去掉任何一个边都会使其变的不连通。所以一个连通图的生成树是该连通图顶点集确定的极小连通子图。
  其实极小连通子图的概念是用来辅助定义生成树的概念的。

概念(5-8)都是针对有向图的

5.强连通图

  有向图中,若任意两个顶点 V i V_i Vi V j V_j Vj,满足从 V i V_i Vi V j V_j Vj以及从 V j V_j Vj V i V_i Vi都连通,也就是都含有至少一条通路,则称此有向图为强连通图。如图3所示就是一个强连通图。
连通子图,算法,图论

图 3 强连通图

  可以这样说,连通图是在无向图的基础上对图中顶点之间的连通做了更高的要求,而强连通图是在有向图的基础上对图中顶点的连通做了更高的要求。

6.极大强连通子图

  此概念和无向图的“极大连通子图”的概念类似,只是前者是对有向图而言,后者是对无向图而言。

7.强连通分量

  此概念和无向图的“连通分量”的概念类似,只是前者是对有向图而言,后者是对无向图而言。
  如图4中的2个子图都是强连通分量,也都是极大强连通子图。
连通子图,算法,图论

图 4 强连通分量

8.极小强连通子图

  有向图并无此概念。

声明

  本资料是我本人整合网上的资料得来的,主要是因为发现很多帖子讲不清楚这个几个概念,很多发帖人自己并未真正理解这些概念之间的区别,读者看了并不能学到正确的知识。所以我一边学习,一边整理出了这篇文章,本人所作也并非都是正确的,如有错误,还望指正。文章来源地址https://www.toymoban.com/news/detail-612566.html

到了这里,关于图的基本概念辨析,包括连通图、极大连通子图、连通分量、强连通图、极大强连通子图等的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【图论】强连通分量进阶

    强连通分量可以判断环和进行缩点。还有一系列作用.... 这篇文章介绍 缩点 https://www.luogu.com.cn/problem/P2341 我们分析可以知道当一个点没有出度时,则为最受欢迎的牛。但如果有多个出度,则没有最受欢迎的牛。 这是只有一个出度的情况:   这是多个出度的情况: 但为什么要

    2024年02月14日
    浏览(45)
  • 图论——强连通分量详解!

    本篇主要内容: 强连通分量等概念 Tarjan算法的过程与实现 首先我们要明白上面是 连通 。 在一张图中 任意 两个点能 互相 到达。(举个例子) 所以我们称上面的这个图是一个 连通图 !  接着我们在来理解什么是 强连通 。 若一张 有向图 的节点两两互相可达,则称这张图

    2024年02月07日
    浏览(37)
  • 有向图的强连通分量

    对于一个有向图,连通分量:对于分量中任意两点u,v,必然可以从u走到v,且从v走到u. 强连通分量:极大连通分量。 求出强连通分量后,可以通过将强连通分量缩点的方式,将有向图转化成有向无环图。 求强连通分量的方法:tarjan O(n+m),时间复杂度是线性的 1 . 采用dfs来遍历整

    2024年02月10日
    浏览(39)
  • 有向图的强连通分量算法

    有向图的强连通分量算法 强连通分量定义 在有向图中,某个子集中的顶点可以直接或者间接互相可达,那么这个子集就是此有向图的一个强连通分量,值得注意的是,一旦某个节点划分为特定的强连通分量后,此顶点不能在其它子树中重复使用,隐含了图的遍历过程和极大

    2024年02月06日
    浏览(84)
  • 第三章 图论 No.9有向图的强连通与半连通分量

    连通分量是无向图的概念,yxc说错了,不要被误导 强连通分量:在一个有向图中,对于分量中的任意两点u,v,一定能从u走到v,且能从v走到u。强连通分量是一些点的集合,若加入其他点,强连通分量中的任意两点就不能互相递达 半连通分量:在一个有向图中,对于分量中

    2024年02月13日
    浏览(50)
  • 离散数学:图的基本概念

    本帖子讨论图的基本概念,这一章,我们将利用有序对和二元关系的概念定义图。图分为了无向图和有向图,他们有共性也有区别,请大家注意体会,用联系和辩证的观点去认识。 注意无向图和有向图的表示,最大区别在于边的集合的表示,无向图中边集为无序集VV的子集,

    2024年02月09日
    浏览(53)
  • 图的基本概念

    一个图 G 它可以由顶点集(图 G 中顶点的有限非空集) V 和边集(图 G 中顶点之间的关系集合) E 所组成。图中顶点个数也可以称为图的阶;任何一条边的两头必须连接某一个顶点。图不可以是空,即顶点集 V 一定是非空集,但边集 E 可以是空集。 有向图 无向图 无向图里的

    2024年02月14日
    浏览(51)
  • 团体程序设计天梯赛 L2-013 红色警报(连通分量)

    分数 25 战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序,当失去一个城市导致国家被分裂为多个无法连通的区域时,就发出红色警报。注意:若该国本来就不完全连通,是分裂的k个区域,而失去一个城市并不改变其他城市之间的连通性,则不要发出

    2024年03月13日
    浏览(52)
  • 数据结构:图的基本概念

    图是一种非线性的数据结构,表示多对多的关系。 图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V, E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。 在图中需要注意的是: 线性表和树可以看做特殊的图。 线性表中我们把数据

    2023年04月12日
    浏览(45)
  • 图论_(1)_图的基本概念

    图(graph) 是由顶点集合和顶点间的二元关系集合(即边的集合或弧的集合)组成的数据结构,通常可以用 G ( V , E ) G(V,E) G ( V , E ) 表示 顶点集合(vertext set) 用 V ( G ) V(G) V ( G ) 表示,其中元素称为 顶点(vertex) ,用 u 、 v u、v u 、 v 等符号表示。 边的集合(edge set) 用 E ( G ) E(G) E ( G

    2024年02月05日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包