电子科大图论答案

图论第三次作业图论第三次作业 一 第六章 2 证明 根据欧拉公式的推论 有 m l n 2 l 2 1 若 deg f 4 则 m 4 n 2 2 2n 4 2 若 deg f 5 则 m 5 n 2 3 即 3m 5n 10 3 若 deg f 6 则 m 6 n 2 4 即 2m 3n 6 3 证明 G 是简单连通图 根据欧拉公式推论 m 3n 6 又 根据欧拉公式 n m 2 2 n m 2 n 3n 6 2n 4 4 证明 1 G 是极大平面图 每个面的次数为 3 由次数公式 2m 3 由欧拉公式 2 n m m 2 n m 即 m 3n 6 2 又 m n 2 2n 4 3 对于 3n 的极大可平面图的的每个顶点v 有 3d v 即对任一一点或者 子图 至少有三个邻点与之相连 要使这个点或子图与图 G 不连通 必须把与 之相连的点去掉 所以至少需要去掉三个点才能使 H w Gw G 由点连通 度的定义知 3G 5 证明 假设图 G 不是极大可平面图 那么 G 不然至少还有两点之间可以添加一条边 e 使 G e 仍为可平面图 由于图 G 满足 36mn 那么对图 G e 有 36mn 而平面图的必要条件为 36mn 两者矛盾 所以图 G 是极 大可平面图 6 证明 1 由 4G 知 5n 当 n 5 时 图 G 为 5 K 而 5 K 为不可平面图 所以 6n 由 4G 和握手定理有2 4mn 再由极大可平面图的性质 36mn 即可得 6n 对于可平面图有 5G 而 6n 所以至少有 6 个点的度数 不超过 5 2 由 5G 和握手定理有2 5mn 再由极大可平面图的性质 36mn 即可得 12n 对于可平面图有 5G 而 12n 所以 至少有 12 个点的度数不超过 5 二 第七章 2 证明 设 n 2k 1 G 是 正则单图 且 0 m G k 由定理 5 可知 G G 1 28 解 1 又 k k 1 k 2 2 k 3 k k 1 2 k 2 k k 1 k 2 k2 4k 5 k k 1 k 2 2 k 3 所以 原图色多项式为 k k 1 k 2 2 k2 4k 5 k k 1 k 2 2 k 3 k k 1 k 2 2 k2 5k 8 2 原图与该图同构 又 同构的图具有相同的色多项式 所以原图色多项式为 k k 1 k 2 2 k2 5k 8 31 证明 1 用归纳法来证明 当 m 1 时 直接计算 Pk G km km 1 得 km 1系数 为 1 且 Pk G 中具有非零系数的 k 的最小次数为 1 即 G 分支数 故 m 1 时命题成立 设对于少于 m 条边的一切 n 阶单图命题均成立 考虑单图 G n m 由递推公式 Pk G Pk G e Pk G e 由假设可令 Pk G e kn a1kn 1 an 1kn 1 且 a1 m 1 Pk G e kn 1 b1kn 2 bn 2kn 2 且 b1 m 1 Pk G kn a1 1 kn 1 a1 b1 kn 2 bn 2kn 2 Pk G 中 kn 1的系数 a1 1 m Pk G 中具有非零系数的 k 的最小次数为 n 2 即为 G 的分支数 2 一个多项式 若是某个图的色多项式 那么也是该图对应的底图 的色多项式 故我们仅需对单图来证明 若 Pk G k4 3k3 3k2是某个 单图 G 的色多项式 则由 1 可知 m G 3 从而 G 2 另一方面 P1 1 这说明 G 1 与上面结论相矛盾 故 Pk不可能是任何单图 的色多项式 32 证明 因为 G1和 G2中分别有一个唯一的 4 度顶点 u1与 v1 但 是它们邻点状况不相同 u1有 4 个 2 度邻点 而 v1只有两个 2 度顶 点 所以 G1与 G2不同构 利用直接计算方法可得 Pk G1 Pk G2 10k3 5k4 k5 33 证明 1 当 n 1 时 Pk K1 k 命题成立 若 n m 时 命题均成立 设 G 是树 且 n G m 可知 存在悬挂边 e E G 于是 G e 是孤立点加上顶点数为 m 1 的树 G e 是 v G e m 1 的树 由归纳法可知 Pk G Pk G e Pk G e k2 k 1 m 2 k k 1 m 2 k k 1 m 1 故命题成立 2 Pk G e Pk G Pk G e Pk G e 0 所以 Pk G e Pk G 另一方 面由于 G 连通 设 T 是 G 的生成树 逐次用上述导出的公式将余数 T 的边从 G 中除去 于是最后有 Pk G Pk T 由 a Pk T k k 1 m 1 所 以 Pk G k k 1 m 1 若连通图 G 的 Pk G k k 1 m 1时 则 n m 1 所以 G 是一棵树 即当 且仅当 G 是树时等号才成立 三 第九章 1 解 每条边有 2 种定向方式 所以一个简单图共有 2m G 种定向 2 证明 不失一般性 设 G 是连通图 G 中奇度顶点个数必然为偶 数个 将偶数个奇度顶点配对 然后在每一对配对顶点间连一条边 得到欧拉图 G1 在 G1 中用 Fluery 算法求出 G 的一欧拉环游 C 然 后顺次在 C 上标上方向 由此得到 C 的定向图 C1 在 C1中 去掉添加的边后 得到 G 的定向图 D 显然 对 v V D 有 d v d v 1 7 解 强连通分支 1 2 3 5 6 7 4 9 8 单向连通分支 1 2 3 4 5 6 7 8 9 弱连通分支 1 2 3 4 5 6 7 8 9 11 证明 设该树有 i 个分支点