前言

之前有一篇图论，但是比数学书还简介（数学书至少有例题），且图片大量丢失。为了迎接接踵而至的图论算法，重新梳理一些知识。

这一篇会非常枯燥无味

---

图的基本信息

定义

图，就是一张图。 用教科书一些的话来说就是：

$$\boxed{ \begin{aligned} & \text{一个有序对 }G = (V,E)\text{，其中：} \\ & V \text{ 是非空的顶点集（所有点的集合）。} \\ & E \text{ 是边集（所有连线的集合），每条边对应 } V \text{ 的一对顶点。} \end{aligned} } \\ \texttt{（来自\color{#3964FE} DeepSeek\color{NULL}）}$$

通俗地来说，就是一堆点，点之间有连线。例如这是一个图：

应用

图可以应用在网络、路线规划、朋友圈这一类有节点和边的关系的问题中。利用图可以更好地梳理节点之间的关系。

顶点和边

如定义所说，图由点，即节点（也叫顶点）和边构成。例如上面的图中，有节点 $\{1,2,3\}$，有边 $\{\{1,2\},\{2,3\},\{3,1\}\}$。

边可以分为有向和无向。就是有箭头和没有箭头。有向的边称为有向边，无向的边称为无向边。上面的图中的边就是无向的，称为无向图。如果加上箭头，就变成了下面这样：

像这样边都有向的图称为有向图。

那有没有既有有箭头的边，也有没有箭头的边的图（就是既有无向边，也有有向边的图）呢？当然有了，这种图成为混合图。当然，这样的图可以直接转化为有向图，只需要在无向边建两条相反的就行了。

度

在无向图中，与这个节点相连的边的数量就称为这个点的度。例如下面这张图：

其中节点 $1$ 的度为 $3$，节点 $2$ 的度为 $2$。

在有向图中，度还分为出度和入度。出度是从这个点出去的边，入度是进来这的点的边。例如：

其中 $1$ 点的出度、入度分别为 $2$ 和 $1$，$2$ 点的出度和入度都为 $1$。

权

有时会给边设置长度（当然可以是负数），这个长度可以表示路径长度、代价等。给边设置长度的图叫做带权图，反之就是无权图。

图的分类

利用上面的一些信息，可以大概得对图进行分类。

1. 无向/有向：

   • 无向图：边都是无向边的图；
   • 有向图：边都是有向边的图；
   • 混合图：既有有向边也有无向边的图。

2. 无权/有权：

   • 无权图：边没有权的图；
   • 有权图：边有权的图；
   • 这当然也可以混合，但通常题目会把无权统一设定为 $-1$、inf、$0$ 等。

3. 连通（无向）：

   • 连通图：任意两个点之间都存在至少一条路径
   • 非连通图：有些点之间不存在路径，可以分成多个连通分量（节点之间互相连通的子图）。

4. 连通（有向）：

   • 连通：
     1. 强联通：任意两点之间都双向连通（即 $u\to v$ 和 $v\to u$）
     2. 单向连通：任意两点之间单向连通（即存在 $u\to v$ 或 $v\to u$）
     3. 弱连通：视为无向图后连通。
   • 非连通：把有向图视为无向图后任然不连通。

5. 稀疏/稠密（没有明确界限）：

   • 稀疏图：边数相对较少
   • 稠密图：边数相对较多

6. 其他：

   • 完全图：任意两点之间都有边。
   • 二分图：可以把节点划分到两个集合，使每条边的两段都在不同的集合。
   • 剩下的就算了吧

图论

1. 一张图中，所有点的度数之和等于边数的两倍。（一条边会连接两个点，产生两个度）
2. 度数为奇数的点个数一定是偶数。（一进一出）

3. 欧拉路/欧拉回路（一笔画）

欧拉回路：从一点出发，可以经过所有边且回到原点。

• 无向图判断：所有点的度都是偶数。
• 有向图判断：所有点的出度和入度相等。

欧拉路：从一点出发，可以经过所有边。

• 存在欧拉回路就会存在欧拉路。
• 无向图判断：所有顶点的度中，有 $2$（一个作为起点，另一个作为终点）个为奇数。
• 有向图判断：所有顶点的出度和入度中，一个点出度比入度多一（作为起点），一个点入度比出度多一（作为终点）。

4. 完全图的边数为 $\dfrac{边数\times(边数-1)}{2}$。