首页 > 试题广场 >

# 判断正误 # 连通分量是无向图中极小连通子图。

[单选题]

# 判断正误 #

连通分量是无向图中极小连通子图。

  • 正确
  • 错误
推荐
错误
无向图:边没有方向的图称为无向图
其次,极大连通子图可以存在于无向图中,也可以存在于有向图中
最后,极小连通子图只存在于连通的无向图中,不存在于不连通的无向图和有向图中。
 无向图G的极大连通子图称为G的连通分量( Connected Component)
任何连通图的连通分量只有一个,即是其自身,非连通的无向图有多个连通分量。
编辑于 2019-11-13 14:35:54 回复(0)

答案选B


解析
大佬们的解析都太过于学术化,我来点偏实践理解的补充。
连通分量就是:给定一个无向图,从某个节点进行dfs深搜,所能够搜到的最大区域,也叫极大连通子图

发表于 2019-11-13 11:20:06 回复(0)
B
本题考查的是的相关基本概念。
首先了解一下无向图的概念:边没有方向的图称为无向图
其次,明确一个概念,极大连通子图可以存在于无向图中,也可以存在于有向图中
最后知道,极小连通子图只存在于连通的无向图中,不存在于不连通的无向图和有向图中。
无向图G的极大连通子图称为G的连通分量。任何连通图的连通分量只有一个,即是其自身,非连通的无向图有多个连通分量。
综上所述,题干错误,答案选B。

发表于 2019-11-12 16:23:09 回复(0)
概念记混了,极小连通子图是最小生成树,极大连通子图才是连通分量
发表于 2022-07-26 20:50:32 回复(0)
B。考察的是连通分量的定义。
  • 在无向图中,如果从顶点vi到顶点vj有路径,则称vi和vj连通。如果图中任意两个顶点之间都连通,则称该图为连通图,否则,将其中的较大连通子图称为连通分量
  • 在有向图中,如果对于每一对顶点vi和vj,从vi到vj和从vj到vi都有路径,则称该图为强连通图;否则,将其中的极大连通子图称为强连通分量
发表于 2019-11-12 18:13:13 回复(0)
无向图:边没有方向的图
极大连通子图可以存在于无向图中,也可以存在于有向图
极小连通子图只存在于连通的无向图中,不存在于不连通的无向图和有向图。


编辑于 2022-05-19 21:14:19 回复(0)
连通分量:给定一个无向图,从某个结点进行dfs深度搜索,所能够搜到的最大区域,也叫极大连通子图。
发表于 2021-03-22 15:33:58 回复(0)

G的连通分量是指极大连通子图,极小连通子图只存在于连通的无向图中

发表于 2020-03-14 15:13:21 回复(0)
错误。
首先定义子图,就是说一个图的边集和点集都是另外一个图的子集。
路径:如果图的边集中存在这些边: (x_1,x_2), (x_2, x_3), ... , (x_(k-1), x_k),则说存在一条x_1到x_k的路径。
有向图的连通性:一个图中的任何一对点(u, v)都存在一条从u到v的路径。
连通子图:一个图是另外一个图的子图,并且它连通。
极大(强)联通子图:一个图的(强)连通子图,并且加入任何一个不在它的点集中的点都会导致它不再(强)连通。
强连通是对于有向图的说法。
发表于 2019-11-12 17:09:47 回复(0)