离散数学第10章习题答案

第10章 图

第10章习题答案

1.解 (1)设G有m条边，由握手定理得2m＝?d(v)＝2＋2＋3＋3＋4＝14，所以G的边数7条。

v?V(2)由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为图的度数列。 (3) 由握手定理得?d(v)＝2m＝24，度数为3的结点有6个占去18度，还有6度由其它结点占有，

v?V其余结点的度数可为0、1、2，当均为2时所用结点数最少，所以应由3个结点占有这6度，即图G中至多有9个结点。

2.证明 设v1、v2、?、vn表示任给的n个人，以v1、v2、?、vn为结点，当且仅当两人为朋友时其对应的结点之间连一条边，这样得到一个简单图G。由握手定理知

?d(v)＝3n必为偶数，从而n必为偶数。

kk?1n3. 解 由于非负整数列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不成立，矛盾。

4.证明 因为两图中都有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. 解 (1)G的所有子图如图所示。

1

第10章 图

(2)图(8)?(18)是G的所有生成子图。

7. 解 (1)五个结点的图G与它的补图G如图所示。对G与G建立双射：v1?v1，v2?v2，v3?v3，

v4?v4，v5?v5。显然这两个图保持相应点边之间的对应的关联关系，故G?G。因此，G是五个结点的

(13)(14)(15)(16)(17)(18)(7)(8)(9)(10)(11)(12)(1)(2)(3)(4)(5)(6)自补图。

（1）G（2)G(3)设图G是自补图，有m条边，G对应的完全图的边数为s，则G对应的补图G的边数为s－m。因为G?G，故边数相等，即有m＝s－m，s＝2m，因此G对应的完全图的边数s为偶数。

(2)由(3)知，自补图对应的完全图的边数为偶数。n个结点的完全图Kn的边数为n(n－1)，当n＝3或n＝6时，Kn的边数为奇数，因此不存在三个结点或六个结点的自补图。

(4)设G为n阶自补图，则需n(n－1)能被2整除，因此n必为4k或4k＋1形式。

8.解 由G的补图G的定义可知，G∪G为Kn，由于n为奇数，所以Kn中各顶点的度数n－1为偶数。对于图G的任意结点v，应有v也是G的顶点，且dG(v)＋dG(v)＝dKn(v)＝n－1，由于n－1为偶数，所以dG(v)和dG(v)奇偶性相同，因此若G中有r个奇数度结点，则G中也有r个奇数度结点。

9.画出4阶无向完全图K4的所有非同构的生成子图，并指出自补图来。

1212 2

第10章 图

解 下图中的11个图是K4的全部的非同构的生成子图，其中(7)为自补图。 10.

证明 由握手

定理的推论可知，G中5度结点数只能是0、2、4、6、8五种情况（此时6度结点数分别为9、7、5、3、1）。以上五种情况都满足至少5个6度结点或至少6个5度结点的情况。

11.证明 设G为任一3度正则图，有n个结点v1、v2、?、vn，则所有结点度数之和若n为奇数，则3n也为奇数，与握手定理矛盾。故n为偶数。

12.证明 若G中孤立结点的个数大于2，结论显然成立。若G中有1个孤立结点，则G中至少有3个结点，因而不考虑孤立结点，就是说G中每个结点的度数都大于等于1。又因为G为简单图，所以每个结点的度数都小于等于n-1。因而G中结点的度的取值只能是1，2，?，n-1这n个数。由抽屉原理可知，取n-1个值的n个结点的度至少有两个是相同的。

13. 解 (1)从a到d的所有基本路共有10条：abd，abcd，abed，abced，abecd，afed，afecd，afebd，afebcd，afecbd。

(2)从a到d的所有简单路共有14条：除（1）中的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. 解 (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。 15. 证明 (1)设无向图G中只有两个奇数度结点u和v。从u开始构造一条回路，即从u出发经关联结点u的边e1到达结点u1，若d(u1)为偶数，则必可由u1再经关联u1的边e2到达结点u2，如此继续下去，每条边只取一次，直到另一个奇数度结点为止，由于图G中只有两个奇数度结点，故该结点或是u或是v。

3

+

-+

-+

-+

-+

-

?d(v)＝3n。

ii?1n第10章 图

如果是v，那么从u到v的一条路就构造好了。如果仍是u，该回路上每个结点都关联偶数条边，而d(u)是奇数，所以至少还有一条边关联结点u的边不在该回路上。继续从u出发，沿着该边到达另一个结点u1?，依次下去直到另一个奇数度结点停下。这样经过有限次后必可到达结点v，这就是一条从u到v的路。

(2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达不一定成立。下面有向图中，只有两个奇数度结点u和v，u和v之间都不可达。

16.证明 设无向图G是不连通的，其k个连通分支为G1、G2、?、Gk。任取结点u、v∈G，若u和

v不在图G的同一个连通分支中，则[u，v]不是图G的边，因而[u，v]是图G的边；若u和v在图G

uwv的同一个连通分支中，不妨设其在连通分支Gi（1≤i≤k）中，在不同于Gi的另一连通分支上取一结点w，则[u，w]和[w，v]都不是图G的边，，因而[u，w]和[w，v]都是G的边。综上可知，不管那种情况，u和v都是可达的。由u和v的任意性可知，G是连通的。

17. 证明 充分性：若连通图G中存在结点u和w，使得连接u和w的每条路都经过e，则在子图G－{e}中u和w必不可达，故e是G的割边。

必要性：若e是G的割边，则G－{e}至少有两个连通分支G1＝和G2＝。任取u∈V1，w∈V2，因为G连通，故在G中必有连接u和w的路?，但u、w在G－{e}中不可达，因此?必通过

e，即u和w之间的任意路必经过e。

18.证明 先证任一结点至少位于一个单向分图中。

任给一结点v，若v是孤立结点，则含v的平凡图即为单向分图。若v不是孤立结点，则必有一个结点u，使得u与v有一弧e与它们联结。此时若有单向分图G1??V1,E1?，|V1|≥3，使u，v∈V1，且e∈E1，那么结论成立；若不存在这样的G1，则由u，v和e就构成一个单向分图。因此，任何结点至少位于一个单向分图中。

其次证明，任何一条弧至少位于一个单向分图中。

任给一弧e，其关联的结点u和v。若存在一单向分图G1??V1,E1?，|V1|≥3，使u，v∈V1，且e∈E1，那么结论成立。否则，u，v和e就构成一个单向分图。综上可知，任一弧至少位于一个单向分图中。

19.证明 显然任一结点和任一弧都位于一个弱分图中。

假设有一结点v位于两个不同的弱分图G1??V1,E1?和G2??V2,E2?中，即v∈V1∩V2。由于略去弧的方向后，V1中所有结点与v可达，V2中所有结点也与v可达，故V1与V2中所有结点可达，这与

G1和G2为弱分图矛盾，故任一结点不可能包含于不同的弱分图中，即任一结点能且只能位于一个弱分图

中。

假设一弧e位于两个不同的弱分图中，该弧e所关联的两个结点也位于两个不同的弱分图中，这是不

4

第10章 图

可能的，因此任一弧也只能位于一个弱分图中。

20. 解

（a） （b） （c）图中得（a）为强连通图；（b）为单向连通图但不是强连通图；（c）是弱连通图但不是单向连通图，当然更不是强连通图。

21.证明 充分性。

给定有向图D＝，如果D有一条经过每一个结点的路为v1e1v2e2?vn?1en?1vn，这时V＝{v1，

v2，?，vn?1，vn}，E＝{e1，e2，?，en?1}?E，边ei（1≤i≤n－1）以vi为起点，以vi?1为终点。任给

两个结点vl、vm∈V，不妨设l＜m，则vlelvl?1?em?1vm就是从结点vl到vm的路，故D是单向连通的。

必要性。

对结点数v进行归纳。

当v＝1或2时，单向连通图显然有一条经过每一个结点的路。

设v＝k时，有一条经过每一个结点的路v1v2?vp，其中结点可能有重复，这条路的下标只表示该路所经过结点的次序，显然k≤p。

当v＝k＋1时，取一结点u，在图中删去结点u，使D－{u}还是单向连通图。根据归纳假设，D－{u}有一条经过每一个结点的路v1v2?vp。令i＝max{s|vs到u有路}，j＝min{s|u到vs有路}。假如j＞

i＋1，则必有t满足i＜t＜j。由于图D是单向连通的，vt与u之间必有路。如果该路是从vt到u，则与i＝max{s|vs到u有路}矛盾。如果该路是从u到vt，则与j＝min{s|u到vs有路}矛盾。故而j＞i＋1不可能，只能是j≤i＋1。当j＝i＋1时，有经过每个结点的路v1v2?vi?u?vi?1vi?2?vp。当j≤i时，有经过每个结点的路v1v2?vj?vi?u?vj?vivi?1?vp。

22.证明 设e为图G的第个连通分支Gi的一条边。

若e不是Gi的割边，则Gi－e仍然连通，因而G的连通分支数不变，即

?(G)＝?(G－e) （1）

若e是Gi的割边，则Gi－e有且仅有两个连通分支，因而G－e比G多一个支连通分支，即

?(G)＋1＝?(G－e) （2）

由（1）和（2）可得?(G)≤?(G－e)≤?(G)＋1。

23.证明 （1）首先证明n－p≤m。对边数m做归纳法。m＝0时，G为零图，p＝n，n－p＝0，此时结论显然成立。

设m＜k（k≥1）时结论成立，要证m≥3时结论成立。在G中找一个边割集，不妨设这个边割集中

5

本文来源：https://www.bwwdw.com/article/uiaf.html