离散数学（图论）笔记

词汇

英文试卷，实在头大。

infinite graph：无限图

finite graph：有限图

simple graph：简单图

multiple edge：多重边

multigraph：多重图

pseudograph：伪图

undirected graph：无向图

directed graph：有向图

multiplicity：重数

Acquaintanceship Graph：表示人认识关系的无向图

Friendship Graph：同 Acquaintanceship Graph

Influence Graph：表示人相互影响的有向图

Collaboration Graph：表示协作关系的简单无向图

Call Graph：调用图，属于有向图。

Web Graph：属于有向图。

Citation Graph：引用图，有向，无多重边和圈。

underlying undirected graph：基本无向图，把有向图的方向忽略得到的图。

complete graph：完全图

cycle：圈图

wheel：轮图

n-cube：立方图

bipartite：二分图

complete bipartite graph：完全二分图

subgraph：子图

proper subgraph：真子图

subgraph induced：导出子图

edge contraction：通过合并点来构造新的图

基础概念

图（Graph）：顶点（Vertex）加上顶点之间的连线（边（Edge））。

记作： $G = (V,E)$ 。顶点记作： $G(V)$，边记作 $G(E)$ 。

无限图：顶点或边有无数条

多重边：如果 $V_1\to V_2$ 有两条边，则是多重边。注意，下面这种情况不算多重边：

多重图： 有 多重边 的图。

重数：两结点间平行边的条数称为平行边的重数。

伪图： 有环或者多重边的图

上面的圈圈叫做环。

有向图：

简单图：没有 环 和 多重边 的图。

简单有向图：没有 环 和 多重边 的有向图。

邻接、相邻：一条边的两个顶点相邻。

邻居：与 $v$ 相邻的所有点的集合。记作 $N(A)$

度：进出 $v$ 的边数。比如环对度数的贡献是 2. 普通边的贡献是 1. （注意：无向图的边的度数贡献是 1，而不是当作双向的2）

孤立顶点：度数 0 的顶点。

悬挂顶点：度数 1 的顶点。

入度：进入顶点的边数。记作 $\operatorname{deg}^- (v)$ 。

出度：离开顶点的边数。记作 $\operatorname{deg}^+ (v)$ 。

完全图(Complete graph)：任意对不同顶点都相连的简单无向图。根据顶点的个数 $k$ 记作 $K_n$ 。

圈图（Circle graph）：自己看图就懂了：

记作 $C_n$ 。

轮图（Wheel graph）：中间带个轴心。

记作 $W_n$

立方图（Cubic graph）：

记作 $Q_n$

二分图（Bipartite graph）：说白了就是能构成映射的图。

• 判断二分图的方法

完全二分图：

设 $G(V,E)$ 为某一图。

子图：节点集和边集分别是 $G$ 节点集的子集 和 边集的子集的图。

生成子图：含有 $G$ 所有顶点的子图。

导出子图：也称顶点导出的子图。给一组顶点，与这些顶点所带的边构成的图。

假设 $G$ 为：

则顶点 e, c, b 的导出子图是：（不一定刚好构成路径哈，下面只是巧合）

主子图：

---

匹配问题：

两个二分图的可能连线情况如下：

匹配：一个连线方式是上面的所有连线可能性的子集，每个顶点都直连向一个对面的顶点，则这种连接方式是一个匹配。

最大匹配：连接的边数最大的那种匹配。

完全匹配：连接刚好构成一一对应（双射）的匹配。

---

霍尔定理：记 $N(A)$ 是 A 的所有邻居。存在 $V_1 \to V_2$ 完全匹配的充要条件是：对于所有 $V_1$ 的子集， $\left| N(A) \right| \leqslant \left| A \right|$

邻接表：一种通过每个顶点的邻居的图表示法。

邻接矩阵：类似关系矩阵。 $a_{ij} = 1$ 表示 $v_i \to v_j$ 的边存在。

关联矩阵：通过顶点和边的连接关系矩阵来描述无向图。

图的同构：如果两个图能扭成一个模样就是同构。严谨点说是存在 $G_1 \to G_2$的映射 $f$ 使得顶点映射过去后，边的连接关系不变。

通路：经过一系列顶点的边的序列。

连通图和不连通图：看下面的图就懂了：

连通分支：看下面的图就懂了：

割点：如果一个顶点连同它的相关边删除掉，会产生更多连通分支，这个点就是割点。

比如这个 $c$ 点。

不可分割图：没有割点的图。

连通度：最少删除 $k$ 个割点能变成不连通图，那么这个图连通度是 $k$ 。

割边：如果一个边被删除之后，会产生更多连通分支，那么这个边就是割边。

边连通度：同理。

强连通：有向图任意 $a,b$ 两点均有 $a\to b, b\to a$ 的通路，则该图是强连通的。

弱连通：有向图去掉方向之后任意 $a,b$ 两点均存在通路，则是弱连通的。

强连通分支：有向图的极大强连通子图。

欧拉回路问题：能否从一个顶点出发，沿着图的边前进，恰好经过图的每条边一次并且回到出发点？

欧拉回路定理：连通多重图中存在欧拉回路当且仅当图中所有顶点的度数为偶数。

哈密顿回路问题：能否从一个顶点出发，沿着图的边前进，恰好经过图的每个顶点一次并且回到出发点？

加权图：给每条边赋予权重（例如表示距离）的图。

最短通路算法：就是寻找开销最小的路径的算法。（开销用权重之和表示）

• Dijkstra 算法
• Floyd 算法
• A* 算法

平面图：如果一个图存在一种表示形式使得其可以铺平后没有交叉，则是平面图。

平面图欧拉公式：设平面图 G，有 $e$ 条边，$v$ 个顶点，则 $v+r = e+2$。面数等于边数减顶点数加二。推荐阅读：经典证明：不用数学归纳法直接推导平面图的Euler公式。记忆的话可以用三角形这个特例，两面三点三边。

面的度：面的边界上的边数。

$e\leqslant 3v -6\ (v\geqslant 3)$

初等细分：通俗地说就是在平面图的某一条边上加个起到分割作用的顶点。

同胚：若 $G_1$，初等细分得到 $G_2,G_3$，则 $G_1, G_2, G_3$ 是同胚的。

库拉图斯基定理：一个图是非平面图 $\Leftrightarrow$ 它包含一个同胚于 $K_{3,3}$ 或 $K_5$ 的子图。（注：$K_5$ 是5阶完全图，$K_{3,3}$ 是各三个顶点的二部图）。

图着色：给每个顶点指定一种颜色，使得任意相邻顶点的颜色不同。

图着色数：给图着色所需的最少颜色数。记作 $\chi(G)$。

四色定理：平面图的着色数不超过 4.

• 完全二分图的着色数是 2.

常用算法

判断二分图

着色法：只用两种颜色，能否保证给所有点染色时，任何相邻两个点的颜色不同，可以的就是二分图。染色可以用广度优先和深度优先两种顺序。（原理：完全二分图的着色数是 2.）

Dijkstra 寻路算法的工作原理

详见此文。一句话解释就是：找到与起点相邻最近点，再把这个点与源点看做一个整体，作为新的起点，重复步骤，直到抵达目标。

Floyd 算法的工作原理

一句话解释就是：先用一个邻接矩阵，只存放相邻点的数据。不相邻的点记为 $\infty$。然后分别地使用各个点 $P_i$ 建立 $P_i$ 相邻点之间的线索，直到所有点完成这样的操作。可参考此文。

TSP（行商）问题

问题描述可直接看此处。

参考：https://zhuanlan.zhihu.com/p/161082172