小朋友都会的图论

图

相比前面的抽代，这里总算是休闲难度了

图的很多有关定义

我觉得吧，实在没有必要说什么是图了，计算机专业不懂图的话确实有点难办

图的结点数叫做图的阶数，阶数是几就叫几阶图；序偶是有序的，但是专家还是了发明一种无序序偶，记作 $(x,y)$ ，无序积则是两个集合中的元素分别组成的无序序偶的集合，记作 $A\&B$ ， $A\&B=\{ (x,y)|x \in A, y \in B \}$

各种边和图

有向边，无向边都是老生常谈的东西的，一个端点连着的边叫做它的关联边

如果一条边两头连在一个点上面，那这条边叫这个点的自环，如果两个点之间有重复的边，那这些边叫平行边或重复边，其数量叫做边的重数，有平行边的图叫多重图，没有平行边和自环的图叫简单图，如果简单图的任意两个点都有边连接，那这个图又叫完全图

无向图，有向图，无向简单图，有向简单图，无向完全图，有向完全图都是一看就懂什么意思的，混合图指的是同时有有向边和无向边的图

如果图 $A$ 是图 $B$ 的一部分，那 $A$ 就是 $B$ 的子图，如果 $A$ 有 $B$ 的全部结点，那 $A$ 是 $B$ 的生成子图 ，还有个东西叫导出子图，就是拿一组点或者一组边，然后加上那些点之间的边或者那些边连的点，得到的子图就是导出子图了

一个结点连了几条边，那它的度数就是几，记作 $\deg(v)$ ，如果是有向边，还要分为入度和出度，记作 $\deg^+(v)$ 和 $\deg^-(v)$

度数为 $1$ 的结点叫做悬挂节点，对应的边叫做悬挂边

显然，图的总度数是边数的两倍，在所有图中度数是奇数的点都是偶数个

如果你有两个分子，这两个分子虽然画出的结构式不一样，但实际上是完全相同的物质，那我们可以说这两个分子的图同构 ~~（虽然但是这是我能想到最简单表示同构概念的方法了~~ ，写作 $A \cong B$

[!tip] 代数系统的同构也是用这个全等符号表示（不知道为什么专家没加上去

所以啊，同构就是全等

路在脚下

一个点到另一个点的路径就是通路，没有相同边的叫简单通路，没有相同点的叫初级通路或者基本通路

一个大学生应该能猜出什么是回路，回路同样有简单回路和初级回路或基本回路

有一些非常显然的结论就不写了

学过语文的应该都知道一个点到另一个点是可达的是什么意思

如果图里面每个点都可以去到任何一个点，那这个图叫连通图

无向图里面每一块连通的部分导出的子图叫做它的连通分支，连通分支的数量叫做连通分支数

对于有向图，如果只是把每个点连起来但不一定通，那这就是个弱连通图或者直接叫连通图，如果任何两个点之间至少有一个点能去另一个点，这就是个单向连通图，如果像无向图那样畅通无阻的话就叫强连通图

显然一个有向图只要有一条能经过全部结点的回路就是强连通图了，如果只是通路那就是单向连通图

如果有向图 $G$ 的子图 $G'$ 是弱连通的，且 $G$ 的其他子图 $G'' \supset G'$ 都不是弱连通的，那 $G'$ 就是 $G$ 的极大弱连通子图，同理也有极大单向连通子图和极大强连通子图

加加减减

对图删除边和删除结点应该都会，而收缩边指的是两个连在一起的点合二为一 ~~（唉我懒得画图了~~

计算机如何看图

图可以用图形，可以用集合，也可以用矩阵

首先上场的是关联矩阵，记作 $\boldsymbol{M}(G)$ ，它的每列都代表一条边，每行代表一个点，值为 $1$ 表示这条边在这个点上，下面是一个关联矩阵的例子

\boldsymbol{M}(G)=\begin{bmatrix} 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}

真是又臭又长呢

接下来登场的是 OI 选手最熟悉的邻接矩阵，记作 $\boldsymbol{A}(G)$ ，就是说一个点到另一个点有几条边连接，具体点就是行所对应的点到列所对应的点的边数

\boldsymbol{A}(G_1)=\begin{bmatrix} 1 & 3 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix}, \boldsymbol{A}(G_2) = \begin{bmatrix} 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix}

还有一位是可达矩阵，记作 $\boldsymbol{D}(G)$ ，顾名思义就是行所对应的点是否能到列所对应的点

\boldsymbol{D}(G)=\begin{bmatrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ \end{bmatrix}

额这样是不是不太好（

算了就这样吧（

当脚下的路有了距离

如果图的每条边都有了对应的长度，那这个图就是赋权图，还有个东西叫边权矩阵，记作 $\boldsymbol{B}(G)$ ，如果行代表的点能到列所代表的点，那数值就是对应的边权，否则是 $\infty$

\boldsymbol{B}(G)=\begin{bmatrix} 0 & 1 & 4 & \infty & \infty & \infty \\ 1 & 0 & 2 & 7 & 5 & \infty \\ 4 & 2 & 0 & \infty & 1 & \infty \\ \infty & 7 & \infty & 0 & 3 & 2 \\ \infty & 5 & 1 & 3 & 0 & 6 \\ \infty & \infty & \infty & 2 & 6 & 0 \end{bmatrix}

↑这是个无向图的边权矩阵，很容易发现它是对称矩阵

迪杰斯特拉

Dijkstra 算法（唉这名字怎么这么怪）是拿来求一个点到图上其他点的最短路径的算法，其过程是非常的贪心啊

过程如下：

开两个数组，一个 $S$ 存已遍历的结点，一个 $L$ 存到各点的距离， $L$ 的所有项（除了开始那个点）都初始化为 $\infty$
最开始的点距离初始化为 $0$ ，更新与其邻接的点的距离，对应L[i]新值为min(正在遍历的点的距离 + 边权, L[i])，然后把现在这个点加入 $S$
之后继续遍历未遍历的点中L[i]最小的点，一个一个看直到所有点都到了 $S$ 里面
这时 $L$ 里面的值都是最小的了

代码以后再补

欧拉：你好

小学生都知道什么是欧拉图，就是一个有不重复走完全部边的回路的图，也就是有欧拉回路的图，如果一个图只有欧拉通路，这个图只能叫半欧拉图

只有无向连通图的奇度数结点为 $0$ 或 $2$ 个时，这个图才有欧拉通路

如果全部结点度数都是偶数，那这个图有欧拉回路

如果一个有向连通图每个结点的入度等于出度，那这个图也有欧拉回路

弗罗莱

Fleury 算法是用来求欧拉图里面的欧拉回路的，其思想要领是：从某个点开始走，走过哪条边就删掉那条边，优先走不会改变图的连通性的边。等到所有边都走完了就可以输出路径了

就这么简单

有时间可以整个代码（？

哈密顿：你好吗

小学生也应该知道什么是哈密顿图，就是一个有不重复走完全部点的回路的图，也就是有哈密顿回路的图，如果一个图只有哈密顿通路，这个图只能叫半哈密顿图

这玩意比欧拉图难判断多了，怎么才能简单地拿下，专家也说不准

如果一个 $n$ 阶无向简单图中随便两个不相邻点的度数和 $\geq n-1$ ，那它有哈密顿通路，如果 $\geq n$ ，那它有哈密顿回路

如果图中每个点都有 $\deg(v) \geq \frac{2}{n}$ ，那它也有哈密顿回路

这玩意……应该不太会考吧（