第10章习题答案

习题101.(1)图G的度数列为2、2、3、3、4，则G的边数是多少(2)3、3、2、3和5、2、3、1、4能成为图的度数列吗为什么(3)图G有12条边，度数为3的结点有6个，其余结点的度数均小于3，问图G中至多有几个结点为什么解(1)设G有m条边，由握手定理得2m＝＝2＋2＋3＋3＋4＝14，所以G的边数7条。(2)由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为图的度数列。(3)由握手定理得＝2m＝24，度数为3的结点有6个占去18度，还有6度由其它结点占有，其余结点的度数可为0、1、2，当均为2时所用结点数最少，所以应由3个结点占有这6度，即图G中至多有9个结点。2.若有n个人，每个人恰有3个朋友，则n必为偶数。证明设、、…、表示任给的n个人，以、、…、为结点，当且仅当两人为朋友时其对应的结点之间连一条边，这样得到一个简单图G。由握手定理知＝3n必为偶数，从而n必为偶数。3.判断下列各非负整数列哪些是可图化的哪些是可简单图化的-(1)(1，1，1，2，3)。(2)(2，2，2，2，2)。(3)(3，3，3，3)。(4)(1，2，3，4，5)。(5)(1，3，3，3)。解由于非负整数列d＝(d1，d2，…，dn)是可图化的当且仅当≡0(mod2)，所以(1)、(2)、(3)、(5)能构成无向图的度数列。(1)、(2)、(3)是可简单图化的。其对应的无向简单图如图所示。)(5)是不可简单图化的。若不然，存在无向图G以为1，3，3，3度数列，不妨设G中结点为、、、，且d()＝1，d()＝d()＝d()＝3。而只能与、、之一相邻，设与相邻，于是d()＝d()＝3不成立，矛盾。4.试证明图10-48中的两个无向图是不同构的。%证明因为两图中都有4个3度结点，左图中每个3度结点均与2个2度结点邻接，而右图中每个3度结点均只与1个2度结点邻接，所以这两个无向图是不同构的。5.在图同构意义下，试画出具有三个结点的所有简单有向图。解具有三个结点的所有非同构的简单有向图共16个，如图所示，其中(8)(16)为其生成子图。6.给定无向完全图G＝<V，E>，且|V|＝4。在图同构意义下，试求：(1)G的所有子图。(2)G的所有生成子图。解(1)G的所有子图如图所示。(2)图(8)(18)是G的所有生成子图。—7.(1)试给出一个五个结点的自补图。【(2)是否有三个结点或六个结点的自补图。(3)一个图是自补图，则其对应的完全图的边数必是偶数。(4)一个自补图的结点数必是4k或4k＋1。解(1)五个结点的图G与它的补图如图所示。对G与建立双射：，，，，。显然这两个图保持相应点边之间的对应的关联关系，故G。因此，G是五个结点的自补图。(3)设图G是自补图，有m条边，G对应的完全图的边数为s，则G对应的补图的边数为s－m。因为G，故边数相等，即有m＝s－m，s＝2m，因此G对应的完全图的边数s为偶数。](2)由(3)知，自补图对应的完全图的边数为偶数。n个结点的完全图6时，的边数为奇数，因此不存在三个结点或六个结点的自补图。的边数为n(n－1)，当n＝3或n＝(4)设G为n阶自补图，则需n(n－1)能被2整除，因此n必为4k或4k＋1形式。8.一个n(n≥2)阶无向简单图G中，n为奇数，已知G中有r个奇数度结点，问G的补图中有几个奇数度结点解由G的补图的定义可知，G∪为，由于n为奇数，所以中各顶点的度数n－1为偶数。对于图＝n－1，由于n－1为偶数，所G的任意结点，应有也是的顶点，且＋＝以和奇偶性相同，因此若G中有r个奇数度结点，则中也有r个奇数度结点。9.画出4阶无向完全图K4的所有非同构的生成子图，并指出自补图来。解下图中的11个图是K4的全部的非同构的生成子图，其中(7)为自补图。;10.设图G中有9个结点，每个结点的度不是5就是6。试证明G中至少有5个6度结点或至少有6个5度结点。证明由握手定理的推论可知，G中5度结点数只能是0、2、4、6、8五种情况（此时6度结点数分别为9、7、5、3、1）。以上五种情况都满足至少5个6度结点或至少6个5度结点的情况。11.证明3度正则图必有偶数个结点。证明设G为任一3度正则图，有n个结点、、…、，则所有结点度数之和＝3n。若n为奇数，则3n也为奇数，与握手定理矛盾。故n为偶数。12.设G为至少有两个结点的简单图，证明：G中至少有两个结点度数相同。证明若G中孤立结点的个数大于2，结论显然成立。若G中有1个孤立结点，则G中至少有3个结点，因而不考虑孤立结点，就是说G中每个结点的度数都大于等于1。又因为G为简单图，所以每个结点的度数都小于等于n-1。因而G中结点的度的取值只能是1，2，…，n-1这n个数。由抽屉原理可知，取n-1个值的n个结点的度至少有两个是相同的。—13.给定无向图G＝<V，E>如图10-49所示，试求：(1)从a到d的所有基本路。(2)从a到d的所有简单路。(3)长度分别是最小和最大的基本回路。(4)长度分别是最小和最大的简单回路。(5)从a到d的距离。(6)(G)、(G)、(G)、(G)分别是多少解(1)从a到d的所有基本路共有10条：abd，abcd，abed，abced，abecd，afed，afecd，afebd，afebcd，afecbd。(2)从a到d的所有简单路共有14条：除（1）中的10条外还有abcebd，abecbd，afebced，afecbed。(