图论：图的基本概念

知识点

注：这部分内容参考Rosen. &屈婉玲.

知识梳理参考资料：

• 图论概念梳理 (yhx-12243.github.io)

• 《离散数学》学习记录 - 图论 - 知乎 (zhihu.com)

• Zifan的小站-离散数学

• 简单图 (Simple graph)：若一个图中没有*自环*和*重边*时，它被称为简单图

• 度序列：注意，度序列的顺序是根据标定的标号顺序排列的，而不是根据度升序。

• 有向图的度数列等于出度列+入度列（均取正值）。

• 补图：对于无向简单图 $G=(V, E)$ ，它的补图 (Complement graph)指的是这样的一张图，记作 $\bar{G}$ ，满足 $V(\bar{G})=V(G)$ ，且对任意顶点对 $(u, v)$ ， $(u, v) \in E(G)$ 当且仅当 $(u, v) \notin E\left(G^{\prime}\right)$ 。

• 有向图中的平行边要求起点和终点都要相同。

• $k-$正则图：各点的度都为$k.$

• $k-$连通图：最小点连通度$\ge k$，这意味着去除任何$k-1$个点得到的导出子图都是连通的。去除$k$个点未必（不一定就是需要的那k个点，也不一定最小点连通度就是k）。

• 无向图短程线$d(u_i, v_i)$，有向图短程线$d<u_i,v_i> <span class="arithmatex"><span class="MathJax_Preview">不一定等于</span><script type="math/tex">不一定等于$d.d. 无向完全图、有向完全图中任意两点的短程线都为1，但是竞赛图中任意两点的短程线是不定的。

图的连通性

对于任何的无向图G，有 $$ \kappa(G) \leqslant \lambda(G) \leqslant \delta(G) $$

图的矩阵表示

关联矩阵

$$M = (a_{ij})_{m\times n}表示G = <V,E>,|V| = m, |E| = n, a_{ij}表示边E_j与点V_i的关联次数.$$

邻接矩阵

$$M = (a_{ij})_{n\times n}表示D = <V, E>,其中a_{ij}表示点V_i邻接到V_j的次数.$$

注意：有向图的临界矩阵不一定是对称阵！无向图的临界矩阵一定是对称阵。

对于有向图，每行元素之和$\sum_{j = 1}^na_{ij}$表示第$i$个元素的**出度**，每列元素之和$\sum_{i = 1}^na_{ij}$表示第$i$个元素的**入度**。

可达矩阵

扩大路径法

图的同构

• 如何判断两个图是否同构？

必要条件：

• 相同的度序列

充要条件：能够找到双射

• 如何全面的枚举所有非同构的图？

参考阅读：非同构图介绍及其获取方案 - 知乎 (zhihu.com)

• 一个trick ：$G_1 \cong G_2 \iff \overline{G_1} \cong \overline{G_2}.$这意味着可以从补图突破。

图的连通性

割点

• 等价表述：$p(G-v) > p(G).$

割边

• 等价表述： $p(G-e) > p(G).$

一些概念的区分

零图 平凡图 空图

• 零图: 边集为空的集合 n阶零图记为$N_n$

• 平凡图：一阶零图$N_1，即只有一个点，没有边的图

• 空图：图的定义中规定顶点集$V$为非空集，但在图的运算中可能产生顶点集为空的运算结果，因此规定顶点集为空的图为空图，记为 $\varnothing.$

邻域 闭邻域

• 无向图 邻域：与u相邻的点构成的集合为u的邻域

• 无向图 闭邻域：在邻域基础上包括u自身

• 无向图 关联：与u关联的边的集合

• 有向图 后继：从u出发达到的点

注：根据屈婉玲版本，若存在自环，后继和前驱中是**不包括自身**的。推测无向图中若存在自环，邻域中应该也不包含自身。

• 有向图 前驱：可到达u的点

• 有向图 邻域：后继和前驱的并集

• 有向图 闭邻域： 邻域基础上加上自身

有向完全图 竞赛图

二者都是有向简单图。

• 有向完全图：任意两个点之间都有**双向的**边。
• 竞赛图：基图（有向图去掉所有的方向退化为的无向图）为完全图的有向图，这意味着任意两点之间有且仅有一条边。

回路 简单回路 初级回路（圈） 环 自环

• 途径 (Walk): 一个点和边的交错序列，其中首尾是点 $-v_{0}, e_{1}, v_{1}, e_{2}, v_{2}, \cdots, e_{k}, v_{k}$ ，有时简写为 $v_{0} \rightarrow v_{1} \rightarrow v_{2} \rightarrow \cdots \rightarrow v_{k}$ 。其中 $e_{i}$ 的两个端点分别为 $v_{i-1}$ 和 $v_{i}$ (以下默认设 $w=\left[v_{0}, e_{1}, v_{1}, e_{2}, v_{2}, \cdots, e_{k}, v_{k}\right]$ 。
• 迹 (Trail)：对于一条途径 $w$ ，若 $e_{1}, e_{2}, \cdots, e_{k}$ 两两互不相同，则称 $w$ 是一条迹。
• 路径 (Path) (又称简单路径 (Simple path))：对于一条迹 $w$ ，除了 $v_{0}$ 和 $v_{k}$ 允许相同外，其余点两两互不相同，则称 $w$ 是一条路径。
• 回路 (Circuit)：对于一个迹 $w$ ，若 $v_{0}=v_{k}$ ，则称 $w$ 是一个回路。
• 环圈 (Cycle) (又称简单回路 (Simple circuit))：对于一条简单路径 $w$ ，若 $v_{0}=v_{k}$ ，则称 $w$ 是一个环。

子图 生成子图 导出子图

• 子图 定义：子图G’中所有的顶点和边均包含于原图G。即E’∈E，并且V’∈V。

• 生成子图（Spanning Subgraph） 定义：生成子图G’中**顶点个数V’必须和原图G中V的数量相同**，而E’∈E即可。

• 导出子图(Induced Subgraph) 定义：导出子图G’，V’∈V，但对于V’中任一顶点，只要在原图G中有对应边，那么就要出现在E’中。

关联与邻接

• 关联(incident): 指一条边和一个点关联。
• 相邻、邻接(adjacent): 指两个点或者两条边相邻、邻接。

弱连通图 单向连通图 强连通图

• 弱连通图：基图为连通图。

• 单向连通图：任意两点之间至少有一个方向是可达的。

​ $D为单向连通图\iff D中存在经过每个点至少一次的通路.$

• 强连通图：任意两点之间两个方向可达。

$D为强连通图\iff D中存在经过每个点至少一次的回路．$

三者为递进关系。

习题选录（按照题型）

度序列

• 注意：无向图自环对度的贡献为2；有向图自环分别对出度和入度贡献1。

握手定理

1. 证明三维空间中不存在有奇数个面，且每个面都有奇数条棱的几何体。

2. 证明若无向图G中有且仅有两个奇度顶点，那么这两个顶点必然连通。

反证法，反设两个奇数度顶点不连通，那么G中可以找到两个独立的连通分量$G_A, G_B$，分别包含A、B，那么在这两个子图中，有且只有A或B为奇度顶点，而其他点都为偶度点，这与握手定理矛盾$\square.$

画出所有满足要求的非同构图问题

• 从度序列思考：可以有哪些不同的度序列？
• 思考每一种度序列会有几种非同构的图
• 对于稠密图，从反面思考，画它的补图的所有非同构图

完全图、正则图、补图

1. 讨论$k-$正则图的不同构的生成子图为正则图的种数。

注意：对于确定的k，不同构的正则不一定是唯一的！！

由握手定理，对于k为奇数的情况，其生成子图只能取到$0\sim n$中的偶数情况。

对于k为偶数的情况，其生成子图可以取到全部情况。

1. 结论： $\delta(G)+\Delta(\overline G) = n-1\\ \Delta(G) + \delta(\overline G) = n-1$
2. 设G是6阶无向简单图，证明：$G或它的补图\overline{G}中存在3个点彼此相邻.$

扩大路径法

1. 设G是无向简单图，$\delta(G) \ge 2$，证明：G中存在长度大于等于$\delta(G)+1$的圈。

**笔者解答**采用构造法证明。考虑最坏的情况。

构造一个顶点序列$\{u_1,u_2, \cdots,u_{\delta(G)},u_{\delta(G)+1}\}$，表示按照顺序不断加入新的点。在最坏的情况下，所有的新加入的点都尽可能不与外界的点相连，也就是保证与已经加入序列的点都有边的相连，，同时，所有的点的度都只有$\delta(G)$，那么依次会有$\{\delta(G),\delta(G)-1, \delta(G)-2,\dots, \delta(G)-\delta(G) = 0\}$个度是与外界相连的，可以发现直到第$\delta(G)+1$个点时，不再可以与外界相连，也就是说不能再新加入点了，而此时形成的最大圈长度为$\delta(G)+1.\square$

参考答案 用**扩大路径法**证明. 证明线索如下. 设 $\Gamma=v_{0} v_{1} \cdots v_{l}$ 为极大路径 (可用扩大路径法得到), 则 $l \geqslant \delta(G)$ (为什么?). 由极大路径的性质 $\left(\Gamma\right.$ 的两个端点 $v_{0}$ 与 $v_{l}$ 不与 $\Gamma$ 外顶点相邻) 以及简单 图茨定义可知, $v_{0}$ 要达到其度数 $d\left(v_{0}\right) \geqslant \delta(G)$, 必须与 $\Gamma$ 上至少 $\delta(G)$ 个顶点相邻, 设其为 $v_{i_{1}}=$ $v_{1}, v_{i_{2}}, \cdots, v_{i_{\delta}}$. 于是, 圈 $v_{0} v_{i_{1}} \cdots v_{i_{2}} \cdots v_{i_{\delta}} v_{0}$ 长度大于等于 $\delta(G)+1$, 式中的 $\delta=\delta(G)$. 参见主教材中的例 $14.8$.

图的连通性

1. 一个不是强连通图的单向连通图至少要加几条边，就能使之成为一个强连通图？

利用二者的充要表示。

• 单向连通图：任意两点之间至少有一个方向是可达的。

​ $D为单向连通图\iff D中存在经过每个点至少一次的通路.$

• 强连通图：任意两点之间两个方向可达。

$D为强连通图\iff D中存在经过每个点至少一次的回路．$

1. 证明$n阶(n \ge 2)$简单连通图G中至少有两个顶点不是割点。

$Pf.$首先证明两个命题：

1. 悬挂顶点不是割点。

2. 设G为n阶无向连通图，则在G中任何两个顶点之间加一条新边，所得的n阶图G'中的割点数小于等于G中的割点数。

利用**生成树**的思想，因为G连通，故G有生成树，设T为G中一颗生成树。由于$n \ge 2$，所以T中至少有两片树叶（两个叶节点），由命题1可知这些叶节点不是割点。当T加边还原成G时，由命题2可知，G中至少有两个点不是割点$\square.$

1. 设$D = <V,E>$是简单有向图，$\delta(G) \ge 2$，$\delta^-(G) > 0, \delta^+(G) > 0,$证明：D中存在长度大于等于$\max\{\delta^-(G),\delta^+(G)\}+1$的圈。

类似上题，可以证明 $$ (1)存在长度\ge \delta^-(G) + 1 的圈.\ (2)存在长度\ge \delta^+(G) + 1 的圈. $$ 因此得证。

1. 设G是n阶m条边的无向连通图，证明：$m \ge n-1.$

此题的结论是很直观的——我们似乎无法构造一个少于n-1条边的无向连通图。然而，这样的说明是缺乏说服力的。因此考虑数学归纳法，对n归纳： $$ (1)&Basis.n = 1, m = 0\to 平凡图，显然成立.\ (2)&I.H.设\forall n \le k时成立,\ (3)&I.S.n = k+1时,任取其中一点v,除去该点得到G' = G-v,G'的连通分支G_1, G_2, \cdots,G_s,1\le s \le \delta(G)\&设G_i的阶数和边数分别为V_i, E_i, V_i \le k,由归纳假设,E_i \ge V_i -1,\ & \Rightarrow \sum E_i \ge \sum V_i - s\ &又\because 删去的边E \ge \delta(G), \sum V_i = k, 1\le s \le \delta(G)\ &\Rightarrow m = E + \sum E_i\ge \delta(G) + k - s \ge k = (k+1) - 1\ &由(1)(2)(3),\square. $$

完全图与二部图

1. 在无向完全图中，寻找边数最多的生成子图，使得其成为完全二部图。

完全图转完全二部图的过程：

• 将顶点集划分为两个互补的顶点子集$V_1,V_2,|V_1| = r, |V_2| = s$
• 删去所有$e_i = {v_i, v_j}, v_i, v_j \in V_1或者\in V_2$

得到的完全二部图边数为$rs$，删去的边的数量为$C_r^2 + C_s^2.$

1. 完全二部图$K_{r,s}, r,s \ge 2$，则：

2. 含有多少个非同构的圈？$\min\{r,s\}-1$

3. 至多有多少个顶点彼此不相邻？$\max\{r,s\}$

4. 至多有多少条边彼此不相邻？

   考虑任意两条边$e_1 = \{u_1, v_1\}, e_2 = \{u_2, v_2\}$，注意到两个端点只要有一个是相同的， 那么两条边就相邻了，因此对于所有的边，它们处于$V_r,V_s$中的点要户部相同，因此至多有$\min\{r,s\}$条。

5. 点连通度$\kappa$为几？边连通度$\lambda$为几？$\kappa(K) = \min\{r,s\},\lambda(K) = \min\{r,s\}.$

邻接矩阵

1. 

图的应用

1. 有三个油瓶，分别是1斤装，7两装，3两装（注：一斤=十两）。现在一斤的瓶子里装满了油，另外两个是空瓶。如何用这3个油瓶将1斤油分成2个5两？至少进行多少次？

参考答案

将三个瓶子里油量写成三元有序对$(v_1, v_2, v_3),$则初始状态为（10，0，0），最终状态为（5，5，0），画出完整的**状态转移图**，如下图：

不难得出短程线，及最短距离9。

笔者解法 编程来处理

#include <bits/stdc++.h>
using namespace std;
typedef struct mm mm;
struct mm {
int a;
int b;
int c;
};//这里还发现一个坑：如果使用set，且类型为自定义的结构体时，需要重载operator<！！
//原因是set维护时会对数据升序处理，
bool operator<(const mm &a, const mm &b)  {
if(a.a != b.a) return a.a < b.a;
else {
  if(a.b != b.b) return a.b < b.b;
  else return a.c < b.c;
}
}
set<mm> s;
stack<mm> stk;
void foo(mm cur) {
if(cur.a > 0 &&  cur.b < 7) {
  int inc = min(cur.a + cur.b, 7) - cur.b;
  mm tmp = {cur.a - inc,  cur.b + inc, cur.c};
  if(s.find(tmp) == s.end()) {
      s.insert(tmp);
      stk.push(tmp);
  }
}
if(cur.a > 0 && cur.c < 3) {
  int inc = min(cur.c + cur.a, 3) - cur.c;
  mm tmp = {cur.a - inc, cur.b, cur.c + inc};
  if(s.find(tmp) == s.end()) {
      s.insert(tmp);
      stk.push(tmp);
  }
}
if(cur.b > 0 && cur.a < 10) {
  mm tmp = {cur.a + cur.b, 0, cur.c};
  if(s.find(tmp) == s.end()) {
      s.insert(tmp);
      stk.push(tmp);
  }
}
if(cur.b > 0 && cur.c < 3) {
  int inc = min(cur.c + cur.b, 3) - cur.c;
  mm tmp = {cur.a, cur.b - inc, cur.c + inc};
  if(s.find(tmp) == s.end()) {
      s.insert(tmp);
      stk.push(tmp);
  }
}
if(cur.c > 0 && cur.a < 10) {
  mm tmp = {cur.a + cur.c, cur.b, 0};
  if(s.find(tmp) == s.end()) {
      s.insert(tmp);
      stk.push(tmp);
  }
}
if(cur.c > 0 && cur.b < 7) {
  int inc = min(cur.b + cur.c, 7) - cur.b;
  mm tmp = {cur.a, cur.b + inc, cur.c - inc};
  if(s.find(tmp) == s.end()) {
      s.insert(tmp);
      stk.push(tmp);
  }
}
}
int ret = 100000;
int main() {
mm start = {10, 0, 0};
stk.push(start);
s.insert(start);
foo(start);
int cnt = 0;
while(!stk.empty()) {
  mm cur = stk.top();
  stk.pop();
  if(cur.a == 5 && cur.b == 5) {
      cout << cur.a << " " <<  cur.b << " " << cur.c << endl;
      ret = min(ret, cnt);
      cout << cnt << endl;
      cnt = 0;
  }
  else {
      foo(cur);
      cout << cur.a << " " <<  cur.b << " " << cur.c << endl;
      cnt++;
  }
}
cout << cnt << endl;
return 0;
}

输出结果（部分）：

7 0 3
7 3 0
4 3 3
4 6 0
1 6 3
1 7 2
8 0 2
8 2 0
5 2 3
5 5 0
cntLen = 9

1. 类似1的问题：（农夫、狗、羊、白菜过河问题）

有一个农夫带一只羊、一筐菜和一只狼过河.果没有农夫看管，则狼要吃羊，羊要吃菜.但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？

参考解答：

农夫、狼、羊、白菜（回溯法求解）