图论1-1 图的介绍
图可以表示生活中的许多东西，它是由一个点集以及点集中一些点对的连线构成。如一个人就可以表示成一个点，两个点之间的连线表示朋友关系等。
1.1 图的基本介绍
图（Graph）是由一个点集（vertices, V）和一个边集（edges, E）构成，表示为 G(V, E)。
有时候，图也被定义为一个有序三元组 $(V(G),E(G),\phi_G)$，其中 $\phi_G$被称为关联函数，$\phi(e)=uv$表示边$e$连接$uv$两个顶点。
- 顶点：是图的基本要素，也叫做节点（node）。顶点可以带有标记也可以不带。
- 边：用于连接任意两个顶点（也可以自己连自己）， 有时候边也叫做弧（arc）。
- 顶点数：$\upsilon$；边数：$\varepsilon$
- 如果两个图 G 和 H，有$V(G)=V(H),E(G)=E(H),\phi(G)=\phi(H)$，则这两个图** 恒等**$G=H$。
- 如果两个图 **只有 **边和顶点的标号不同，则这两个图 同构$G\cong H$
例：
- 一条边的顶点与这条边称为关联，反之亦然。
- 与同一条边关联的叫做相邻，反之亦然。
- 端点重合为一个点的边称为环，上图顶点6就存在一个环。
1.2 图的种类
1. 空图（Null graph）
没有边的图叫做空图。
2. 平凡图（Trivial Graph）
只有一个顶点的图叫做平凡图，它是最小的图。其他的所有图都叫做非平凡图（Nontrivial graph）。
3. 无向图（Undirected Graph）
边没有方向的图叫做无向图。
4. 有向图（Directed Graph）
边有方向的图叫做有向图。
5. 连通图（Connected Graph）
从一个点开始，可以访问到其他任意点的图叫做连通图。
6. 非连通图（Disconnected Graph）
从一个点开始，不能访问到其他任意点的图叫做连通图。
7. 正则图（Regular Graph）
每个顶点度都相同的图叫做正则图。每个顶点度为 K 的图叫做 K-正则图（K-Regular）
8. 完全图（Complete Graph）
每个顶点都与其他顶点相邻的图叫做完全图，完全图是一个$\upsilon-1$正则图。
9. 圈图（Cycle Graph）
如果一个图自身就是一个环，就叫做圈图，也称为自环。
10. 有环图（Cyclic Graph）
一个图至少含有一个环，称为有环图。
11. 无环图（acyclic graph）、
一个图不包含环，称为无环图。
12. 有向无环图（Directed Acyclic Graph）
一个有向图不包含环，称为有向无环图。
13. 二分图（Bipartite Graph）
如果一个图的顶点可以分成两个集合，且每个集合内部的顶点之间不存在边，这样的图叫做二分图，也叫做二部图。
14. 简单图（Simple graph）
如果一个图既没有环也没有重边，叫做简单图。
1.3 一个结论
如果 G 是简单图，则$\varepsilon\leq C_\upsilon^2$
1.4 图的表示
在数据结构中，图有两种表示方法。
1. 邻接矩阵（Adjacency Matrix）
使用一个二维的矩阵表示图，矩阵的行和列都为顶点编号，若顶点$1,2$直接有一条边，则矩阵的位置$(1,2)$置一。
2. 邻接表（Adjacency List）
每一个顶点对应一个链表，链表的头节点为顶点编号，后面的节点为相邻的顶点。
3. 两种数据结构对比
当图含有较多边的时候，建议使用邻接矩阵。
| 邻接矩阵 | 邻接表 | |
|---|---|---|
| 添加一条边 | $O(1)$ | $O(1)$ |
| 删除一条边 | $O(1)$ | $O(n)$ |
| 初始化 | $O(n^2)$ | $O(n)$ |
参考资料：https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/
