G第十四章部分课后习题参考答案5、设无向图G有10条边,3度与4度顶点各2个,其余顶点的度数均小于3,问G至、少有多少个顶点?在最少顶点的情况下,写出度数列、解:由握手定理图G的度数之和为:21020()(G)。3度与4度顶点各2个,这4个顶点的度数之和为14度。其余顶点的度数共有6度。其余顶点的度数均小于3,欲使G的顶点最少,其余顶点的度数应都取2,所以,G至少有7个顶点,出度数列为3,3,4,4,2,2,2,()4,()2.GG7、设有向图D的度数列为2,3,2,3,出度列为1,2,1,1,求D的入度列,并求(D),(D),(D),(),D(D),(D).解:D的度数列为2,3,2,3,出度列为1,2,1,1,D的入度列为1,1,1,2.()3,()2,DD(D)2,()1,D(D)2,(D)18、设无向图中有6条边,3度与5度顶点各1个,其余顶点都是2度点,问该图有多少个顶点?解:由握手定理图G的度数之和为:2612设2度点x个,则31512x12,x2,该图有4个顶点.14、下面给出的两个正整数数列中哪个是可图化的?对可图化的数列,试给出3种非同构的无向图,其中至少有两个时简单图。(1)2,2,3,3,4,4,5(2)2,2,2,2,3,3,4,4解:(1)2+2+3+3+4+4+5=23是奇数,不可图化;(2)2+2+2+2+3+3+4+4=16,是偶数,可图化;18、设有3个4阶4条边的无向简单图G1、G2、G3,证明它们至少有两个是同构的。证明:4阶4条边的无向简单图的顶点的最大度数为3,度数之和为8,因而度数列1kkkG3为2,2,2,2;3,2,2,1;3,3,1,1。但3,3,1,1对应的图不是简单图。所以从同构的观点看,4阶4条边的无向简单图只有两个:所以,G1、G2、G3至少有两个是同构的。20、已知n阶无向简单图G有m条边,试求G的补图G的边数m。解:n(n1)m2m21、无向图G如下图(1)求G的全部点割集与边割集,指出其中的割点和桥;(2)求G的点连通度k(G)与边连通度(G)。ae1e2debe5解:点割集:{a,b},(d)e3e4c边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}()=(GG)=123、求G的点连通度(G)、边连通度(G)与最小度数()。G解:(G)2、(G)3、()428、设n阶无向简单图为3-正则图,且边数m与n满足2n-3=m问这样的无向图有几种非同构的情况?解:n2m得n=6,m=9.2n3m2A000021013020101000000202020101000000202020004042331、设图G和它的部图G的边数分别为m和m,试确定G的阶数。解:mmn(n1)21得n18(mm)245、有向图D如图(1)求v2到v5长度为1,2,3,4的通路数;(2)求v5到v5长度为1,2,3,4的回路数;(3)求D中长度为4的通路数;(4)求D中长度小于或等于4的回路数;(5)写出D的可达矩阵。v1v4v5v2v3解:有向图D的邻接矩阵为:0000010111,A010200100A20202002000000000440400400004A404000404AAAA0152421422521552221552225(1)v2到v5长度为1,2,3,4的通路数为0,2,0,0;(2)v5到v5长度为1,2,3,4的回路数为0,0,4,0;(3)D中长度为4的通路数为32;(4)D中长度小于或等于4的回路数10;3111(4)出D的可达矩阵1P111111111111111111111第十六章部分课后习题参考答案1、画出所有5阶和7阶非同构的无向树.2、一棵无向树T有5片树叶,3个2度分支点,其余的分支点都是3度顶点,问T有几个顶点?解:设3度分支点x个,则51323x2(53x1),解得x3T有11个顶点3、无向树T有8个树叶,2个3度分支点,其余的分支点都是4度顶点,问T有几个4度分支点?根据T的度数列,请至少画出4棵非同构的无向树。解:设4度分支点x个,则81234x2(82x1),解得x2度数列1111111133444至in4、棵无向树T有i几片树叶?(i=2,3,…,k)个i度分支点,其余顶点都是树叶,问T应该有解:设树叶片,则xniix12(nix1),解得x(2)ni2评论:2,3,4题都是用了两个结论,一是握手定理,二是mn15、n(n≥3)阶无向树T的最大度少为几?最多为几?解:2,n-16、若n(n≥3)阶无向树T的最大度=2,问T中最长的路径长度为几?解:n-17、证明:n(n≥2)阶无向树不是欧拉图.证明:无向树没有回路,因而不是欧拉图。8、证明:n(n≥2)阶无向树不是哈密顿图.证明:无向树没有回路,因而不是哈密顿图。9、证明:任何无向树T都是二部图.证明:无向树没有回路,因而不存在技术长度的圈,是二部图。10、什么样的无向树T既是欧拉图,又是哈密顿图?解:一阶无向树14、设e为无向连通图G中的一条边,e在G的任何生成树中,问e应有什么性质?解:e是桥15、设e为无向连通图G中的一条边,e不在G的任何生成树中,问e应有什么性质?解:e是环23、已知n阶m条的无向图G是k(k≥2)棵树组成的森林,证明:m=n-k.;证明:数学归纳法。k=1时,m=n-1,结论成立;设k=t-1(t-11)时,结论成立,当k=t时,无向图G是t棵树组成的森林,任取两棵树,每棵树任取一个顶点,这两个顶点连线。则所得新图有t-1棵树,所以m=n-(k-1).所以原图中m=n-k得证。24、在图16.6所示2图中,实边所示的生成子图T是该图的生成树.(1)指出T的弦,及每条弦对应的基本回路和对应T的基本回路系统.5(2)指出T的所有树枝,及每条树枝对应的基本割集和对应T的基本割集系统.(a)(b)图16.16解:(a)T的弦:c,d,g,hT的基本回路系统:S={{a,c,b},{a,b,f,d},{e,a,b,h},{e,a,b,f,g}}T的所有树枝:e,a,b,fT的基本割集系统:S={{e,g,h},{a,c,d,g,h},{b,c,d,g,h},{f,d,g}}(b)有关问题仿照给出25、求图16.17所示带权图中的最小生成树.(a)(b)图16.17解:注:答案不唯一。37、画一棵权为3,4,5,6,7,8,9的最优2叉树,并计算出它的权.638.下面给出的各符号串集合哪些是前缀码?A1={0,10,110,1111}是前缀码A2={1,01,001,000}是前缀码A3={1,11,101,001,0011}不是前缀码A4={b,c,aa,ac,aba,abb,abc}是前缀码A5={b,c,a,aa,ac,abc,abb,aba}不是前缀码41.设7个字母在通信中出现的频率如下:a:35%b:20%c:15%d:10%e:10%f:5%g:5%用Huffman算法求传输它们的前缀码.要求画出最优树,指出每个字母对应的编码.并指出传输10n(n≥2)个按上述频率出现的字母,需要多少个二进制数字.解:a:01b:10c:000d:110e:001f:1111g:1110W(T)=5*4+5*4+10*3+10*3+15*3+20*2+35*2=255传输10n(n≥2)个按上述频率出现的字母,需要255*10n-2个二进制数字.7