第10章习题答案
第10章图
习题10
1.(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＝?v?Vd(v)＝2＋2＋3＋3＋4＝14，所以G的边数7条。
(2)于这两个序列中有奇数个是奇数，握手定理的推论知，它们都不能成为图的度数列。 (3) 握手定理得?v?Vd(v)＝2m＝24，度数为3的结点有6个占去18度，还有6度其它结点占有，
其余结点的度数可为0、1、2，当均为2时所用结点数最少，所以应3个结点占有这6度，即图G中至多有9个结点。
2.若有n个人，每个人恰有3个朋友，则n必为偶数。
证明设v1、v2、?、vn表示任给的n个人，以v1、v2、?、vn为结点，当且仅当两人为朋友时其对
n应的结点之间连一条边，这样得到一个简单图G。握手定理知?k?1d(vk)＝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)是可图化的当且仅当?di≡0(mod 2)，所以(1)、(2)、
i?1n(3)、(5)能构成无向图的度数列。
(1)、(2)、(3)是可简单图化的。其对应的无向简单图如图所示。
(5)是不可简单图化的。若不然，存在无向图G以为1，3，3，3度数列，不妨设G中结点为v1、v2、
v3、v4，且d(v1)＝1，d(v2)＝d(v3)＝d(v4)＝3。而v1只能与v2、v3、v4之一相邻，设v1与v2相邻，于是d(v3)＝d(v4)＝3不成立，矛盾。
1
第10章图
4.试证明图10-48中的两个无向图是不同构的。
证明因为两图中都有4个3度结点，左图中每个3度结点均与2个2度结点邻接，而右图中每个3度结点均只与1个2度结点邻接，所以这两个无向图是不同构的。
5.在图同构意义下，试画出具有三个结点的所有简单有向图。
解具有三个结点的所有非同构的简单有向图共16个，如图所示，其中(8)?(16)为其生成子图。
(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15) (16)6.给定无向完全图G＝，且|V|＝4。在图同构意义下，试求： (1)G的所有子图。 (2)G的所有生成子图。
解 (1)G的所有子图如图所示。 (2)图(8)?(18)是G的所有生成子图。
(7)(8)(9)(10)(11)(12)(1)(2)(3)(4)(5)(6)
7.(1)试给出一个五个结点的自补图。
(13)(14)(15)(16)(17)(18) 2
第10章图
(2)是否有三个结点或六个结点的自补图。
(3)一个图是自补图，则其对应的完全图的边数必是偶数。 (4)一个自补图的结点数必是4k或4k＋1。
解 (1)五个结点的图G与它的补图G如图所示。对G 与G建立双射：v1?v1，v2?v2，v3?v3，v4?v4，
v5?v5。显然这两个图保持相应点边之间的对应的关联关系，故G?G。因此，G是五个结点的自补图。
(3)设图G是自补图，有m条
G。以上五种情况都满足至少5个6度结点或至少6个5度结点的情况。
11.证明3度正则图必有偶数个结点。
n证明设G为任一3度正则图，有n个结点v1、v2、?、vn，则所有结点度数之和?d(vi)＝3n。若n
i?1为奇数，则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＝如图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条：除中的10条外还有abcebd，abecbd，afebced，afecbed。 (3)长度最小的基本回路共4个：bceb，bdeb，cdec，bcdb。长度最大的基本回路共1个：abdcefa。 (4)长度最小的简单回路共4个：bceb，bdeb，cdec，bcdb。长度最大的简单回路2个：abcebdefa，afebcedba。 (5)从a到d的距离为2。
(6)?(G)＝2，?(G)＝2，?(G)＝2，?(G)＝4。 14.给定有向图G＝如图10-50所示，试求： (1)各结点的出度、入度和度。 (2)从a到d的所有基本路和简单路。 (3)所有基本回路和简单回路。
解 (1)d(a)＝2，d(a)＝1，d(b)＝1，d(b)＝2，d(c)＝1，d(c)＝1，d(d)＝2，d(d)＝2，d(e)＝1，d(e)＝1。
(2)从a到d的基本路2条：ad，abd。从a到d的简单路5条：ad，abd，adcbd，adead，adeabd。 (3)基本回路共3个abdea，adea，bdcb.简单回路共4个：abdea，adea，bdcb，adcbdea。
4
-+
-+
-+
-+
