图论及其应用1-3章习题答案(电子科大)

习题一习题一 1 题 14 证明图 1 28 中的两图是同构的 证明证明 将图 1 28 的两图顶点标号为如下的 a 与 b 图 作映射 f f vi ui 1 i 10 容易证明 对 vivj E a 有 f vivj uiuj E b 1 i 10 1 j 10 由图的同构定义知 图 1 27 的两个图是同构的 2 题 6 设G是具有m条边的n阶简单图 证明 m 当且仅当G是 2 n 完全图 证明证明 必要性 若 G 为非完全图 则 v V G 有 d v n 1 d v n n 1 2m n n 1 m n n 1 2 与已知矛盾 2 n 充分性 若 G 为完全图 则 2m d v n n 1 m 2 n 图 1 28 a v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 u1 u2 u3 u4 u5 u6 u7 u8 u9 u10 b 3 题 9 证明 若k正则偶图具有二分类V V1 V2 则 V1 V2 证明证明 由于 G 为k正则偶图 所以 k V1 m k V2 V1 V2 4 题 12 证明 若 2 则G包含圈 证明证明 只就连通图证明即可 设 V G v1 v2 vn 对于 G 中的路 v1v2 vk 若 vk与 v1邻接 则构成一个圈 若 vi1vi2 vin是一条路 由于 2 因此 对 vin 存在点 vik与之邻接 则 vik vinvik构成一个圈 5 题 17 证明 若G不连通 则连通 G 证明证明 对 若 u 与 v 属于 G 的不同连通分支 显然 u 与 v 在中 GVvu G 连通 若 u 与 v 属于 g 的同一连通分支 设 w 为 G 的另一个连通分支中的一个 顶点 则 u 与 w v 与 w 分别在中连通 因此 u 与 v 在中连通 G G 习题二习题二 2 证明 每棵恰有两个 1 度顶点的树均是路 证明 设树 T 为任意一个恰有两个 1 度顶点的树 则 T 是连通的 且无圈 令 V1 V2 为度为 1 的顶点 由于其他的顶点度数均为 0 或者 2 且 T 中无圈 则从 V1到 V2 有 且只有一条连通路 所以 每棵恰有两个 1 度顶点的树均是路 得证 5 证明 正整数序列是一棵树的度序列当且仅当 21n ddd 1 2 1 nd n i i 证明 设正整数序列是一棵树 T 的度序列 则满足 E 为 T 21n dddEd n i i 2 1 的边数 又有边数和顶点的关系 所以1 En 1 2 1 nd n i i 14 证明 若 e 是的边 则 n K 3 2 n n nneK 若 e 为 Kn 的一条边 由 Kn 中的边的对称性以及每棵生成树的边数为 n 1 Kn 的所有 生成树的总边数为 所以 每条边所对应的生成树的棵数为 2 1 n nn 所以 K n e 对应的生成树的棵数为 3 2 2 1 2 1 1 n n n nn nn 332 2 2 nnn n nnnneK 16 Kruskal 算法能否用来求 1 赋权连通图中的最大权值的树 2 赋权图中的最小权的最大森林 如果可以 怎样实现 解 1 不能 Kruskal 算法得到的任何生成树一定是最小生成树 2 可以 步骤如下 步骤一 选择边 e1 是的尽可能小 1 e 步骤二 若已选定边 则从选取 使 i eee 21 21i eeeE 1 i e a 为无圈图 121 i eeeG b 是满足 a 的尽可能小的权 1 i e 步骤三 当步骤二不能继续执行时停止 习题三习题三 3 设 G 是阶大于 2 的连通图 证明下列命题等价 1 G 是块 2 G 无环且任意一个点和任意一条边都位于同一个圈上 3 G 无环且任意三个不同点都位于同一条路上 证明 1 2 G 是块 任取 G 的一点 u 一边 e 在 e 边插入一点 v 使得 e 成为两条边 由此得到 新图 显然的是阶数大于 3 的块 由定理 G 中的 u v 位于同一个圈上 于是 1 G 1 G 中 u 与边 e 都位于同一个圈上 1 G 2 3 无环 且任意一点和任意一条边都位于同一个圈上 任取 的点 u 边 e 若 在 上 则三个不同点位于同一个闭路 即位于同一条路 如 不在 上 由定理 的两点在 同一个闭路上 在 边插入一个点 v 由此得到新图 显然的是阶数大于 3 的块 则 两条边的三个不同点在同一条路上 3 1 连通 若 不是块 则 中存在着割点 划分为不同的子集块 无 环 点 在每一条的路上 则与已知矛盾 是块 12 xv yv 13 设 H 是连通图 G 的子图 举例说明 有可能 k H k G 解 通常 整个图为 割点 左边的图 为 的的子图 则 15 设 T 是简单连通图 G 的生成树 称为 G 的余树 图 G 的极小边割是指其 TEGT 任何真子集均不是边割的边割 证明 1 不含 G 的极小边割 T 2 包含 G 的唯一的极小边割 其中 e 为 G 的不在中的边 eT T 证明 1 设含有 G 的极小边割S 则 T 中不含极小边割S 由于 T 是简单连通图 G 的T 生成树 则 T 中必然含有一组极小割边 这与 T