【数据结构】—图的基本概念

1. 图不可以为空。有边集合和点集合组成。边集合可为空。
2. 简单图：边不重复、不存在定点到自身的边。
3. 入度：指向该点的 有几个；
   出度：从该点发出的 有几个。
   度：入度 + 出度。即由该点发出、指向该点的总数。
4. 子图：含有部分的顶点，部分的边。
   生成子图：每个点都有。
5. 无向完全图：任意两个顶点都存在边。
   有向完全图：任意两个顶点都存在方向相反的两条弧。
6. 连通：【对象：无向图】点v 到点w 有路径「可以连上，走得通」。
   连通图：【无向图中】任意两个顶点都连通。
   连通分量：无向图中的极大连通子图。（要连通、要尽量包含多的点和边）

对于 n 个顶点的 无向图

• 若连通，最少 n-1 条边。 //这个时候可以联想到树，n个顶点 n-1 条边。
• 若非连通，最多（n-1）*（n-2）/ 2条边。//怎么来的呢？n 个顶点，砍掉一个顶点，剩下的 n-1 个顶点连的死死的，有 (n-1) (n-2)/2 条边
• 无向图的顶点的度之和为 2e。

7. 强连通图：【对象：有向图】任何一对顶点都是强连通的
   强连通分量：有向图中的极大连通分量。（要连通、要尽可能的包含多的点和边）

n 个顶点的有向图

• 至少 n 条边。//形成了回路，每个点都能到其他点。

8. 有回路的图不存在拓扑排序。
9. 生成树不唯一，不存在回路，
10. 有向树：顶点入度为0，其余入度为1。