离散数学及其应用--第2版第10章部分习题解答.docx

习题

设无向图G=（V，E），V={v1，v2，v3，v4，v5}，E={（v1，v2），（v2，v2），（v2，v4），（v4，v5），（v3，v4），（v1，v3），（v3，v1）}。

画出G的图形；

求出G中各结点的度及奇数度结点的个数。

解答：a)

b)d(v1)=3，d(v2)=4，d(v3)=3，d(v4)=3，d(v5)=1

下列序列中，哪些是可构成无向简单图的结点度数序列？

1）（1，1，2，2，3）2）（1，1，2，2，2）

3）（0，1，3，3，3）4）（1，3，4，4，5）

5）（0，1，1，2，3，3）

解答：1)N2)Y3)N4)N5)Y(当删去一个3度结点的度数序列为(0,0,1,1,2,0)时)，N（当删去一个3度结点的度数序列为(0,0,0,1,3,0)时)

设无向图G有16条边，3个4度结点，4个3度结点，其余结点的度数均小于3，问：G中至少有几个结点。

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

3×4＋4×3＋2x≥2×16

解得：x≥4

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

所以G至少有11个结点

证明：若有n个人，每个人恰恰有三个朋友，则n必为偶数。

证明：n个人对应n个结点，每个人恰恰有三个朋友，即为每个结点有3度，根据握手定理的推论，n必为偶数。

设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3。

证明：用反证法.若G的最大度?(G)??2,则按握手定理2m??2n,其中m是边数.从而m??n,而这与题设矛盾.

证明：无向简单图G=(V,E),e=|E|,v=|V|则有e?v(v-1)/2.

证明：无向简单图是完全图时边数最多，完全图的边数为v(v-1)/2，所以无向简单图有e?v(v-1)/2.

设图G=(V,E),e=|E|,v=|V|,d(v)min为G中结点的最小度数,d(v)max为G中结点的最大度数.证明:d(v)min?2e/v?d(v)max.

证明：根据握手定理：

将式（1）代入式（2），整理得：d(v)min?2e/v?d(v)max.

有n个抽屉，若每两个抽屉里有一种相同的物品，每种物品恰好放在两个抽屉中，问共有多少种物品？

解：每个抽屉用一个结点表示；每两个抽屉放相同的物品，在每两个抽屉对应的结点间连接一条边，则构成一个n个结点的完全图，每条边是一个物品。n个结点的完全图有n(n-1)/2条边，所以共有n(n-1)/2种物品。

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

证明：由定义可知，无向简单图是无环无多重边的图，因此n个节点的无向简单图，每个结点最多和其它结点都有边相连接时有n-1条边。因此，简单图的最大度为n-1，小于结点个数n。

下列各图有多少个结点和多少条边？

1）Kn2）Cn3）Wn4）Km，n5）Qn

解：1）n个结点，n(n-1)/2条边

2）n个结点，n条边

3)n+1个结点，2n条边

4)m+n个结点，mn条边

5）2n个结点，n*2n-1条边

当n为何值时，下列各图是正则图？

1）Kn2）Cn3）Wn4）Qn

解：(1)对所有n?1

(2)对所有n=3

(3)4

(4)对所有n?1

证明：3正则图必有偶数个结点。

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

(b)

证明：同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系。我们可以看出，(a)图和(b)图中都有一个三度结点，(a)图中三度结点的某条边关联着两个一度结点和一个二度结点，而(b)图中三度结点关联着两个二度结点和一个一度结点，因此可断定二图不是同构的。

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

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

证明：简单图的同构关系是等价关系。

提示：简单图的同构关系是自反、对称和传递的。

连通图G有n个结点，e条边，则e?n-1。

证明：用归纳法证明。

当n=2时，连通图G至少有一条边，e?1，所以e?n-1成立。

设n￡k时，结论成立，即e?k-1。

当n=k+1时，

=1\*GB3①若删去一个度数为d(v)的结点得到图G’，而且图G’仍是连通的，图G’的结点数和边数分别为k和e’，则e’?k-1，e’=e-d(v)，所以e-d(v)?k-1，则e?k-1+d(v),因为G是连通图，d(v)?1,因而e?k,所以e?n-1.

=2\*GB3②若删去一个度数为d(v)的结点得到图G’，而且图G’不连通的，假设图G’有两个连通分支G1’、