《湘潭大学 刘任任版 离散数学课后习题答案 习题8》由会员分享，可在线阅读，更多相关《湘潭大学 刘任任版 离散数学课后习题答案 习题8（6页珍藏版）》请在金锄头文库上搜索。
1、 习题 81、图中 8.10 中哪些是 E 图？哪些是半 E 图？ )(a)(b)(c分析：根据欧拉定理及其推论，E 图是不含任何奇点的图，半 E 图是最多含两个奇点的图。解： (a) 半 E 图 。 （b）E 图。 （c）非半 E 图 和 E 图 2、试作出一个 E 图 G(p,q),使得 p 与 q 均为奇数。能否作出一个 E 图 G(p,q)，使得 p 为偶数，而 q 为奇数？如果是 p 为奇数，q 为偶数呢？解：以下 E 图中， p 与 q 的奇偶如下表 p qG1 奇数 奇数G2 偶数 奇数G3 奇数 偶数3、求证：若 G 是 E 图，则 G 的每个块也是 E 图。 分析：一个图如果
2、含有 E 回路，则该图是 E 图；另一方面一个块是 G 中不含割点的极大连通不可分子图，且非割点不可能属于两个或两个以上的块。这样沿 G 中的一条 E 回路遍历G 的所有边时，从一个块到达另一个块时，只能经过割点才能实现。证明：设 B 是 G 的块，任取 G 中一条 E 回路 C，由 B 中的某一点 v 出发，沿 C 前进，C只有经过 G 的割点才能离开 B，也就是说只有经过同一个割点才能回到 B 中，注意到这个事实后，我们将 C 中属于 B 外的一个个闭笔回路除去，最后回到 v 时，我们得到的就是 B上的一个 E 回路，所以 B 也是 E 图。4、求证：若 G 无奇点，则 G 中存在边互不重
3、的回路 ，使得分析：G 中无奇点，则除了孤立点后其他所有点的度至少为 2，而孤立点不与任何边关联，因此在分析由边构成的回路时可以不加考虑；而如果一个图所有的顶点的度至少为 2，则由第五章习题 18 知该图必含回路。证明：将 G 中孤立点去掉以后得到图 G1，显然 G1 也是一个无奇点的 E 图，且 。)1(G由第五章习题 18 知，G1 必含有回路 C1；在图 G1-C1 中去掉孤立点，得图 G2，显然 G2mC,1L)()()(21mCL321仍然是一个无奇点的图，且 ，于是 G2 中也必含回路 C2，如此直到 Gm 中有2)(G回路 Cm，且 Gm-Cm 全为孤立点为止，于是有：5、求证：
4、若 G 有 2k0 个奇点，则 G 中存在 k 个边互不重的链 ,使得：分析：一个图的 E 回路去掉一条边以后，将得到一条 E 链。证明：设 为 G 中的奇数度顶点， k1 在 Vi 和 Vi+k 之间用新边 ei 连接，=1，2.k,所得之图记为 G*，易知 G*的每个顶点均为偶数，从而 G*存在 E 闭链 C* 。现从 C*中删去 ei （=1，2.k） ，则 C*被分解成 k 条不相交的链Qi(=1，2.k),显然有: 6、 证明：如果 （1）G 不是 2连通图，或者（2）G 是二分图,且 XY,则 G 不是 H 图。分析：G 不是 2连通图，说明 ，于是 或 ，如果 ，则说1)(1)(
5、0)(G0)(明 G 不连通，如 G 不连通，显然 G 不是 H 图，如 则 G 中存在孤立点，因此有(G-v) 2，由定理 8.2.1G 不是 H 图。若 G 是二分图，则 X 或 Y 中的任意两个顶点不邻接，因此 G-X 剩下的是 Y 中的点，这些点都是孤立点；同样 G-Y 剩下的是 X 中的点，这些点也是孤立点；即有 ，如果 XY ，则有|)(|)(YX，成立。无论哪个结论成立，根据定理 8.2.1 都有 G 不|)(|)(XYG或是 H 图。证明：若（1）成立则 G 不连通或者是 G 有割点 u，若 G 不连通,则 G 不是 H 图，若 G 有割点 u，取 S=u,于是 (G-u) S
6、 因此 G 不是 H 图.因此 G 不是 H 图.7、证明：若 G 是半 H 图,则对于 V(G)的每一个真子集 S，有: 分析：图 G 的权与它的生成子图 的连通分支数满足： ，因为一个图的生成子图是在该图的基础上去掉若干边得到的，显然去掉边以后只能使该图的连通分支增加。)()()(21mCCLkQ,1L)()()(21QQkkVV212,1,L)()()(kQEQE. ,.2XYSXY）（即 ： ）（ 则令） 成 立 ， 不 妨 设若 （ .1)(SG)对于图 G 的一条 H 通路 C，满足任取 , VS证明:设 C 是 G 的一条 H 通路，任取 , 易知而 C-S 是 G-S 的生成子
7、图. 8、试述 H 图与 E 图之间的关系。 分析：H 图是指存在一条从某个点出发经过其他顶点有且仅有一次的回路；而 E 图是指从某点出发通过图中所有的边一次且仅有一次的回路。从定义可看出，这两者之间没有充分或必要的关系。解 ： 考虑如下四个图: 1G3G4G2易知 G1 是 E 图，但非 H 图; G2 是 H 图，但非 E 图; G3 既非 E 图，又非 H 图；G4 既是 E图，也是 H 图。9、作一个图，它的闭包不是完全图分析：一个 p 阶图的闭包是指对 G 中满足 d(u)+d(v)p 的顶点 u,v，若 uv E(G)，则将边uv 加到 G 中，得到 G+uv，如此反复加边，直到满
8、足 d(u)+d(v)p 的所有顶点均邻接。由闭包的定义，如果一个图本身不存在任何一对顶点 u,v，满足 d(u)+d(v)p，则它的闭包就是其自身。显然可找到满足这种条件的非完全图。10、若 G 的任何两个顶点均由一条 H 通路连接着，则称 G 是 H 连通的。（2）对于 p4，构造一个具有 的 H 连通图 G。分析：根据定理 5.3.1 有 ，因此)(21piivdq2/)(1piivdq而 ，所以 qp*(G)/2，因此如果能判断 (G) 3，则有)()(1Gpvdpii.1)()(SCG故 .1)(SG故不 是 完 全 图 。， 但，解 ： 如 右 图 ).)13(2,4)1( pqp
9、则连 通 的 ， 且是证 明 ： 若 )(1.;)13(2/ pPq 下面的证明关键是判断 (G)3。证明：（1）任取 wV(G), 由于 G 是连通的，所以 d(w)1。若 d(w)=1,则与 w 邻接的顶点 u 与 w 之间不可能有一条 H 通路连接它们，否则因为p4，所以 G 中除了 u 与 w 外还有其他顶点，因此，如果 u 与 w 之间有一条 H 通路的话，这条 H 通路与 u 与 w 的连线就构成了一个回路，这样与 d(w)=1 矛盾，所以 d(w)1；同样的道理，若 d(w)=2，则与 w 邻接的顶点 u 与 v 之间不存在 H 通路。因此 (G) 3 。从而 2q=d(u)3p
10、, 即： 2q3p,也即 q 3p/2() 若 p 为奇数，于是() 若 p 为偶数，则 3p 为偶数，于是综合以上各种情况 ，有： （2）() 当 p=偶数时，q=3p/2，满足条件的图如下图(a);() 当 p=奇数时， 满足条件的图如下图 (b);图(a) 图(b);13(2pq;)13(2p;)(,)13(2pq 11、证明：若 G 是一个具有 p2 的连通简单图，则 G 有一条长度至少是 2 的通路。分析：使用反证法，假设 G 中没有一条长度大于或等于 2 的通路。先找到图 G 的一条最长通路 P，设其长度为 m，由假设 mm。从而 G 是 H 图。图 。是） 则（为 奇 数 ， 还
11、 有若均 有 证 明 ： 若 对 任 何的 度 序 列 为 ：阶 简 单 图、 设 ）（ pdmdpm mG12,2/)1( ,.31 L图 。是知 ，从 而 ， 由 定 理 ， 也 即即于 是 ， 则若 则 由 题 设 有若为 奇 数 ， 则） 若（ HGmpdmpdpdmpb dpapmppmp m4.281)(2)1( 21)( ,1)(212)1( 图 。为知再 由 定 理由 题 设 有即 ） ， 则 必 有 ：为 偶 数 （若证 明 ： 对 任 何 正 整 数 dppmm4.28,/)( ,13)1( ,2 121mVL。）（，）（令 11 )(),(iiii vdTvdSEE。即事
12、 实 上 ， 于 是因 此 ，由 定 义 知 ： S TSTSTSmII IIIUQIU,0 22 ,1 故 结 论 成 立 。 的 假 设 矛 盾 ！此 与且：是 有 通 路 ） ，（连 接 。 不 妨 设外 的 通 路 与连 通 可 知 ， 有 一 条由 ） 。（外 至 少 还 有 一 个 顶 点所 以 ，因 ：的 回 路中 的 长 为从 而 有设 PvvvP jGECG Vp vvmGTv imij j imii ,. .1,1, .111110 01121 L L 图 。是， 则或有， 而 且 对 任 何 mdpp ,/21L13、在图 8-8 中，如果分别去掉 v3，v4 和 v5，
13、则相应得到的旅行推销员问题的解分别取什么下界估计值？ 分析：利用 Kruskal 算法可给出一个关于旅行推销员问题的的下界估计式：任选赋权完全图 Kn 的一个顶点 v，用 Kruskal 算法求出 Kn-v 的最优树 T，设 C 是最优的 H 回路，于是有 C-v 也是 Kn-v 的一个生成树，因此有：w(T) w(C-v)设 e1 和 e2 是 Kn 中与 v 关联的边中权最小的两条边，于是：w(T)+w(e1)+w(e2)w(C)上式左边的表达式即是 w(C)的下界估计式。解：（1）去掉 v3 后的最优数 T3 的权为 w(T3)=5+5+1+7=18,而与 v3 关联的 5 条边中权最小
14、的两条之权为 w(e1)=8,w(e2)=9,因此下界估计值为 w(C3)=18+8+9=35,( 2 )去掉 v4 后，仿上有 w(T4)=20, w(C4)=20+7+8=35;（3）去掉 v5 后, 有 w(T5)=26, w(C5)=26+1+5=32.14、设 G 是一种赋权完全图，其中对任意 x,y,zV(G),都满足 ： 证明：G 中最优 H 回路最多具有权 其中 T 是 G 中的一棵最优树。分析：H 回路是指从图中某点出发，经过图中每个顶点有且仅有一次，最后回到出发点的一条回路。由于 G 是一种赋权完全图，所以从任意顶点出发包括了 G 的其他所有顶点有且仅有一次再回到原点的回路都构成了 G 的一条 H 回路 ，且最优 H 回路 C 的权满足 C。因此
