《苏XI友离散数学作业(7-9章).ppt》由会员分享，可在线阅读，更多相关《苏XI友离散数学作业(7-9章).ppt（15页珍藏版）》请在三一文库上搜索。
1、2019/9/2,1,作业 13,P173-7.1 下列各组数中,哪些能构成无向图的度数列?哪些能构成无向简单图的度数列? (1)1,1,1,2,3.能构成无向简单图的度数列.例如, (2)3,3,3,3.可以构成无向简单图的度数列,例如,2019/9/2,2,作业 13,(3)1,3,3,3.不能构成无向简单图的度数列.因为有一个悬挂点,则其余三个顶点度数不可能均为3,但可构成无向图的度数列,例如,2019/9/2,3,作业13,P173-7.5 下面各无向图中有几个顶点? (2)21条边,3个4度顶点,其余的都是3度顶点. 解.设该图有n个顶点,则由握手定理 34(n3)3=221, 解得
2、,n=13.故该图有13个顶点. P173-7.6 35条边,每个顶点的度数至少为3的图最多有几个顶点? 解.设该图最多有n个顶点,由握手定理 3n352, 则 n70/3=23. 故该图最多有23个顶点.,2019/9/2,4,作业13,P173-7.13 设G1,G2,G3均为4阶无向简单图,它们均有两条边,它们能彼此均非同构吗?为什么? 解.G1,G2,G3彼此不能均非同构.因为4阶2条边的非同构无 向简单图只有2个. 事实上,因为图只有两条边,故总度数为4,且为无向简单图, 因而每个顶点度数最多为2.将4分解为4个数的和且每个数 不超过2,得下面3组数: (0,0,2,2), (0,1
3、,1,2), (1,1,1,1) 而(0,0,2,2)不可能是一4阶2条边的无向简单图的度数列, 因2个顶点为孤立点,则另两个顶点的度数最多为1,否则,会 出现平行边或环.所以(4,2)图只有2个非同构的图,如上图.,2019/9/2,5,作业14,补充1 (1)若无向图G中只有两个奇度顶点,则这两个奇度顶点一定是连通的. (2)若有向图D中只有两个奇度顶点,则它们一个可达另一个或相互可达吗? (1)证明.设G中的两个奇度顶点分别为u和v,若u和v不连通,即它们之间无任何通路,则G至少有两个连通分支G1,G2,使得u和v分别属于G1和G2,于是G1和G2中各有1个奇度顶点,这与握手定理的推论矛
4、盾.因而u和v一定是连通的. (2)解.有向图D中只有两个奇度顶点u和v,则u与v不一定相互可达,也不一定一个可达另一个. 如右图,顶点u和v的度数均为1,w的度数为2, 但u不可达v,v也不可达u.,2019/9/2,6,作业14,补充2 设G是n阶无向简单图,如果G中每一对顶点的度数之和均大于等于n-1,那么G是连通图. 证明.假设G不是连通图,则G至少有两个连通分支G1,G2,设G1中有n1个顶点,G2中有n2个顶点,则 n1+n2n. 分别从G1和G2中任取一个顶点u,v,由于G是简单图,从而G1和G2也都是简单图,所以 d(u)n1-1,d(v)n2-1, 故d(u)+d(v)n1+
5、n2-2n-2,与题设矛盾.,2019/9/2,7,作业14,P174-7.18 有向图D如下图所示.求D中长度为4的通路总数,并指出其中有多少条是回路?又有几条是 v3到v4的通路? 解.图D的邻接矩阵为 则 由A4得,aij=15,aii=3,a34=2,故D中长度为4的 通路有15条,其中有3条回路,从v3到v4长度为4的通路有 2条.,i=1,4,i=1,j=1,4,4,(4),(4),(4),2019/9/2,8,作业14,P203-9.1 设无向树T有3个3度顶点,2个2度顶点,其余顶点都是树叶,问T有几片树叶? 解.设T有t片树叶,则T的总顶点数为3+2+t,总边数为3+2+t-
6、1=4+t,由握手定理,有 2(4+t)=33+22+t, 解得t=5,故T有5片树叶. P203-9.4 已知n(n2)阶无向简单图G有n-1条边,G一定为树吗? 解.不一定.如G为非连通图时就不是树. 例如,在图G中,n=5,m=4,m=n-1,但G 不是树.,2019/9/2,9,作业14,P203-9.7 在下图所示的无向图G中,实线边所示的子图为G的一棵生成树T,求G对应于T的基本回路系统和基本割集系统. 解.对应于弦c的基本回路为:Cc=adcb, 对应于弦e的基本回路为:Ce=ade, 对应于弦g的基本回路为:Cg=agf, 对应于弦h的基本回路为:Ch=afhb, 所以对应于T
7、的基本回路系统为:adcb,ade,agf,afhb. 对应于树枝a的基本割集为:Sa=a,e,c,g,h, 对应于树枝b的基本割集为:Sb=b,c,h, 对应于树枝d的基本割集为:Sd=c,d,e, 对应于树枝f的基本割集为:Sf=f,g,h, 所以T的基本割集为:a,e,c,g,h,b,c,h,c,d,e,f,g,h.,2019/9/2,10,作业14,P203-9.8 求下图所示两带权图的最小生成树,并计算它们的权. 解.(a)的最小生成树为 T1,如下图.T1的权为: W(T1)=1+2+3+1=7. (b)的最小生成树为 T2,如右图.T2的权为: W(T2)=1+2+4+4=11.
8、,2019/9/2,11,作业15,P204-9.11 下图给出的2元树表达一个算式. (1)给出这个算式的表达式; (2)给出算式的波兰符号法表达式; (3)给出算式的逆波兰符号法表达式. 解.(1)(abc)de) (fg)hij. (2)abcde fghij. (3)abcdefg hij.,2019/9/2,12,作业15,P204-9.13 设7个字母在通信中出现的频率如下: a:35%,b:20%,c:15%,d:10%,e:10%,f:5%,g:5%.求 传输这7个字母的最佳前缀码. 解.以100乘各频率并由小到大 排列为:w1=5,w2=5,w3=10, w4=10,w5=1
9、5,w6=20,w7=35. 用huffman算法求带权为 w1,w2,w3,w4,w5,w6,w7的 最优2元树如右图. 最佳前缀码为:01,11,001,100,101,0000,0001. 对应的码子传输的字母为:11传a,01传b,101传c, 100传d,001传e,0001传f,0000传g.,2019/9/2,13,作业15,P188-8.3 完全二部图Kr,s中,边数m为多少? 解.Kr,s中,边数m为:m=rs. P188-8.6 画一个无向欧拉图,使它具有: (1)偶数个顶点,偶数条边; (2)奇数个顶点,奇数条边; (3)偶数个顶点,奇数条边; (4)奇数个顶点,偶数条边
10、. 解.(1) (2) (3) (4),2019/9/2,14,作业15,P189-8.8 画一个无向图,使它是: (1)既是欧拉图,又是哈密尔顿图; (2)是欧拉图,而不是哈密尔顿图; (3)是哈密尔顿图,而不是欧拉图; (4)既不是欧拉图,也不是哈密尔顿图. 解. (1) (2) (3) (4),2019/9/2,15,作业15,P189-8.18 彼得森图如下图所示.证明它不是二部图,也不是欧拉图,更不是平面图. 证明.因为彼得森图中有长度为 奇数的回路v1v2v3v4v5v1,所以 它不是二部图. 图中每个顶点的度数均为3, 故它也不是欧拉图. 又因为它可以收缩为K5,由库拉托夫斯基定理可 知它也不是平面图.,