连通（无向图）与强连通（有向图）
有向图与无向图之间的连通，强连通
连通图（无向图）与强连通图（有向图）
连通图与强连通图
常考考点：n个顶点的连通图(强连通图)最少有多少条边
无向图，有向图的最少边数
连通分量与强连通分量：这里一定要搞明白
无向图
左边的图为原图，右边的四个为连通子图，我们要找的是连通分量=>极大连通子图。在这里很清楚的看到圈出来的两个图，没有更大的连通子图，把它们包含起来。所以圈出来的就是极大连通子图
有向图
右边的四个图为强连通图的强连通子图，圈出来的即为强连通分量=>极大强连通子图
结论：
- 如果原图是一个连通图或者强连通图，那么它的连通分量或者强连通分量都是与原图一样的。
- 如果原图不是一个连通图或者强连通图，那么它的连通分量或者强连通分量会有许多个
极小连通子图
极小连通子图示意图
生成树
生成树示意图
这里注意一点，生成树是包含多有顶点的一个极小连通子图，而且是不唯一的。
n个顶点图的生成树有n-1条边
生成森林
连通图只能生成树，非连通图则可以生成森林
生成森林图示
顶点的度
以该顶点为一个端点的边的数目
有向图和无向图的度
- 无向图中顶点的度就是连接该顶点的边数
- 有向图中顶点的度=出度+入度
网
即每个边都有一个权值
网示意图
稠密图和稀疏图
稠密图和稀疏图示意图
有向树
有向树示意图
有向树跟树的区别是：有向树是图
若为树结构：第二层左边第一个结点的度为2
若为有向树结构：第二层左边第一个结点的度为3
网友评论