离散课后习题5

第十四章部分课后习题参照答案5、设无向图G有10条边，3度与4度极点各2个，其他极点的度数均小于3，问G至G、罕有多少个极点在最少极点的状况下，写出度数列、( )(G)。解：由握手定理图G的度数之和为：210203度与4度极点各2个，这4个极点的度数之和为14度。其他极点的度数共有6度。其他极点的度数均小于3，欲使G的极点最少，其他极点的度数应都取2,因此，G起码有7个极点,出度数列为3,3,4,4,2,2,2,(G)4,G( )2.7、设有向图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.(D)3,D( )2,(D)2,(D)1,(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+3+3+4+4=16,是偶数，可图化；18、设有3个4阶4条边的无向简单图G1、G2、G3，证明它们起码有两个是同构的。证明：4阶4条边的无向简单图的极点的最大度数为3，度数之和为8，因此度数列1为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)m解：m′221、无向图G以下列图(1)求G的所有点割集与边割集，指出此中的割点和桥；求G的点连通度k(G)与边连通度(G)。e1e2dbe5

ee3

e4c解：点割集:{a,b},(d)边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}k( )=)=1(GG23、求G的点连通度k(G)、边连通度G( )与最小度数G( )。解：k(G)2、(G)3、(G)428、设n阶无向简单图为3-正则图，且边数m与n知足2n-3=m问这样的无向图有几种非同构的状况3n2m解：得n=6,m=9.2n3m2、设图G和它的部图G的边数分别为m和m，试确立G的阶数。31解：mmn(n1)得n118(mm)2245、有向图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的毗邻矩阵为：000010101020200101000000202020A00001，A201010A32020010100000020202001010202000000400000121544040052522A400004AA2A3A42121540400425220404025254v2到v5长度为1，2，3，4的通路数为0,2,0,0；v5到v5长度为1，2，3，4的回路数为0,0,4,0；(3)D中长度为4的通路数为32；(4)D中长度小于或等于4的回路数10；31111111111(4)出D的可达矩阵P111111111111111第十六章部分课后习题参照答案1、画出所有5阶和7阶非同构的无向树.2、一棵无向树T有5片树叶，3个2度分支点，其他的分支点都是3度极点，问T有几个极点解：设3度分支点x个，则51323x2(53x1)，解得x3有11个极点3、无向树T有8个树叶，2个3度分支点，其他的分支点都是4度极点，问T有几个4度分支点依据T的度数列，请起码画出4棵非同构的无向树。解：设4度分支点x个，则81234x2(82x1)，解得x2度数列44、棵无向树T有ni(i=2，3，，k)个i度分支点，其他极点都是树叶，问T应当有几片树叶解：设树叶x片，则niix12(nix1)，解得x(i2)ni2议论：2，3，4题都是用了两个结论,一是握手定理，二是mn15、n(n≥3)阶无向树T的最大度解：2，n-16、若n(n≥3)阶无向树T的最大度解：n-1

起码为几最多为几=2，问T中最长的路径长度为几7、证明：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-1≥1)时，结论建立，当k=t时,无向图G是t棵树构成的丛林,任取两棵树，每棵树任取一个极点，这两个极点连线。则所得新图有t-1棵树，因此m=n-（k-1）.因此原图中m=n-k得证。24、在图所示2图中，实边所示的生成子图T是该图的生成树.(1)指出T的弦，及每条弦对应的基本回路和对应T的基本回路系统.5指出T的所有树枝，及每条树枝对应的基本割集和对应T的基本割集系统.(a)(b)图解：(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、求图所示带权图中的最小生成树.(a)(b)图解：注：答案不独一。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%5%用Huffman算法求传输它们的前缀码.要求画出最优树，指出每个字母对应的编码.并指出传