一图搞清楚(非)(强)连通图中的极大(小)（强）连通子图-Toy模板网

这篇具有很好参考价值的文章主要介绍了一图搞清楚(非)(强)连通图中的极大(小)（强）连通子图。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

在学习图的过程中，常常搞不清楚下面这些概念：

连通图、非连通图、强连通图、非强连通图、极大连通子图与连通分量、极大强连通子图与强连通分量、极小连通子图与生成树、极小强连通子图（后面得知根本就没有这个概念）......

现在决定用一张图（放大查看）对他们的关系进行说明：

首先我们需要对这些概念进行分类：

其次就具体来看下这些概念，其实真正涉及的核心概念就三个：极大连通子图（连通分量）；极小连通子图（生成树）；极大强连通子图（强连通分量）。

第一个极大连通子图，它就是连通分量。在一个连通图中，极大连通图子图就是该连通图本身，具有唯一性，如图1所示；在一个非连通图中，极大连通子图有多个，如图2所示。

图1

图2

第二个极小连通子图，它就是生成树。在一个连通图中，极小连通子图个数不唯一，但是都满足有n个节点和n-1个节点，如下图3所示；而在非连通图中是不存在极小连通子图的。

图3

第三个极大强连通子图，它就是强连通分量。在一个强连通图中，极大强连通子图是唯一的，如图4所示；而在非强连通子图中它不唯一，如图5所示。

图4

图5文章来源地址https://www.toymoban.com/news/detail-444998.html

到了这里，关于一图搞清楚(非)(强)连通图中的极大(小)（强）连通子图的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

一图搞清楚(非)(强)连通图中的极大(小)（强）连通子图