极大连通子图与极小连通子图（带图讲解）

极大连通子图与极小连通子图（带图讲解）

引用

CSDN

1.

https://blog.csdn.net/qq_37134008/article/details/85325251

在图论中，极大连通子图和极小连通子图是两个容易混淆但又非常重要的概念。本文将通过对比的方式，详细解释这两个概念，并通过示意图帮助读者更好地理解。

无向图

连通图

在无向图中，若从顶点V1到V2有路径，则称顶点V1和V2是连通的。如果图中任意一对顶点都是连通的，则称此图是连通图。（连通的无向图）

极大连通子图

1. 连通图只有一个极大连通子图，就是它本身。（是唯一的）
2. 非连通图有多个极大连通子图。（非连通图的极大连通子图叫做连通分量，每个分量都是一个连通图）
3. 称为极大是因为如果此时加入任何一个不在图的点集中的点都会导致它不再连通。
   下图为非连通图，图中有两个极大连通子图（连通分量）。
   

极小连通子图

1. 一个连通图的生成树是该连通图顶点集确定的极小连通子图。（同一个连通图可以有不同的生成树，所以生成树不是唯一的）
   （极小连通子图只存在于连通图中）
2. 用边把极小连通子图中所有节点给连起来，若有n个节点，则有n-1条边。如下图生成树有6个节点，有5条边。
3. 之所以称为极小是因为此时如果删除一条边，就无法构成生成树，也就是说给极小连通子图的每个边都是不可少的。
4. 如果在生成树上添加一条边，一定会构成一个环。
   也就是说只要能连通图的所有顶点而又不产生回路的任何子图都是它的生成树。
   

总结来说：极大连通子图是讨论连通分量的,极小连通子图是讨论生成树的。

强连通图

此外，还需要说明强连通图和极大强连通子图的概念。

强连通图

在有向图中，若对于每一对顶点Vi和Vj，都存在一条从Vi到Vj和从Vj到Vi的路径，则称此图为强连通图。（连通的有向图）

有n个顶点的强连通图最多有n（n-1）条标，最少有n条边。（4个顶点的强连通图图示如上图和下图）

极大强连通子图

1. 强连通图的极大强连通子图为其本身。（是唯一的）
2. 非强连通图有多个极大强连通子图。（非强连通图的极大强连通子图叫做强连通分量）

极小强连通子图

不存在这个概念