湘潭大学计算机科学与技术刘任任版离散数学课后习题答案 - 第二学期--图论与组合数学

习 题 六

1．设G是一个无回路的图, 求证：若G中任意两个顶点间有惟一的通路, 则G是树. 证明：由假设知，G是一个无回路的连通图，故G是树。

2．证明：非平凡树的最长通路的起点和终点均为悬挂点. 分析：利用最长通路的性质可证。

证明：设P是树T中的极长通路。若P的起点v满足d(v)?1，则P不是T中极长的通路。对终点u也可同理讨论。故结论成立。

3．证明：恰有两个悬挂点的树是一条通路.

分析：因为树是连通没有回路的，所以树中至少存在一条通路P。因此只需证明恰有两个悬挂点的树中的所有的点都在这条通路P中即可。

证明：设u,v是树T中的两个悬挂点，即d(u)?d(v)?1。因T是树，所以存在(u,v)-通路

P：uw1?wkv,k?0。显然，d(wi)?2。若d(wi)?2，则由T恰有两个悬挂点的假设，可知T中有回路；若T中还有顶点x不在P中，则存在(u,x)-通路，显然u与x不邻接，且d(x)?2。于是，可推得T中有回路，矛盾。故结论成立。

4．设G是树, ??G??k, 求证：G中至少有k个悬挂点.

分析：由于??G??k，所以G中至少存在一个顶点v的度≥k，于是至少有k个顶点与邻接，又G是树，所以G中没有回路，因此与v邻接的点往外延伸出去的分支中，每个分支的最后一个顶点必定是一个悬挂点，因此G中至少有k个悬挂点。

证明：设u?V(G)，且d(u)?m?k。于是，存在v1,?,vm?V(G)，使

(l)uvi?E(G),i?1,?,m。若vi不是悬挂点，则有vi??V(G),使。如此下去，有vi?V(G)，

满足vi(l)?vj,i?j,且d(vi(l))?1, i?1,?,m。故G中至少有k个悬挂点。

5．设G?p,q?是一个图, 求证：若q?p, 则G中必含回路.

分析：利用树是没有回路且连通的图，且树中的顶点数和边数的关系可证。

证明：设G(p,q)有k个分支：G[V1]?G1(p1,q1),?,G[Vk]?Gk(pk,qk)。显然，

p?p1???pk,q?q1???qk。若G无回路，则每个Gi(pi,qi)均是树，i?1,?,k。

于是qi?pi?1,i?1,?,k。从而 q?p?k?p，k?1，即q?p。此为矛盾，故G必含回路。

6．设G?p,q?是有k个连通分支的图, 求证：G是森林当且仅当q?p?k.

证明：见题5的证明。

22

7．画出K4的所有16棵生成树.

解，K4的所有16棵生成树如下图所示。

1

4 4 1

4 2

1

3 4 2 1

3

4 2

1

3

4 23

2

1

3 4 2 1

3 4 2

1

3

4 2

3

2

3

2

3

1

2

1

2

1

2

4 3

4 3

4 3

1

2

1

2

1

2

4 3

4 3

4 3

1

2

4 3

8．设G?p,q?是连通图, 求证：q?p?1.

分析：树应该是具有p个顶点中边数最少的连通图，而树中的边数q=p-1可证。

证明：设G是连通图。若G无回路，则G是树，于是q?p?1。若G有回路，则删去G中k?0条边使之保持连通且无回路。于是q?k?p?1，即q?p?1?k?p?1。 9．递推计算K2,3的生成树数目.

24

e e =

e +

K2,3 e e +

+ +

e =

+ + + +

e e + +

25

=

e e

=

+ +

+ + + + + +

e +

+ =

+ + + + + =12

+ + + + + +

10．通过考虑树中的最长通路, 直接验证有标记的5个顶点的树的总数为125.

分析：设树中5个顶点的标记分别为1，2，3，4，5。而5个顶点的树的最长通路只能是4、3、2，如下（1）（2）（3）所示。 (1) 最长通路长度为4；

(2) 最长通路长度为3；

（3） 最长通路长度为2。 对于（1），把每个顶点看作是一个空，不同的顶点序列对应不同的树，但由于对称性12345和54321所形成的树应该是同一棵树，因此这种情况下所有有标记的树的数目为：5！/2=60个； 对于（2），把上面四个顶点分别看作一个空，在构造树的时候可以先构造这四个顶点，剩下的一

个顶点只能放在下面，选择上面四个顶点的数目应为可以从所有有标记的树的数目为C54*4！，但同样由对称性，如1234这样的排列和顶点5构成的树与1235这样的排列和4构

成的数是一样的。因此这种情况下所有有标记的树的数目为：C5*4！/2=60个； 对于（3），只要确定了中间度为4的顶点，这棵树就构造完了，所有这种情况下有标记的树的数

1目为：C5?5个；

4 26

习题8

1、图中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 的奇偶如下表 G1 G2 G3

p 奇数 偶数 奇数 q 奇数 奇数 偶数 G1G3G23、求证：若G 是 E 图，则 G 的每个块也是 E 图。

分析：一个图如果含有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中存在边互不重的回路 C , C ，使得 1, ?m

E(G)?E(C1)?E(C2)???E(Cm)分析：G中无奇点，则除了孤立点后其他所有点的度至少为2，而孤立点不与任何边关联，因此在分析由边构成的回路时可以不加考虑；而如果一个图所有的顶点的度至少为2，则由第五章习

37

题18知该图必含回路。

证明：将G中孤立点去掉以后得到图G1，显然G1也是一个无奇点的E图，且?(G1)?2。由第五章习题18知，G1必含有回路C1；在图G1-C1中去掉孤立点，得图G2，显然G2仍然是一个无奇点的图，且?(G2)?2，于是G2中也必含回路C2，…如此直到Gm中有回路Cm，且Gm-Cm全为孤立点为止，于是有：

5、求证：若G有2k>0个奇点，则G中存在k个边互不重的链 Q 1 , , Q k ,使得： ?

E(G)?E(C1)?E(C2)???E(Cm)E(G)?E(Q1)?E(Q2)???E(Qk)分析：一个图的E回路去掉一条边以后，将得到一条E链。

证明：设 1, V 2 , ? , V k , V k ? 1 ,? , VV 2 k为 G 中的奇数度顶点，k≥1在Vi和Vi+k 之间用新边ei连接，ⅰ=1，2….k,所得之图记为G*，易知G*的每个顶点均为偶数，从而G*存在 E 闭链C* 。现从C*中删去ei （ⅰ=1，2….k），则C*被分解成 k 条不相交的链Qi(ⅰ=1，2….k),显然有:

E(G)?E(Q1)?E(Q2)???E(Qk)6、 证明：如果 （1）G不是2—连通图，或者（2）G是二分图,且X≠Y,则 G 不是 H 图。 分析：G不是2—连通图，说明

?(G)?1，于是?(G)?1或?(G)?0，如果?(G)?0，则说明G

不连通，如G不连通，显然G不是H图，如?(G)?1则G中存在孤立点，因此有ω(G-v)≥2，由定理8.2.1G不是H图。若G是二分图，则X或Y中的任意两个顶点不邻接，因此G-X剩下的是Y中的点，这些点都是孤立点；同样G-Y剩下的是X中的点，这些点也是孤立点；即有?(G?X)?|Y|，?(G?Y)?|X|，如果X≠Y，则有?(G?X)?|Y|?|X|或?(G?Y)?|X|?|Y|成立。无论哪个结论成立，根据定理8.2.1都有G不是H图。

证明：若（1）成立则G不连通或者是G有割点u，若G不连通,则G不是H图，若G有割点u，取S={u},于是ω(G-u)> S因此 G不是H图.

若（2）成立，不妨设X?Y.令S?X,则

?（G?S）?Y?X?S 即：?（G?S）?S.因此 G不是H图.

?(G?S)?S?1.

38

7、证明：若 G 是半 H 图,则对于V(G)的每一个真子集S，有:

')'分析：图G的权与它的生成子图 G 的连通分支数满足： ? ( G ) ? ? (G ，因为一个图的生成子图

是在该图的基础上去掉若干边得到的，显然去掉边以后只能使该图的连通分支增加。

?1 . 对于图G的一条H通路C，满足任取S?V, ( C ? S ) ? S ?

证明:设C是G的一条H通路，任取S?V, 易知

?(C?S)?S?1.而 C-S是 G-S 的生成子图. 故?(G?S)??(C?S)?S?1.故?(G?S)?S?1.

8、试述 H 图与 E 图之间的关系。

分析：H图是指存在一条从某个点出发经过其他顶点有且仅有一次的回路；而E图是指从某点出发通过图中所有的边一次且仅有一次的回路。从定义可看出，这两者之间没有充分或必要的关系。 解 ： 考虑如下四个图:

G1G2G3G4

易知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，如此反复加边，直到满足d(u)+d(v)≥p的所有顶点均邻接。由闭包的定义，如果一个图本身不存在任何一对顶点u,v，满足d(u)+d(v)≥p，则它的闭包就是其自身。显然可找到满足这种条件的非完全图。

解：如右图G，G?G，但G不是完全图。

10、若 G 的任何两个顶点均由一条 H 通路连接着，则称G 是H连通的。

??G?1?(1)证明：若G是H连通的，且p?4,则q??(3p?1)?.?2?

?1?q?(3p?1) （2）对于p≧4，构造一个具有 的H连通图G。 ??2?? 39

分析：根据定理5.3.1有2q?pd(vi)/2 ?d(v)，因此q??i?1ii?1pp而

?d(v)?p??(G)，所以q≥p*δ(G)/2，因此如果能判断δ(G)≥3，则有

ii?1 q ? p ( G ) / 2 ? 3 P / 2 ? ? p 1 ) ? ;下面的证明关键是判断δ(G)≥3。 ? ?(3???2??

证明：（1）任取w∈V(G),由于G是连通的，所以d(w)≥1。

若d(w)=1,则与w邻接的顶点u与w之间不可能有一条H 通路连接它们，否则因为p≥4，所以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, 即：2q≥3p,也即q ≥ 3p/2

(ⅰ) 若p为奇数，于是

1(ⅱ) 若p为偶数，则3p为偶数，于是

1q?(3p?1);2?1?q??(3p?1)?;?2??1?q?(3p?1);??综合以上各种情况 ，有： 2??

（2）(ⅰ)当p=偶数时，q=3p/2，满足条件的图如下图(a);

(ⅱ) 当p=奇数时， q ? ? ( 3 p ? 1 ) ?满足条件的图如下图(b); ,… ?1?2??… 图(a)

40

… … 图(b)

11、证明：若G是一个具有 p≧2δ的连通简单图，则 G 有一条长度至少是2δ的通路。 分析：使用反证法，假设G 中没有一条长度大于或等于2δ的通路。先找到图G的一条最长通路P，设其长度为m，由假设m<2δ。再在P的基础上构造一条长度为m+1的回路C，显然C中包含的顶点数小<2δ，由于p≧2δ，所以图G至少还有一个顶点v不在该圈中，又由于G是连通的，所以v到C上有一条通路P’。于是P’+C的长度等于通路P的长度的通路构成了一条比P更长的通路，这与P是G的一条最长通路矛盾。从而本题可得到证明。

证明：(用反证法)设 P ? V ? V是G的最长通路,其长度为m，假设m<2δ。 V12m?1由P是G的最长通路，则V1,Vm+1只能与 P中的顶点相邻，注意到 G 是简单图 令S?{viv1vi?1?E(G)},T?{vivm?1vi?E(G)} ?S?d（v1）??，T?d（vm?1）??。由定义知：vm?1?S?T,因此，S?T?m?2?,于是S?T??,

事实上，?2??S?T?S?T?S?T?????S?T?2??S?T S?T?0,即S?T??。?

设vi?S?T??,从而有G中的长为m?1的回路C：v1v2?vivm?1vm?vi?1v1.因p?2?,m?1?2?,所以，C外至少还有一个顶点v0?V（G）。 由G连通可知，有一条P外的通路与C连接。不妨设v0vj?E（G），1?j?m?1. 是有通路P?：vvv?vv?vvvv?v.且P??P,此与P的假设矛盾！0jj?11i?1mm?1ii?11 故结论成立。

12、设p(?3)阶简单图G的度序列为：d1?d2???dp.证明：若对任何m,1

1?m?(p?1)/2,均有dm?m若p为奇数，还有d1?（p?1）则G是H图。（p?1） 41 22

本文来源：https://www.bwwdw.com/article/0tht.html