图论

图的表示

图的分类
平凡图	由一个孤立点构成的图
简单图	无平行边，无环的图（注意有环的定义是存在某元素从自身到自身的边）
完全图	任意两节点都有边相连的简单图
连通图	对于有向图，分为单向连通（图中每两个结点可以通过一个方向可达）和强连通
欧拉图	有欧拉回路的连通无向图
平面图	在一个平面上，无向图 G 的图解中若没有任何边的交叉，则称图 G 是个平面图；否则，称 G 是非平面图

图的表示：邻接矩阵（和 DS 一样）

• 若上半部分均为 1，则单向连通
• 简单图的主对角线全为零（无环）
• 若邻接矩阵中G[i][j] = 1，则说明结点 i 和 j 之间存在通路
• 若邻接矩阵中G^k[i][i] = 1，则说明结点 i 之间存在长度为 k 的回路

将图的可达矩阵：和求二元关系的传递闭包一样一样的，就说有点熟悉

$$G_{可达} = \bigcup_{i=1}^n G^i=G∪G^2∪G^3∪...∪G^n$$

图的性质

握手定理：任意图的总度数是边数的两倍

树边和结点的关系：在树中，结点数始终比边数要多一个

欧拉通路与回路

• 存在欧拉通路（经过所有结点的简单通路，无重复边）的图只存在 0 或 2 个奇数度结点
• 存在欧拉回路（经过所有结点的简单回路，无重复边）的图（即欧拉图）不存在奇数度结点

注意，存在偶数个结点的欧拉图总边数可以是奇数，因为边数 = 总度数/2，而总度数一定为偶数个偶数的和（有偶数个结点且每个结点度数均为偶数，但最后是相加），偶数的和的二分之一有可能是奇数，如 1x2+1x4 = 6，而 6/2 = 3

二部图（偶图）

对偶图

平面图：对于连通的平面图，有 n-e+r = 2，即结点数减去边数加上面数始终等于 2

对偶图

图的完全匹配

连通性与割集

无向图的连通性很简单：任意两个结点之间可达

有向图的连通性分为三种情况

• 强连通：任意两个结点之间可达（如双向链表）
• 单向连通：任意两个节点之间单向可达（如链表）
• 弱连通：不满足单向连通，但失去方向后，是一个连通的无向图

在图的矩阵表示中较为明显，若上半部分全为 1，则为单向连通，若除主对角线全为 1，则为强连通

边割集与点割集（对于无向图而言）

1. 首先要求图是联通的
2. 其次，找到一组边集合，删去这组边后，图将恰好变的非连通，那么这个边集合即为该图的边割集（很多时候边割集不唯一）
3. 若某边割集仅含一个元素，那么这个边称为该图的割边

点割同理，只不过删的是结点（删结点时要删去所以何其相连的边）

对于一个图，定义其最小的点割集的基数为其点连通度，定义其最小的边割集的基数为其边连通度（基数即集合中元素个数）

• 显然具有割点、割边的图点连通度和边连通度均为 1

通路与回路

回路的进化历程（通路同理）

• 回路：出发点和终点相同，路径不做任何限制
• 简单回路：回路的基础上，路径中不经过相同的边
• 基本回路：回路的基础上，路径中不经过相同的结点（基本回路一定是简单回路）
• 欧拉回路：一条经过所有边的简单回路

欧拉通/回路与结点度数的关系

• 当一个无向图有欧拉通路，则其只有 0 个或 2 个奇数度结点
• 当一个无向图有欧拉回路，则其没有奇数度结点

欧拉图：具有欧拉回路的图

欧拉定理：对于连通平面图，其结点数 v，边数 e，面数 r 满足 v-e+r = 2

路径的长度：经过的边的个数

树和生成树

树是一种特殊的图

之前说过握手定理，图的度数是边数的两倍，同样适用于树，并且在树中，因为父亲结点只有一个，所以必然有边数等于结点数 -1

最小生成树

• 普利姆算法：从结点出发
• 克鲁斯卡尔算法：从边出发