离散数学7习题解答.docVIP

第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中顶点为,且,于是而只能与之一相邻,设与相邻,这样一来,除能达到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.3 D的入度列不可能为1,1,1,1.否则,必有出度列为2,2,2,2(因为,)此时,入度列元素之和为4,不等于出度列元素之和8,这违背握手定理.类似地讨论可知,1,1,1,1也不能为D的出席列. 7.4 不能. N阶无向简单图的最大度而这里的n个正整数彼此不同,因而这n个数不能构成无向简单图的度数列,否则所得图的最大度大于n,这与最大度应该小于等于n-1矛盾. 7.5 (1) 16个顶点. 图中边数,设图中的顶点数为.根据握手定理可知 所以, (2) 13个顶点.图中边数,设3度顶点个数为x,由握手定理有 由此方程解出.于是图中顶点数 (3) 由握手定理及各顶点度数均相同,寻找方程 的非负整数解,这里不会出现均为奇数的情况. 其中为阶级,即顶点数,为度数共可得到下面10种情况. ①个顶点,度数为48.此图一定是由一个顶点的24个环构成,当然为非简单图. ②2个顶点,每个顶点的度数均为24.这样的图有多种非同构的情况,一定为非简单图. ③3个顶点,每个顶点的度数均为16.所地应的图也都是非简单图. ④4个顶点,每个顶点的度数均为12. 所对应的图也都是非简单图. ⑤6个顶点，每个顶点的度数均为8，所对应的图也都是非简单图. ⑥个顶点,每个顶点的度数均为6.所对应的非同构的图中有简单图,也有非简单图. ⑦12个顶点,每个顶点的度数均为4. 所对应的非同构的图中有简单图,也有非简单图. ⑧16个顶点,每个顶点的度数均为3,所对应的非同构的图中有简单图,也有非简单图. ⑨24个顶点,每个顶点的度数均为2.所对应的非同构的图中有简单图,也有非简单图. ⑩48个顶点,每个顶点的度数均为1,所对应的图是唯一的,即由24个构成的简单图. 分析 由于n阶无向简单图G中,,的以①-⑤所对应的图不可能有简单图.⑥-⑨既有简单图,也有非简单图,读者可以画出若干个非同构的图,而⑩只能为简单图. 7.6 设G为n阶图,由握手定理可知 , 所以, 这里, 为不大于的最大整数,例如 7.7 由于,说明G中任何顶点的度数,可是由于G为简单图,因而,这又使得,于是,也就是说,G中每个顶点的度数都是,因而应有.于是G为阶正则图,即G为n阶完全图 7.8 由G的补图的定义可知,为,由于n为奇数,所以, 中各项顶点的度数为偶数.对于任意的应有且 其中表示在G中的度数, 表示在中的度数.由于为偶数,所以, 与同为奇数或同为偶数,因而若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)的补图为(13),它们也非同构,因而它们也都不是自补图.(10)与(12)互为补图,它们非同构,因而它们都不是自补图.(15)与(17)互为补图,它们非同构,所以,它们都不是自补图.类似地,(16)与(18)互为补图且非同构,所以,它们也都不是自补图. 而(11)与自己的补图同构,所以,(11)是自补图. 7.12 3阶有向完全图共有20个非同构的子图,见图7.7所示,其中(5)-(20)为