第七章 特 殊 图 类.docx

《第七章 特 殊 图 类.docx》由会员分享，可在线阅读，更多相关《第七章 特 殊 图 类.docx（15页珍藏版）》请在第一文库网上搜索。

1、第七章特殊图类习题7.11.设树T有6条边，试问T有多少个结点？解2.3.因m=n-1,这里m=6,所以n=6+1=7.若无向图G中有n个结点，n-1条边，G为树。这个命题正确吗？为什么？不正确。K3与平凡图构成的非连通图中有4个结点3条边，但是它不是树。设无向图G有n个结点，n-1条边，则G为连通图当且仅当G中无回路。证明必要性。因为G中有n个结点，边数m=n-1,又因为G是连通的，由本节定理1可知，G为树，因而G中无回路。再证充分性。因为G中无回路，又因为边数m=n1,由本节定理1,可知G为树，所以G是连通的。4 .设G是一个森林，由3个连通分支组成，若它有15个结点，试问G有多少条边？解

2、因m=n-r,这里n=15,r=3,所以m=15-3=12,即G有12条边。5 .画出具有6个结点的所有不同构的树。6 解6个结点的所有不同构的树如图7-1所示。7 .任何一棵非平凡树中，至少有两片树叶。证明由定理1,在任意的(巩勿)树中，边数力=-1；所以，由握手定理得4()=2Z=2(1)i=I若T没有树叶，则由于T是连通图，所以丁中任一结点均有2(.)22,从而dy)2ni/=1则与矛盾。若树T仅有1片树叶，则其余-1个结点的度数不小于2,于是2Z(j)2(1)+1=2-1/=1从而、相矛盾。综合，得知T中至少有两片树叶。.在图7-2中，(1),所示的连通图中各有几棵非同构的生成树？图7

3、-2解图7-2中共有两棵非同构的生成树(如图73(D,(2)o图72(2)中共有3棵(4)图7-4图7-37 .在图7-4中所示的带权图G共有多少棵生成树，它们的权各为多少？其中哪些是图中的最小生成树？解在图74中共有8棵生成树，如图7-5(D所示，第i生成树用T(=,2,8)表示。Irer)=Irer)=8,i16卜Cr)=Irer)=6,IrCr)=WCr)=眩Cr)=7,25378IrCr)=9。其中T,T是图中的最小生成树。J-9.用Kruska1算法，求图7-6的最小生成树，并计算出该生成树的权。解最小生成树T如图77所示，W(T)=180习题7.21.一个有向图G,仅有的一个结点入

4、度为0,其余所有结点的入度均为1,G一定是根树吗？解不一定是。如图7-8就不是根树.2 .五个结点可以形成多少棵根树？并指出这些根树都是几元树。解五个结点可形成3棵非同构的无向树，如图7-9(1),(2),所示。由可生成2棵非同构的根树，如图7-9，所示。为3元树，为4元树。由可生成4棵非同构的根树，如图79(6),(7),(8),(9)所示。为2元树，（7）为2元树，为3元树，为2元树。由可生成3棵非同构的示。为1元树，（11）,为2元树。由此可知，五个结点共形成9棵非同构的根树。3 .根树中最长路径的端点都是树叶吗？为什么？解不是。根树中最长路径的端点一个是树根，另一个是树叶，因为根树的高

5、等于最长路径的长度，应从树根开始。4 .证明本节定理4（完全二元树有奇数个结点）。证明设完全二元树T有/个叶结点，n2分支结点，则T的结点数为n=+n,2边数m=2n2,有握手定理可得：2nj=n（j-n所以，n5n-J,因a此，n=n0+n2=2n0-1o即二元树有奇数个结点。5 .对图7-10给出的二元树分别进行先根遍历、中根遍/j历、后根遍历并写出结果。7/解先根遍历：abdfgechiXei中根遍历：fdgbeahcii后根遍历：fgdebhica6 .求带权2、3、5、7、8、11的最优树。图7-10解第一步，取最小的两个权2和3,它们对应的树叶的父亲带权为5,如图7-11a；第二步

6、，在5,5,7,8,11中取最小的两个权5和5,它们对应的树叶的父亲带权为10,如图7-11b；第三步，在10,7,8,11中取最小的两个权7和8,它们对应的树叶的父亲带权为15,如图7-11c；第四步，在10,15,11中取最小的两个权10和11,它们对应的结点的父亲带权为21,如图7-1Id；第五步，15,21对应的结点的父亲带权为36,如图7-11e0图7-1Ie所示的树为带权2、3、5、7、8、11的最优树。图7-11习题7.31.在图7-12所示的三个图中，哪几个是偶图？哪几个不是偶图？是偶图的，请给出互补结点子集；不是偶图的，请说明理由。解图是偶图，互补结点子集为：(=,Me,1=

7、图是偶图，互补结点子集为：犷=/,/,Iz=,4e,幺；图不是偶图。122试证明树是一个偶图。证明设G=V,6是一棵树，任选V后V,定义V的两个子集如下：1=/(,()为偶数,V?=V-V1O现证明V1中任二结点之间无边存在。若存在一条边(u,v)E,u,vV,由于树中任意两个结点之间仅存在惟一一条路，设V。到U的路为V0VV2VkU,则V0V1V2-VkU的长度为偶数,因(u,v)E,所以v0vjv2vkuv是Vo到V的一条通路，且该通路的长度k+2为奇数，从而VVVVUV不是路，因此V必与某个V(i=0,1,2产，10相同，从而VVvVUV012kii+1i+2k是G中的一个圈，这与G是树

8、矛盾。同理可证，V2中任意两个结点之间无边存在。故G中的每条边(u,v)E,必有uVvV或uV,2vv,因此G是具有互补结点子集V和V2的偶图。3一次舞会，共有n位男士和n位女士参加，已知每位男士至少认识两位女士，而每位女士至多认识两位男士，问能否将男士和女士分配为n对，使得每对中的男士和女士彼此都认识？解将n位男士和n位女士分别用结点表示，若某位男士认识某位女士，则在代表他们的结点之间连一条线，得到一个偶图G,它的互补结点子集片和V2分别表示n位男士和n位女士，由题可知，V1中的每个结点度数至少为2,而V2中的每个结点度数至多为2,从而它满足t条件(仁2),因此存在从V1到V,的匹配，故可将

9、男士和女士分配为n对，使得每对中的男士和女士彼此都认识。4今有赵、钱、孙、李、周五位教师，要承担语文、数学、物理、化学、英语五门课程。已知赵熟悉数学、物理、化学三门课程，钱熟悉语文、数学、物理、英语四门课程，孙、李、周三人只熟悉数学、物理两门课程。问能否安排他们五人每人只上一门自己熟悉的课程，使得每门课程都有人教。说明理由。解不能。用结点表示五位教师(V)和五门课(V)，在教师和他熟悉的课程之间I2连一条线，得到一个偶图G,其中，V1中的孙、李、周三个结点只与数学、物理两个结点相邻接，故不满足相异性条件，因此不存在从V,到V,的匹配，故不能按题设要求的安排。习题7.41.试证明图713所示的两

10、个图均为平面图。证明将图7-13所示的两个图改画为图7-14所示的两个图,可以看出图(1),(2)任何两边除在结点处相交外，无其它交叉点即可。因此，图7-13所示的两个图都是平面图.2.图7-13指出图7-15所示的两个图各有几个面；写出每个面的边界和秩。图7-15解图7-15中有五个面,分别为F:abea,F:acea,F:acda,F:cdec,1234Fabeda0它们的秩分别为r(F)=r(F(F)=r(F?=3,r(F)4图7-15有两个面，其中、限甫为F%cfeda,无限城F:acbcfea,它们的秩r(Fj)=r(F)=6,3.4证明：在有6个结点、12条边的连通简单图中，每个面

11、均由3条边围成。证明设该连通简单图的面数为r,由EUIer公式可得，6-12+r=2,所以尸8,其8个面分别设为ri(i=1,2,-,8)o因是简单图，故每个面至少由3条边围成。即D(r)38=24o而由本届定理1知，D(r)=2勿=212=24o因此每个面/=1只能由3条边围成。4 .指出图7-16所示的图为非面图。图7-16图7-17解去掉图7-16中的两条边，并给结点表上名称的图7-17(1),在将图7-17改画图7-17(2),而显然图7-17与均是同胚的，由库拉图斯基定理知，图7-16所示的图为非面图。5 .在简单平面图G中，至少有一个度数小于等于5的结点。证明若G中无圈,则G为森林

12、,结论显然成立,若G中有圈,假设G中有n个结点,m条边,并假设G的所有连通分支为G,G7，G1,每个Gi有叫个结点,条边,则有Z=/7,Z勿=加由于G是简单图,所以每个Gi也是简单图,由本节定理2的推论可知m3n-6,i=1,2,k0从而有vvv勿=乙加乙3一6)=3乙64=3%6436所以m3n-6o再用反证法证明，简单平面图G中至少有一个度数小于等于5的结点。如果G中每个结点的度数均大于等于6,由握手定理可知20=Zdeg()26%,因/=1此1力,代入m3n-6得mWm-6,这显然的矛盾的。故G中至少有一个度数小于等于35的结点。6 .证明小于30条边的简单平面图G中至少有一个度数小于等

13、于4的结点。证明设G是连通平面图。假设G中每一结点V都有deg(v)50因为2m25n,所以n2m50于是，m3n-66m5-6,即5m6m-30o因此，m230,与题设m30矛盾。所以G中必有一个结点的度小于或等于40复习题71 .i棵树T有5个2度结点，3个3度结点，4个4度结点，2个5度结点，其余都是1度结点，问T有多少个1度结点？解假设T有m条边，X个1度结点，则有：m=5+3+4+2+x-12m=52+33+44+25+x解得：x=19,m=32,即T有19个1度结点。2 .设无向vn,m图G是连通图，试证明m2n-1.证明因为，图G是连通图，所以，由本节定理2知图G存在生成树T,而

14、生成树T的边数n-1是不超过图G的边数m的，即mn-103 .设无向n,m图G是森林，且G有P个连通分支，试证明：加=n-p.证明设G的P个连通分支分别为,m1,n2,叫,，nmp,由于森林的每个连通分支都是树，因此，有：m=叫-1，叫=叫-1,，mp=np-1又m1+m2+-mp=m;n1n2+np=n由(1),(2)得：m=n-po4 .T1和T2是连通图G的两棵不同的生成树，a是在T1中但不在T2中的一条边。试证明存在边b,它在中但不在T1中,例9(T-)口和(7)都是G2112的生成树。证明因为，a是在T1中但不在T2中的一条边，所以，12。伯有惟一的圈C,而T1是树，则圈C上一定有一边b不在T1o因此，(T2-b)ua=T2Ua-b是G的生成树。下面证明，(Ta)Db=15b-a也是G而生成树，事实上，因为T1是树，所以T1中的边a是匕的割边，因此T1去掉边a后可得两个连同分支，设为TU知T/又b不在T1中，所以T0b有惟一的圈C,i5 .设无向图G是有比,(2)棵构成的森林，至少在G中添加多少条边才能使G成为一棵树？解设G中的k个连通分支为丁,丁，设结点T,=1,2,石。在G中添加12T/k边(，),/=1,2,次-1,设所得新图为T,则T连