离散数学第二版答案（6-7章）

解：对于图b）中的点d?，其出度为：dG?(d?)?3，入度：dG?(d?)?0。而在a)图中不存在这样的结点。因此这两个图不同构。

10．证明：任何阶大于1的简单无向图必有两个结点的度数相等。

证明：考虑一个有n个结点的连通图（如果有一个孤立结点，去掉孤立结点考虑联通子图）。因为是无向连通图，每个结点的最大度数是n-1，最小度数是1。即对n个点赋值，共n-1种取值，由抽屉原理，必有两个结点的取值相同，即必有两个点的度数相同。

11．设n阶无向图G有m条边，其中nk个结点的度数为k，其余结点的度数为k+1，证明：

??nk?(k?1)n?2m。

证明：由题意，结点数为n，由总边数建立关系：

m?

nk?k?(n?nk)(k?1)，由此可得：nk?(k?1)n?2m。

27.2第168页

1．画出K4的所有不同的子图，并说明其中哪些是生成子图，找出互为补图的生成子图。 解：

(1)(2)(3)

（4）

(5)(6)(7)

其中，（1）和（7），（2）和（6），（3）和（5），（4）中的后两个图可以构成互补的生产子图。

2．设G??V,E,??是完全有向图。证明：对于V的任意非空子集V?，

G[V?]是完全有向图。

证明：（1）当V?中只有一个结点时，G[V?]是完全有向图。

（2）当V?中有多于一个结点时，对其中任意两个结点Vi,Vj是V的子集，即Vi,Vj?V。因为图G是完全有向图，因此Vi,Vj间存在两条有向边eij和eji。G[V?]是由非空子集V?生成的子图，故eij,eji?G[V?]，即

G[V?]中任意两个结点间存在两条有向边，故G[V?]是完全有向图。

3．画出图7-15的两个图的交、并和环和。

v1e1v2e2v3e3e6e4e7v4e5v5v2v3e6e8e1e3v1v4a)b)

解：

交： 并：

v1v1e3e6e1v2e2e3e6e4e5v5e7v4e1v2v3v4

v3

环和：

v1e5v2e2v3e8v4e4e7v5

4．设G是任意6阶简单无向图，证明：G或G必有一个子图是3阶无向图。

证明：取G或G任意取三个点，取与这三个点相关联的变构成一个3阶的无向子图。

5．我们称与补图同构的简单无向图为自补图。证明：每个自补图的阶能够被4整除或被4整除余数为1。

n(n?1),由自补图的定义知该2n(n?1)图与其子图的边数相同（同构），故其边数为，由该数是整数

4n(n?1)得：?k，n?4korn?4k?1。故每个自补图的阶能够被4整除或

4证明：设图的顶点数为n，Kn的边数为

被4整除余数为1。

7.3第173页

1．考虑图7-21

（1）从A至F的路径有多少条？找出所有长度小于6的从A至F的路径。

解：A到F的路径有无数条。长度小于6的有24条。（c f h:4,c g h:4, c e i:4, b d e f h:2, b d e g h:2, b d i:4）

（2）找出从A至F的所有简单路径。

解：12条。(c f h, c g h, c e I, b d e f h, b d e g h, b d i),还有一个自环，需乘以2.

（3）找出从A至F的所有基本路径。

解：6条。(c f h, c g h, c e I, b d e f h, b d e g h, b d i) （4）求出从A至F的距离。求出该图的直径。 解：距离为3。直径为3。 （5）找出该图的所有回路。

解：AaA, AbDdEeBcA, BeEiFhCgB; BgCfB; AbDdEiFhCgBcA; BeEiFhCfB;

2．证明：图7-21中基本路径必为简单路径。

证明：基本路径要求途经的顶点不重复，简单路径要求途经的边不重复。在图7-21中，对于所有的基本路径，边不重复出现。所以基本路径必是简单路径。 3．考虑图7-22

（1）对于每个结点v，求R(v)。

解：R(v1)?R(v2)?R(v3)?R(v4)?{v1,v2,v3,v4,v5,v6}, R(v5)?{v5,v6},R(v6)?{v6},R(v7)?{v6,v7} R(v8)?{v6,v7,v8},R(v9)?{v9},R(v10)?{v10} （2）找出所有强分支、单向分支和弱分支。

解：强分支7个，分别是{v9},{v10},{v8},{v7},{v6},{v5},{v1,v2,v3,v4} 单项分支4个，分别是{v9},{v10},{v6,v7,v8},{v1,v2,v3,v4,v5,v6}