资源描述：
《离散数学 第7章 习题解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第7章习题解答7.1(1),(2),(3),(5)都能构成无向图的度数列,其中除(5)外又都能构成无向简单图的度数列.分析1°非负整数列能构成无向图的度数列当且仅当为偶数,即中的奇数为偶数个.（1）,(2),(3),(5)中分别有4个,0个,4个,4个奇数,所以,它们都能构成无向图的度数列,当然,所对应的无向图很可能是非简单图.而(4)中有3个奇数,因而它不能构成无向图度数列.否则就违背了握手定理的推论.2°(5)虽然能构成无向图的度数列,但不能构成无向简单度数列.否则,若存在无向简单图G,以1,3,3,3为度数列,不妨设G中顶点为,且,于是而只能与之一相邻,设与相邻,
2、这样一来,除能达到3度外,都达不到3度,这是矛盾的.在图7.5所示的4个图中,(1)以1为度数列,(2)以2为度数列,(3)以3为度数列,(4)以4为度数列(非简单图).7.2设有几简单图D以2,2,3,3为度数列,对应的顶点分别为,由于所示,由此可知,D的出度列为2,2,1,0,且满足.请读者画出一个有向图.以2,2,3,3为度数列,且以0,0,2,3为入度列,以2,2,1,0为出度列.7.3D的入度列不可能为1,1,1,1.否则,必有出度列为2,2,2,2(因为,)此时,入度列元素之和为4,不等于出度列元素之和8,这违背握手定理.类似地讨论可知,1,1,1,1也不能
3、为D的出席列.7.4不能.N阶无向简单图的最大度而这里的n个正整数彼此不同,因而这n个数不能构成无向简单图的度数列,否则所得图的最大度大于n,这与最大度应该小于等于n-1矛盾.7.5(1)16个顶点.图中边数,设图中的顶点数为.根据握手定理可知所以,(2)13个顶点.图中边数,设3度顶点个数为x,由握手定理有由此方程解出.于是图中顶点数(3)由握手定理及各顶点度数均相同,寻找方程的非负整数解,这里不会出现均为奇数的情况.其中为阶级,即顶点数,为度数共可得到下面10种情况.①个顶点,度数为48.此图一定是由一个顶点的24个环构成,当然为非简单图.②2个顶点,每个顶点的度数
4、均为24.这样的图有多种非同构的情况,一定为非简单图.③3个顶点,每个顶点的度数均为16.所地应的图也都是非简单图.④4个顶点,每个顶点的度数均为12.所对应的图也都是非简单图.⑤6个顶点，每个顶点的度数均为8，所对应的图也都是非简单图.⑥个顶点,每个顶点的度数均为6.所对应的非同构的图中有简单图,也有非简单图.⑦12个顶点,每个顶点的度数均为4.所对应的非同构的图中有简单图,也有非简单图.⑧16个顶点,每个顶点的度数均为3,所对应的非同构的图中有简单图,也有非简单图.⑨24个顶点,每个顶点的度数均为2.所对应的非同构的图中有简单图,也有非简单图.⑩48个顶点,每个顶点
5、的度数均为1,所对应的图是唯一的,即由24个构成的简单图.分析由于n阶无向简单图G中,,的以①-⑤所对应的图不可能有简单图.⑥-⑨既有简单图,也有非简单图,读者可以画出若干个非同构的图,而⑩只能为简单图.7.6设G为n阶图,由握手定理可知,所以,这里,为不大于的最大整数,例如7.7由于,说明G中任何顶点的度数,可是由于G为简单图,因而,这又使得,于是,也就是说,G中每个顶点的度数都是,因而应有.于是G为阶正则图,即G为n阶完全图7.8由G的补图的定义可知,为,由于n为奇数,所以,中各项顶点的度数为偶数.对于任意的应有且其中表示在G中的度数,表示在中的度数.由于为偶数,所
6、以,与同为奇数或同为偶数,因而若G有r个奇度顶点,则也有r个奇度顶点.7.9由于所以,.而n阶有向简单图中,边数,所以,应有这就导致,这说明D为n阶完全图,且.7.10图7.6给出了的18个非同构的子图,其中有11个生成子图(8-18),其中连通的有6个11,12,13,14,16,17).图7.6中,n,m分别为顶点数和边数.7.11有11个生成子图,在图7.6中,它们分别如图8-18所示.要判断它们之中哪些是自补图,首先要知道同构图的性质,设与的顶点数和边数.若,则且.(8)的补图为,它们的边数不同,所以,不可能同构.因而(8)与(14)均不是自补图类似地,(9)的
7、补图为(13),它们也非同构,因而它们也都不是自补图.(10)与(12)互为补图,它们非同构,因而它们都不是自补图.(15)与(17)互为补图,它们非同构,所以,它们都不是自补图.类似地,(16)与(18)互为补图且非同构,所以,它们也都不是自补图.而(11)与自己的补图同构,所以,(11)是自补图.7.123阶有向完全图共有20个非同构的子图,见图7.7所示,其中(5)-(20)为生成子图,生成子图中(8),(13),(16),(19)均为自补图.分析在图7.7所示的生成子图中,(5)与(11)互为补图,(6)与(10)互为补图,(7)
