图论期末复习

教学云平台 (bupt.edu.cn)

第一章 图的概念

1.1 图的概念

• 若一群人中，凡相识的两人都无公共朋友，凡不相识的两人都恰有两个公共朋友，则每人的朋友数相等(相识者互为朋友)。
• 证明在任意 6 个人的聚会上，要么有 3 个人互相认识，要么有 3 个互不认识。

​ 证明：将 6 人编号为 \(ABCDEF\)，则对于 \(A\)，其余 \(5\) 人要么认识 \(A\)，要么不认识 \(A\)，要么存在 \(3\) 人 都认识 \(A\)，要么存在 \(3\) 人都不认识 \(A\)

​ 不妨设 \(BCD\) 都认识 \(A\)，考虑 \(BCD\) 是否相互认识。

​ 如果 \(BCD\) 之间互不认识，则 \(BCD\) 就是满足条件的 \(3\) 个互不认识的人。

​ 如果 \(BCD\) 存在两人相互认识，不妨设 \(B\) 认识 \(C\)，则 \(ABC\) 就是满足条件的 \(3\) 个互相 认识的人。

• Ramsey数进展：对称矩阵

  \(r, s\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)	\(9\)
  \(3\)	6	9	14	18	23	28	36
  \(4\)		18	25

1.2-1.3 图同构、子图

• 在人数大于 1 的任何一个群体中，一定有两个或者两个以上的人在该群体中有相同的朋友数。

  \(n\) 个点的简单图，点的度数至多为 \(n-1\)，至少为 \(0\)，取值范围是 \([0, n-1]\)，而 \(0\) 和 \(n-1\) 不会同时取得，因此，在一个图中至多有 \(n-1\) 种度数的取值，有 \(n\) 个点，所以一定有两个或者两个以上的点度数相等。

• 证明：如果一个图与其补图同构，则 \(n \equiv 0 \bmod 4\) 或者 \(n \equiv 1 \bmod 4\)

​ 设原图边数为 \(m\)，则补图边数也为 \(m\)，完全图的边数为 \(\frac{n(n-1)}{2}\) 则有：\(2m = \frac{n(n-1)}{2}\)

​ 因此有 \(n(n-1) = 4m\)

​ 所以 \(n \equiv 0 \bmod 4\) 或者 \(n \equiv 1 \bmod 4\)

• \(\delta\) 表示最小度，\(\Delta\) 表示最大度，\(\varepsilon\) 表示边数，\(v\) 表示点数，则有 \(\delta \le \frac{2\varepsilon}{v} \le v\)

• 设平面上有 \(n\) 个点，其中任意两点之间何距离大于或等于 \(1\) ，证明：最有 \(3n\) 对点的距离等于 \(1\)。

​ 在一个单位圆上，至多有 \(6\) 个圆上的点相互之间的距离等于 \(1\)（每相邻的一对点和圆心组成等边三角形，角度为 \(60\) ）

​ 将距离等于 \(1\) 的两点之间连一条边。一共有 \(n\) 个点，每个点的度数至多为 \(6\).

​ 因此有 \(|E| \le 6n\)，即至多 \(3n\) 对点距离等于 \(1\)

1.4-1.6 路和连通性、圈、图的数据结构

• 一些概念：

  • 途径：允许边和点重复。
  • 迹：不允许边重复，允许点重复。
  • 路：不允许边和点重复。
  • 距离：最短路的长。

• 在简单图 \(G\) 中，若 \(\delta \ge k\)，则图 \(G\) 中有长度至少为 \(k\) 的路。

  证明：若图中的最长路的长度小于 \(k\)，不妨设最长路序列为 \(P_1P_2\cdots P_n\)，其中 \(n \le k\)

  由于 \(\delta \ge k\)，因此终点 \(P_n\) 至少有 \(k\) 个邻居，由于 \(n \le k\)，即 \(P_n\) 的邻居至少有一个不在序列中，将其作为终点得到的路会更长，这就产生矛盾。

• \(G\) 连通 \(\Leftrightarrow\) 对 \(\forall S \subset V\) 都有 \([S, \overline{S}] \ne \varnothing\)

• 设有 \(2n\) 个电话交换台，每个台与至少其他 \(n\) 个台有直通线路，则该交换系统中任二台均可实现通话。

  证明：原题表示为简单图 \(G\) 有 \(2n\) 个顶点，且最小度数为 \(n\)，求证图 \(G\) 连通。

  假设图 \(G\) 不连通，则至少存在 \(2\) 个连通分量，至少有一个连通分量的顶点数不超过 \(n\)，而对于一个 \(n\) 个顶点的图，度数的最大值为 \(n-1\)，这就产生矛盾，因此假设不成立。

• 若图 \(G\) 连通，且对 \(\forall v \in V\)，\(d(v)\) 为偶数 \(\Rightarrow\) \(\omega(G-v) \le \frac{d(v)}{2}\)。其中 \(G-v\) 表示图 \(G\) 删去点 \(v\) 得到的图，\(\omega\) 表示连通分量的数量。

• 连通图中，任二最长路必有公共顶点。

• 竞赛图：在无向完全图中为每个边分配一个方向，得到竞赛图。

• \(G\) 为二分图 \(\Leftrightarrow\) \(G\) 不含长度为奇数的圈

• 若简单图 \(G\) 中 \(\delta \ge 2\)，则 \(G\) 含长度大于 \(\delta\) 的圈。

  证明：从图中任意选取一个点开始双向扩展路径，直到无法再扩展，此时得到一条路径 \(P = P_1P_2\cdots P_k\)，由于 \(\delta\) 表示最小度数，则 \(P_k\) 至少有 \(\delta\) 个邻居。

  又因为路径 \(P\) 无法再扩展，所以 \(P_k\) 的所有邻居都在路径 \(P\) 当中。取其中标号最小的邻居，记为 \(P_i\)，则有圈 \(C = P_iP_{i+1}\cdots P_kP_i\)，这个圈的长度至少为 \(\delta + 1\)

第二章 最短路问题

第三章 树

3.1 树的概念

• 每棵非平凡树至少有两个度为 \(1\) 的顶点（悬挂点）。

  证明：设任意非平凡树有 \(n(n > 1)\) 个点，其中有 \(k\) 个点的度数为 \(1\)，其余的 \(n-k\) 个点度数大于 \(1\)

  根据握手定理有 \(2m = 2n-2 \ge k + 2(n-k) = 2n-k\)，即 \(k \ge 2\)

• 恰只包含两个度为 \(1\) 顶点的树是路。

  证明：由上一个推论可知，如果其余的 \(n-2\) 个点的度数都等于 \(2\)，则此时恰好有 \(2\) 个点的度数为 \(1\)，此时树的形状为一条直线，也就是一条路。

• 图 \(G\) 是树，则图 \(G\) 要么只有一个中心点，要么有两个相邻的中心点。

3.2 生成树、余树和键

• 设 \(T\) 为连通图 \(G\) 的一个生成树， \(e\) 为 \(T\) 的一条边，则：

  • 余树 \(\overline{T}\) 不包含 \(G\) 的键；
  • \(\overline{T} + e\) 中唯一包含 \(G\) 的一个键。

• 设 \(F\) 是 \(G\) 的极大林，则：

  • 对 \(G\) 的每个分支 \(H\) ， \(F\cap H\) 是 \(H\) 的生成树；
  • \(\varepsilon(F) = v(G) - \omega(G)\)。

• 任一图 \(G\) 至少包含 \(\varepsilon - v + \omega\) 个不同的圈。

• 若 \(G\) 的每个顶点均为偶点（即度为偶数的顶点），则 \(G\) 没有割边

  证明：假设图 \(G\) 的某条边 \((u, v)\) 是割边，删去这条边后将图分为两个连通分量 \(X\) 和 \(Y\)，其中 \(X\) 是包含了点 \(u\) 的连通分量。

​ 则在 \(X\) 中，除了点 \(u\) 其余的点的度数都是偶数，只有点 \(u\) 的度数是奇数，这与握手定理矛盾。因此假设不成立。

• 若 \(G\) 是 \(k\)-正则偶图且 \(k \ge 2\) ，则没有割边。

  证明：假设图 \(G\) 的某条边 \((u, v)\) 是割边，删去这条边后将图分为两个连通分量 \(X\) 和 \(Y\)，其中 \(X\) 是包含了点 \(u\) 的连通分量。

  由于 \(G\) 是 \(k\)-正则偶图，则 \(X\) 也是偶图，设 \(X\) 的二部划分为 \(S\) 和 \(T\)，不妨设 \(S\) 包含了点 \(u\)。

  根据偶图的性质可知 \(S\) 的度数之和等于 \(T\) 的度数之和。设 \(|S| = s\)，\(|T| = t\)

  因此有 \(sk - 1 = tk\)

  若 \(s \ge t\) 则 \((s-t)k = 1\)，又因为 \(k > 1\)，因此这种情况不成立。

  若 \(s < t\) 则 \((t-s)k = -1\)，同样不成立。

  因此没有割边。

• 当图 \(G\) 连通时，若 \(S \ne \varnothing\)，则边割 \(B = [S, \overline{S}]\) 为键的充分必要条件是 \(G[S]\)，\(G[\overline{S}]\) 都连通。

• 图 \(G\) 的每⼀个边割是图 \(G\) 的⼀些键(即割集)的边不重并。

• 在图 \(G\) 中，设 \(B_1\) 和 \(B_2\) 为键， \(C_1\) 和 \(C_2\) 为 圈（看作边⼦集），则：

  • \(B_1 \oplus B_2\) 是图 \(G\) 的键的边不重并集；
  • \(C_1 \oplus C_2\) 是图 \(G\) 的键的边不重并集；
  • 对图 \(G\) 的任意一条边 \(e\)，\((B_1 \cup B_2)\backslash \{e\}\) 都包含键;
  • 对图 \(G\) 的任意一条边 \(e\)，\((C_1 \cup C_2)\backslash \{e\}\) 都包含圈;

• 若图 \(G\) 包含 \(k\) 棵边不重的⽣成树，则对于顶点集每⼀个划分 \((V_1, V_2, \cdots , V_n)\)，两个端点在这个划分的不同部分的边的数目至少为 \(k(n-1)\)。

• 若连通图 \(G\) 的边子集 \(E'\) 与图 \(G\) 的每⼀棵生成树都有公共边，则 \(E'\) 包含 的⼀个图 \(G\) 的边割。 （提示：证明 \(G⼀E'\) 不连通。）
• 若点 \(u\) 是简单连通图 \(G\) 的割点，则点 \(u\) 是图 \(G^C\) 的非割点。(提示:⼀般地，图 \(G\) 不连通，则图 \(G^C\) 连通。)
• 若树 \(T\) 为连通图 \(G\) 的任意⼀棵树(不⼀定为生成树)，\(e \in E(T)\)，则在图 \(G\) 中⼀定有⼀个键 \(B\)，使得 \(B \cap T = \{e\}\)。

第四章 匹配

4.1 匹配

• \(M\) 为 \(G\) 中的最大匹配 \(\Leftrightarrow\) G 中不在 \(M\)-可扩路。
• \(M\)-可扩路的边数是奇数。

4.2 独立集、团、覆盖和匹配及其之间的关系

• 课本中覆盖表示点覆盖。边覆盖才是边覆盖。
• 独立数：最大独立集的点的数量。
• 覆盖数：最小点覆盖的点的数量。
• 最大独立集 \(+\) 最小点覆盖 \(=n\)
• 如果一个图没有孤立的点，则 最大匹配 \(+\) 最小边覆盖 \(=n\)

• \(S\) 为覆盖：

  \(\Leftrightarrow\) \(G\) 的每边至少有⼀端在 \(S\) 中。

  \(\Leftrightarrow\) 不存在两个端点全在 \(V \backslash S\) 中的边。

  \(\Leftrightarrow\) \(V \backslash S\) 为 空图或独立集。

• 匹配和覆盖的关系：设任意匹配为 \(M\)，最大匹配为 \(M^*\)，最小覆盖为 \(K\)，任意覆盖为 \(K^*\)，则有 \(|M| \le |M^*| \le |K^*| \le |K|\)

4.3 偶图的匹配和覆盖

• 邻集 \(N(S)\) \((S \subseteq V)\) 表示 \(G\) 中所有与 \(S\) 中顶点相邻接的顶点集合。\(N(S)\) 也可能包含 \(S\) 中的顶点。

• 在偶图 \(G=(X,Y,E)\) 中 \(G\) 包含使 \(X\) 中每个顶点都饱和的匹配 \(\Leftrightarrow\) \(\forall S \subseteq X\)，\(|N(S) | \ge |S|\)

• 若 \(G\) 为 \(k\)-正则偶图 \((k>0)\)，则 \(G\) 有完美匹配。

  证明：设 \(G\) 的 \(2\)-划分为 \((X,Y)\)，则有 \(k|X| = E = k|Y|\)

  因此 \(|X| = |Y|\)

  对 \(\forall S \subseteq X\)，令 \(E_1\) 和 \(E_2\) 分别为 \(S\) 和 \(N(S)\) 相关联的边集。显然有 \(E_1 \subseteq E_2\)

  \(k|S| = |E_1| \le |E_2| = k|N(S)| \Rightarrow |S| \le |N(S)|\)

​ 故 \(G\) 中有使 \(X\) 中每个顶点都饱和的匹配 \(M\) ，它也是完美匹配。

• 在二分图中，最大匹配 \(=\) 最小点覆盖。

第五章 遍历问题

5.1 Euler环游

• 无向图是欧拉图当且仅当：

  • 非零度顶点是连通的

  • 顶点的度数都是偶数

• 无向图是半欧拉图当且仅当：

  • 非零度顶点是连通的

  • 恰有 2 个奇度顶点

• 有向图是欧拉图当且仅当：

  • 非零度顶点是强连通的

  • 每个顶点的入度和出度相等

• 有向图是半欧拉图当且仅当：

  • 非零度顶点是弱连通的

  • 至多一个顶点的出度与入度之差为 1

  • 至多一个顶点的入度与出度之差为 1

  • 其他顶点的入度和出度相等

• 求欧拉（环）路的方法：dfs+Hierholzer 算法，dfs 回到上一层的时候就入栈，最后按序弹出栈中元素即可。

• 若可能，画出⼀个点为偶数，而边为奇数的欧拉图。 否则说明理由。

  2 个点，1条自环即可。若不允许自环，则不存在这样的图。

• 若 \(G\) 无奇点，则 \(G\) 的每个块也是欧拉图。

• 若图 \(G\) 无奇点，则存在边不重的圈 \(C_1, C_2, \cdots, C_m\) 使得 \(E(G) = E(C_1) \cup E(C_2)\cup \cdots \cup E(C_m)\)

• 若连通图 \(G\) 有 \(2k(k > 0)\) 个奇点，则 \(G\) 中存在 \(k\) 条边不重的迹 \(Q_1, Q_2, \cdots, Q_m\) 使得 \(E(G) = E(Q_1) \cup E(Q_2)\cup \cdots \cup E(Q_k)\)

• 连通图 \(G\) 任意一个边割边数都是偶数的充分必要条件是图 \(G\) 是一个欧拉图。

• 若连通图 \(G\) 中只有两个奇点，则与任意一个奇点相关联的边中至多有一条是图 \(G\) 的割边。

5.3 Hamilton圈

• 哈密顿图的必要条件：

  • 对 \(\forall S \subset V\)，都有 \(\omega(G-S) \le |S|\)

• 判定为哈密顿图的充分条件：

  • 若图 \(G\) 是 \(v \ge 2\) 的无向简单图，且对于图 \(G\) 中任意不相邻的顶点 \(a, b\) 都有 \(d(a) + d(b) \ge v - 1\)，则图中存在哈密顿通路。

    证明：先证明图 \(G\) 是连通图，假设 \(G\) 不是连通图，则至少有两个连通分量 \(X\) 和 \(Y\)，假设 \(a \in X\)，\(b \in Y\)。则有 \(d(a) + d(b) \le |X| - 1 + |Y| - 1 = v - 2\)，这与 \(d(a) + d(b) \ge v - 1\) 矛盾。因此图 \(G\) 一定是连通图。

    下面证明图 \(G\) 存在哈密顿路径。首先找到一条极大路径 \(P = P_1P_2\cdots P_{k-1}P_k\)

    1. 若 \(k = v\)，则 \(P\) 就是 \(G\) 的哈密顿路径。

    2. 若 \(k < v\)，则先证明存在一个回路经过 \(P\) 上所有的点。

       1. 若 \(P_1\) 和 \(P_k\) 相邻，则存在回路 \(C = P_1P_2\cdots P_{k-1}P_kP_1\)

       2. 若 \(P_1\) 和 \(P_k\) 不相邻，由于 \(P\) 是极大路径，因此 \(P_1\) 和 \(P_k\) 的所有邻居都在路径 \(P\) 中。设 \(P_1\) 的邻居在 \(P\) 中标号最大的为 \(P_j\)，\(P_k\) 的邻居在 \(P\) 中标号最大的为 \(P_i\)

          下面证明 \(j > i\)，假设 \(j \le i\)，则 \(P_1\) 至多有 \(j-1\) 个邻居（\(P_2\cdots P_i\)）， \(P_k\) 至多有 \(k-i\) 个邻居（\(P_j\cdots P_{k-1}\)），则 \(d(P_1) + d(P_k) \le j-1+k-i \le k - 1 < v - 1\)，这就产生矛盾，因此有 \(j > i\)

          则存在一条回路 \(C = P_1P_2\cdots P_{i-1}PiP_kP_{k-1}\cdots P_{j+1}P_j\)

       由于图 \(G\) 是连通图，则在路径 \(P\) 以外存在一个点 \(u\) 与 \(P_2\) 到 \(P_{k-1}\) 的某点邻接（否则，点 \(P\) 中所有的点组成一个连通分量），则将 \(u\) 并入回路 \(C\) 中可以得到一条新的路径。不断执行这个过程，则可以得到一条欧拉路径。

---

最后更新: 2024-01-01
创建日期: 2024-01-01