离散数学第五版习题答案.pdfVIP

离散数学第五版习题答案--第1页

离散数学第五版习题答案

【篇一：自考2324离散数学第五章课后答案】

txt5.1习题参考答案

1、设无向图g有16条边，有3个4度结点，4个3度结点，其余

结点的度数均小于3，问：g中至少有几个结点。

阮允准同学提供答案:

解：设度数小于3的结点有x个，则有

解得：x≥4

所以度数小于3的结点至少有4个

所以g至少有11个结点

2、设无向图g有9个结点，每个结点的度数不是5就是6，证明：

g中至少有5个6度结点或至少有6个5度结点。

阮允准同学答案：

证明：由题意可知：度数为5的结点数只能是0,2，4,6，8。

若度数为5的结点数为0,2，4个，则度数为6的结点数为9，7,5

个结论成立。

若度数为5的结点数为6,8个，结论显然成立。

由上可知，g中至少有5个6度点或至少有6个5度点。

3、证明：简单图的最大度小于结点数。

阮同学认为题中应指定是无向简单图.

晓津证明如下：设简单图有n个结点，某结点的度为最大度，因为

简单图任一结点没有平行边，而任一结点的的边必连有另一结点，

则其最多有n-1条边与其他结点相连，因此其度数最多只有n-1条，

小于结点数n.

4、设图g有n个结点，n+1条边，证明：g中至少有一个结点度数

≥3。阮同学给出证明如下：

证明：设g中所有结点的度数都小于3，即每个结点度数都小于等

于2，则所有结点度数之和小于等于2n，所以g的边数必小于等于

n，这和已知g有n+1条边相矛盾。所以结论成立。

5、试证明下图中两个图不同构。

晓津证明：同构的充要条件是两图的结点和边分别存在一一对应且

保持关联关系。我们可以看出，(a)图和(b)图中都有一个三度结点，

(a)图中三度结点的某条边关联着两个一度结点和一个二度结点，而

离散数学第五版习题答案--第1页

离散数学第五版习题答案--第2页

(b)图中三度结点关联着两个二度结点和一个一度结点，因此可断定

二图不是同构的。

6、画出所有5个结点3条边，以及5个结点7条边的简单图。

解：如下图所示：(晓津与阮同学答案一致)

7、证明：下图中的图是同构的。

证明如下：

在两图中我们可以看到有

a→e,b→h,c→f,d→g

两图中存在结点与边的一一对应关系，并保持关联关系。

8、证明：下面两图是同构的。

阮同学给出证明如下：

证明：找出对应关系：aq,br,cs,dt,eu,fv,

gw,hx

9、证明：三次正则图必有偶数个结点。

阮同学证明如下：

由题意可知每个结点度数都是3度，即每个结点均为奇结点，根据

有偶数个奇结点可知，三次正则图必有偶数个奇结点。

5.2习题参考答案

1、给定图g，如下图所示，求出g中从a到f的所有初级路。

解：从a到f的初级路有：

abcf、abef、adef、abecf、abcef、adecf、adebcf

2、给定图g，如下图所示，找到g中从v2出发的所有初级回路。

晓津认为图中少了一个箭头：从v1到v2有一箭头。

从v2出发的初级回路有：v2v4v1v2、v2v3v4v1v2.

3、设g为无向连通图，有n个结点，那么g