离散数学第7章习题解答 VIP免费

百度文库•好好学习.天天向上-1第7章习题解答(1),(2),⑶，⑸都能组成无向图的度数列,其中除⑸外又都能组成无向简单图的度数列.分析1°非负整数列〃詔2,…，血能组成无向图的度数列当且仅当f川为r-1偶数，即心,〃2,…，〃”中的奇数为偶数个.(1),(2),(3),⑸中别离有4个,0个,4个,4个奇数，所以，它们都能组成无向图的度数列，固然，所对应的无向图极可能是非简单图•而(4)中有3个奇数，因此它不能组成无向图度数列.不然就违背了握手定理的推论.2°⑸虽然能组成无向图的度数列，但不能组成无向简单度数列.不然，若存在无向简单图G,以1,3,3,3为度数列,不妨设G中极点为儿宀宀宀，且〃(片)=1,于是〃(”2)=d(y3)=J(v4)=3.而儿只能与v2,v3»v4之一相邻,设片与冬相邻，这样一来，除冬能达到3度外，耳宀都达不到3度,这是矛盾的.在图所示的4个图中,(1)以1为度数列，⑵以2为度数列，⑶以3为度数列,(4)以4为度数列(非简单图).⑴(2)(3)(4)困7.5设有几简单图D以2,2,3,3为度数列，对应的极点别离为yrv2,v3,v4,由于J(v)=J+(v)+^-(v),所示，d\vl)-d-(vi)=2-0=Zd+(v2)=d(v2)-d-(v2)百度文库•好好学习.天天向上-2=2-0=2,J*(V3)=d(v3)-d-(v3)=3-2=l,J+(v4)=〃(勺)一旷(勺)=3-3=0由此可知,D的出度列为2,2,1,0,且知足工(广化)=》旷(勺).请读者画出一个有向图.以2,2,3,3为度数列，且以0,0,2,3为入度列，以2,2,1,0为出度列.D的入度列不可能为1,1,1,1.不然，必有出度列为2,2,2,2(因为J(v)=J*(v)+J-(v)),)此时，入度列元素之和为4,不等于出度列元素之和8,这违背握手定理.类似地讨论可知，1,1,1,1也不能为D的出席列.不能.N阶无向简单图的最大度厶＜/7-1,而这里的n个正整数彼此不同,因此这n个数不能组成无向简单图的度数列，不然所得图的最大度大于n,这与最大度应该小于等于n-1矛盾.(1)16个极点.图中边数加=16,设图中的极点数为〃.按照握手定理可知2m=32=》〃(片)=Inr-I所以，n=16.(2)13个极点.图中边数也=21,设3度极点个数为x,由握手定理有2in=42=3x4+3x由此方程解出x=10.于是图中极点数71=3+10=13.(3)III握手定理及各极点度数均相同，寻觅方程2x24=nk的非负整数解，这里不会出现儿k均为奇数的惜况.其中“为阶级，即极点数，£为度数共可取得下面10种情况.①个极点,度数为48.此图必然是由一个极点的24个环组成,固然为非简单图.②2个极点，每一个极点的度数均为24.这样的图有多种非同构的情况，必然为非简单图.③3个极点，每一个极点的度数均为16.所地应的图也都是非简单图.④4个极点，每一个极点的度数均为12.所对应的图也都是非简单图.百度文库•好好学习.天天向上-3⑤6个极点，每一个极点的度数均为8,所对应的图也都是非简单图.⑥个极点，每一个极点的度数均为6.所对应的非同构的图中有简单图，也有非简单图.⑦12个极点，每一个极点的度数均为4.所对应的非同构的图中有简单图,也有非简单图.⑧16个极点，每一个极点的度数均为3,所对应的非同构的图中有简单图，也有非简单图.⑨24个极点，每一个极点的度数均为2.所对应的非同构的图中有简单图，也有非简单图.⑩48个极点，每一个极点的度数均为1,所对应的图是唯一的，即由24个K,■组成的简单图.分析由于n阶无向简单图GA(G)<«-1,的以①所对应的图不可能有简单图•⑥-⑨既有简单图，也有非简单图，读者可以画出若干个非同构的图，而⑩只能为简单图.设G为n阶图，由握手定理可知70=2x35=》〃(*])n3n,所以,这里，匕」为不大于兀的最大整数，例如[_2」=2丄2.5」=2,斤」=23.由于3(G)=n-l,说明G中任何极点v的度数J(v)>J(G)=/7-1,可是由于G为简单图，因此△(G)S-1,这乂使得J(v)匸ZX所以...