Graph Theory — Homework 1

Problem 1.

试问：序列

(2, 2, 2, 2, 1, 1) 一定是 6 个顶点的路 P_6 的度序列吗？

证明.

这样的序列不一定是 6 个顶点的路 P_6 的度序列.

CodeBlock Loading...

(1) v1与v6各自连接的点不同：
CodeBlock Loading...
1. (i) v2与v5各自连接的点不同：我们记v2 连接 v3，v5 连接 v4.由于\deg v3=\deg v4=2，故其必然各自分别连接一个点，而此时六个顶点都出现了，符合的连接方式只有v3与v4相连，故此是构成一条路：v1-v2-v3-v4-v5-v6，符合题意.
2. (ii) v3与v4各自连接的点不相同：我们记v3 与v4共同连接的点是v_5，则此时

\left{\deg v3,\deg v4,\deg v5,\deg v1,\deg v_6\right}=\left{2,2,2,1,1\right}

此时无论剩下的一个点怎么连接都无法使得度序列变为题目要求的\left\{2,2,2,2,1,1\right\}. 2. **(2)** **v_1与v_6各自连接的点相同：**我们记v_2连接v_1和v_6，则这三个点的度序列为

\left{\deg v1,\deg v2,\deg v_6\right}=\left{1,2,1\right}

剩下三个点v3,v4,v_5构成的都序列由题意应为：

\left{\deg v3,\deg v4,\deg v_5\right}=\left{2,2,2\right}

这三个点只有可能构成一个三角形.这样的话，度序列符合题意，另外这样相当于是一条路P_3和一个完全图K_3，相当于一个有两个连通分支的图，故不一定是 6 个顶点的路 P_6 的度序列. ∎ **Problem 2.** 证明：连通图的任意两条最长路都有至少一个公共顶点. **反证.** 假设两条最长路分别为：P_1,P_2，且P_1,P_2没有公共顶点.由于G是一个连通图，故存在一条路Q使得Q分别连接P_1中的v_1和P_2中的点v_2.首先这两个点不是端点，若是端点，则L(P_1\cup Q)\geq L(P_1)（L()表路的长度），与最长路的设定矛盾！ 我们记v_1沿P_1向两端延伸的最长子路P_1'的长度为l_1，v_2沿P_2向两端延伸的最长子路P_2'的长度为l_2，则l_1\geq \frac{L(P_1)}{2},l_2\geq \frac{L(P_2)}{2}，且L(Q)\geq 1，我们考虑路P=P_1'\cup Q\cup P_2'：

L(P)=L(P1'\cup Q\cup P2')=l1+l2+L(Q)\geq \frac{L(P_1)}{2}+\frac

CodeBlock Loading...

1. **(1)** L(P_1)=L(P_2)，则：L(P)\geq L(P_1)+1>L(P_1)与最长路的设定矛盾！ 2. **(2)** L(P_1)\neq L(P_2)，不妨设L(P_1)<L(P_2)则：L(P)\geq \frac{L(P_1)}{2}+\frac{L(P_2)}{2}+1>L(P_1)+1>L(P_1)与最长路的设定矛盾！ 综上：连通图的任意两条最长路都有至少一个公共顶点. ∎ **Problem 3.** 设树 T 有一个顶点的度至少为 k.求证：树 T 至少有 k 个叶子. **证明.** 设 v_0 是树 T 的一个顶点，且 \deg(v_0) \ge k.考虑 v_0 的每条邻边 e_i = v_0 u_i,i=1,2,\dots, \deg(v_0).移除 v_0 后，T 分成 \deg(v_0) 棵子树 T_i，每个 T_i 包含 u_i.每棵子树 T_i 中，从 u_i 出发沿任意极长路径，最终会到达一个叶子 l_i（因为树有限无环，且除了 v_0 方向外，其它方向走下去会终止于度数为 1 的顶点）.这些叶子 l_1,\dots,l_{\deg(v_0)} 互不相同，且都在 T 中.由于 \deg(v_0) \ge k，所以至少有 k 个不同的叶子. ∎ **Problem 4.** 设树 T 恰好有 2k 个奇度顶点.试问：T 是否一定可以分解为 k 条路（即此树 T 的边集可以看成是 k 条路的边集的不交并）？ **解.** 我们先证明一个引理： **Lemma 1.** 如果一个连通图中每个顶点的度数均为偶数，那么这个图至少包含一个欧拉回路，即至少有一条遍历图中每条边一遍的回路. 这个引理是显然的：由于每个点的度数为偶数，故我们可以将整个图看成是由若干个环组成的，又因为环一定能找到一条欧拉回路，所以整个图能找到一条由若干个欧拉回路并起来的路当然还是欧拉回路. **回到原题** 由于树T有2k个奇度顶点，我们记为：V(T)=\left\{v_1,v_2,\dots,v_{2k-1},v_{2k}\right\}.我们考虑用k条新的路将v_i与v_{k+i}连接起来(i=1,2,\dots,k)，这样v_i与v_{k+i}的度数都加1，那么这两个点都变为偶度顶点，故我们通过这样的操作能将v_1,v_2,\dots,v_{2k-1},v_{2k}都变为偶度顶点，得到新图G，则由引理我们可知G是连通图且每个顶点的度数均为偶数，那么G存在一个欧拉回路P. 而这个欧拉回路包含e_1,e_2,\dots,e_k，我们把G剔除这k条边恰好得到的就是我们的树T.我们在欧拉回路P上剔除这k条边，就相当于把P划分成了k各部分即得到了我们的k条路，而分解出来的这k条路就验证了T一定可以分解为k条路. ∎ **Problem 5.** 证明：对于任意连通图 G 以及 G 的一个无圈子图 H，都存在 G 的生成树 T 使得 H \subseteq T \subseteq G. **证明.** 我们从 H 出发，逐步添加边，按照如下步骤构造一个包含 H 的生成树 T： 1. **Step1** 设 F_0 = H. 2. **Step2** 若 F_i 不包含 G 的所有顶点，则由于 G 连通，存在一条边 e = uv \in E(G)，其中 u \in V(F_i)，v \notin V(F_i).将 e 加入 F_i 得到 F_{i+1}.因为 v 不在 F_i 中，加入 e 不会形成环. 3. **Step3** 若 F_i 包含所有顶点但不连通，则由于 G 连通，存在边 e 连接 F_i 的两个不同连通分支.将 e 加入 F_i 得到 F_{i+1}.因为 e 连接两个不同分支，不会形成环. 4. **Step4** 重复上述步骤，直到 F_m 连通且包含所有顶点.此时 F_m 是 G 的生成树，且 H \subseteq F_m. 这样我们便得到了生成树 T 使得 H \subseteq T \subseteq G. ∎

PDF

Download the original write-up here.

Problem 1.

试问：序列

(2, 2, 2, 2, 1, 1) 一定是 6 个顶点的路 P_6 的度序列吗？

证明.

这样的序列不一定是 6 个顶点的路 P_6 的度序列.

由于其中有两个点度为1，我们不妨记v_1,v_6为这两个点，那么其必然各自分别连接一个点：

CodeBlock Loading...

(1) v1与v6各自连接的点不同：
我们记v_1 连接 v_2，v_6 连接 v_5.由于\deg v_2=\deg v_5=2，故其必然各自分别连接一个点：
CodeBlock Loading...
1. (i) v2与v5各自连接的点不同：我们记v2 连接 v3，v5 连接 v4.由于\deg v3=\deg v4=2，故其必然各自分别连接一个点，而此时六个顶点都出现了，符合的连接方式只有v3与v4相连，故此是构成一条路：v1-v2-v3-v4-v5-v6，符合题意.
2. (ii) v3与v4各自连接的点不相同：我们记v3 与v4共同连接的点是v_5，则此时

\left{\deg v3,\deg v4,\deg v5,\deg v1,\deg v_6\right}=\left{2,2,2,1,1\right}

此时无论剩下的一个点怎么连接都无法使得度序列变为题目要求的\left\{2,2,2,2,1,1\right\}. 2. **(2)** **v_1与v_6各自连接的点相同：**我们记v_2连接v_1和v_6，则这三个点的度序列为

\left{\deg v1,\deg v2,\deg v_6\right}=\left{1,2,1\right}

剩下三个点v3,v4,v_5构成的都序列由题意应为：

\left{\deg v3,\deg v4,\deg v_5\right}=\left{2,2,2\right}

这三个点只有可能构成一个三角形.这样的话，度序列符合题意，另外这样相当于是一条路P_3和一个完全图K_3，相当于一个有两个连通分支的图，故不一定是 6 个顶点的路 P_6 的度序列. ∎ **Problem 2.** 证明：连通图的任意两条最长路都有至少一个公共顶点. **反证.** 假设两条最长路分别为：P_1,P_2，且P_1,P_2没有公共顶点.由于G是一个连通图，故存在一条路Q使得Q分别连接P_1中的v_1和P_2中的点v_2.首先这两个点不是端点，若是端点，则L(P_1\cup Q)\geq L(P_1)（L()表路的长度），与最长路的设定矛盾！ 我们记v_1沿P_1向两端延伸的最长子路P_1'的长度为l_1，v_2沿P_2向两端延伸的最长子路P_2'的长度为l_2，则l_1\geq \frac{L(P_1)}{2},l_2\geq \frac{L(P_2)}{2}，且L(Q)\geq 1，我们考虑路P=P_1'\cup Q\cup P_2'：

L(P)=L(P1'\cup Q\cup P2')=l1+l2+L(Q)\geq \frac{L(P_1)}{2}+\frac

{L(P_2)}{2}+1

CodeBlock Loading...

1. **(1)** L(P_1)=L(P_2)，则：L(P)\geq L(P_1)+1>L(P_1)与最长路的设定矛盾！ 2. **(2)** L(P_1)\neq L(P_2)，不妨设L(P_1)<L(P_2)则：L(P)\geq \frac{L(P_1)}{2}+\frac{L(P_2)}{2}+1>L(P_1)+1>L(P_1)与最长路的设定矛盾！ 综上：连通图的任意两条最长路都有至少一个公共顶点. ∎ **Problem 3.** 设树 T 有一个顶点的度至少为 k.求证：树 T 至少有 k 个叶子. **证明.** 设 v_0 是树 T 的一个顶点，且 \deg(v_0) \ge k.考虑 v_0 的每条邻边 e_i = v_0 u_i,i=1,2,\dots, \deg(v_0).移除 v_0 后，T 分成 \deg(v_0) 棵子树 T_i，每个 T_i 包含 u_i.每棵子树 T_i 中，从 u_i 出发沿任意极长路径，最终会到达一个叶子 l_i（因为树有限无环，且除了 v_0 方向外，其它方向走下去会终止于度数为 1 的顶点）.这些叶子 l_1,\dots,l_{\deg(v_0)} 互不相同，且都在 T 中.由于 \deg(v_0) \ge k，所以至少有 k 个不同的叶子. ∎ **Problem 4.** 设树 T 恰好有 2k 个奇度顶点.试问：T 是否一定可以分解为 k 条路（即此树 T 的边集可以看成是 k 条路的边集的不交并）？ **解.** 我们先证明一个引理： **Lemma 1.** 如果一个连通图中每个顶点的度数均为偶数，那么这个图至少包含一个欧拉回路，即至少有一条遍历图中每条边一遍的回路. 这个引理是显然的：由于每个点的度数为偶数，故我们可以将整个图看成是由若干个环组成的，又因为环一定能找到一条欧拉回路，所以整个图能找到一条由若干个欧拉回路并起来的路当然还是欧拉回路. **回到原题** 由于树T有2k个奇度顶点，我们记为：V(T)=\left\{v_1,v_2,\dots,v_{2k-1},v_{2k}\right\}.我们考虑用k条新的路将v_i与v_{k+i}连接起来(i=1,2,\dots,k)，这样v_i与v_{k+i}的度数都加1，那么这两个点都变为偶度顶点，故我们通过这样的操作能将v_1,v_2,\dots,v_{2k-1},v_{2k}都变为偶度顶点，得到新图G，则由引理我们可知G是连通图且每个顶点的度数均为偶数，那么G存在一个欧拉回路P. 而这个欧拉回路包含e_1,e_2,\dots,e_k，我们把G剔除这k条边恰好得到的就是我们的树T.我们在欧拉回路P上剔除这k条边，就相当于把P划分成了k各部分即得到了我们的k条路，而分解出来的这k条路就验证了T一定可以分解为k条路. ∎ **Problem 5.** 证明：对于任意连通图 G 以及 G 的一个无圈子图 H，都存在 G 的生成树 T 使得 H \subseteq T \subseteq G. **证明.** 我们从 H 出发，逐步添加边，按照如下步骤构造一个包含 H 的生成树 T： 1. **Step1** 设 F_0 = H. 2. **Step2** 若 F_i 不包含 G 的所有顶点，则由于 G 连通，存在一条边 e = uv \in E(G)，其中 u \in V(F_i)，v \notin V(F_i).将 e 加入 F_i 得到 F_{i+1}.因为 v 不在 F_i 中，加入 e 不会形成环. 3. **Step3** 若 F_i 包含所有顶点但不连通，则由于 G 连通，存在边 e 连接 F_i 的两个不同连通分支.将 e 加入 F_i 得到 F_{i+1}.因为 e 连接两个不同分支，不会形成环. 4. **Step4** 重复上述步骤，直到 F_m 连通且包含所有顶点.此时 F_m 是 G 的生成树，且 H \subseteq F_m. 这样我们便得到了生成树 T 使得 H \subseteq T \subseteq G. ∎

PDF

Download the original write-up here.

Graph Theory — Homework 1

Search

Graph Theory — Homework 1

PDF

PDF