《离散数学》刘任任版第八章

《《离散数学》刘任任版第八章》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、习题81、图屮8.10屮哪些是E图？哪些是半E图?分析：根据欧拉定理及其推论，E图是不含任何奇点的图，半E图是®多含两个奇点的图。解：⑻半E图。(b)E图。(c)非半E图和E图2、试作出一个E图G(p，q)，使得p与q均为奇数。能否作出一个E图G(p,q),使得p为偶数，而q为奇数？如果是p为奇数，q为偶数呢？解：以下E阁中，p与q的奇偶如下表PqG1奇数奇数G2偶数奇数G3奇数偶数G23、求证：若G是E图，则G的每个块也是E图。分析：一个图如果含有E回路，则该图是E图；另一方面一个块是G屮不含割点的

2、极大连通不可分子图，且非割点不可能属于两个或两个以上的块。这样沿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中存在边互不重的回路G，…，Cw,使得£(G)=£(C)u£(C2)u

3、…u£(C„,)分析：G中无奇点，则除了孤立点后其他所有点的度至少为2,而孤立点不与任何边关联，因此在分析由边构成的冋路时可以不加考虑；而如果一个图所有的顶点的度至少为2,则由第五章习题18知该图必含回路。证明：将G中孤立点去掉以后得到图G1,显然G1也是一个无奇点的E图，且#^71^2。由第五章习题18知，G1必含有冋路Ch在图G1-C1中去掉孤立点，得图G2,显然G2仍然是一个无奇点的图，且于是G2中也必含冋路C2,…如此直到Gm中有冋路Cm,且Gm-Cm全为孤立点为止，于是有：£(G)=£(C,

4、)u£(C2)u…u£(CJ5、求证：若G有2k〉0个奇点，则G屮存在k个边互不重的链gi...,2^，使得：E(G)=£(2,)uE(Q2)u-uE(Qk)分析：一个图的E回路去掉一条边以后，将得到一条E链。证明.•设VhV2，…，％，VA.+I，…，V2A为G屮的奇数度顶点，k>l在Vi和Vi+k之间用新边ei连接，i=l,2....k，所得之图记为G*，易知G*的每个顶点均为偶数，从而G*存在E闭链C*。现从C*屮删去ei(i=l,2....k),则C*被分解成k条不相交的链Qi(i=l，2..

5、..k),显然有：E(G)=£(2,)uE(Q2)u…uE(Qk)6、证明：如果(1)G不是2—连通阁，或者(2)G是二分图<乂，¥：>，且X关Y,则G不是H图。分析：G不是2-连通图，说明以0^，于是球^)=1或邮)^0,如果71■⑹=0,则说明G不连通，如G不连通，显然G不是H图，如<⑺=1则G中存在孤立点，因此有

6、是孤立点；即有^(G_X)=

7、r1,^(G_y)=

8、X

9、,如果X关Y,则有ty(G-X)=

10、y

11、>

12、X

13、»j<6y(G-r)=

14、X

15、>

16、r

17、^iEo无论哪个结论成立，醐定理8.2.1都有G不是H图。证明：若(1)成立则G不连通或者是G有割点u,若G不连通，则G不是H图，若G有割点u,取5={11},于是o(G-u)〉S因此G不是H图.若(2)成立，不妨设X

18、y

19、>

20、x

21、=

22、SB

23、J：co(G-S)>

24、S

25、.因此G不是H图.7、证明.•若G是半H阁,则对于V(

26、G)的每一个真子集S,有：分析：图G的权与它的生成子图G’的连通分支数满足：a)(G)

27、S

28、+1.证明:设C是G的一条H通路，任取ScV，易知^c_S)<

29、S

30、+L而C-S是G-S的生成子图.^6ZXG-5)<69(C-5)<

31、S

32、+1.故仍(g-s)s

33、s

34、+i.8、试述H图与E图之间的关系。分析.•H图是指存在一条从某个点出发经过其他顶点

35、有且仅有一次的回路；而E阁是指从某点岀发通过图中所有的边一次且仅有一次的回路。从定义可看出，这两者之间没有充分或必要的关系。g2g4易知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的所有顶点均邻接。由闭包的定义