图的基本概念2

连通（无向图）与强连通（有向图）

有向图与无向图之间的连通，强连通
连通图（无向图）与强连通图（有向图）
连通图与强连通图

常考考点：n个顶点的连通图(强连通图)最少有多少条边

无向图，有向图的最少边数
连通分量与强连通分量：这里一定要搞明白
无向图
左边的图为原图，右边的四个为连通子图，我们要找的是连通分量=>极大连通子图。在这里很清楚的看到圈出来的两个图，没有更大的连通子图，把它们包含起来。所以圈出来的就是极大连通子图
有向图
右边的四个图为强连通图的强连通子图，圈出来的即为强连通分量=>极大强连通子图
结论：

• 如果原图是一个连通图或者强连通图，那么它的连通分量或者强连通分量都是与原图一样的。
• 如果原图不是一个连通图或者强连通图，那么它的连通分量或者强连通分量会有许多个

极小连通子图

极小连通子图示意图
生成树
生成树示意图
这里注意一点，生成树是包含多有顶点的一个极小连通子图，而且是不唯一的。
n个顶点图的生成树有n-1条边

生成森林
连通图只能生成树，非连通图则可以生成森林

生成森林图示

顶点的度
以该顶点为一个端点的边的数目

有向图和无向图的度

• 无向图中顶点的度就是连接该顶点的边数
• 有向图中顶点的度=出度+入度

网
即每个边都有一个权值

网示意图

稠密图和稀疏图

稠密图和稀疏图示意图

有向树

有向树示意图
有向树跟树的区别是：有向树是图
若为树结构：第二层左边第一个结点的度为2
若为有向树结构：第二层左边第一个结点的度为3