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

7.6第186页

1.图7-34是不是二部图？如果是，找出其互补结点子集。 解：是，互补结点子集是：{v1,v3,v5},{v2,v4,v6,v7}。 2.如何由无向图G的邻接矩阵判断G是不是二部图？

解：设G的邻接矩阵为A，V?n，计算A(2)，A(3)，…A(n)。其中如果矩阵的对角线出现了基数，则G不是二部图。如果所有的矩阵（包括矩阵A）的回路长度都是偶数，则是二部图。

3.举出一个二部图的例子，它不满足定理7.6.3的条件，但是存在完美匹配。

解：如第一题的例子，二部图为：

2 4 6 7 1 3 5 该图中不满足定理7.6.3的条件（对于V1，在V2中至少有2个结点与其相邻，但是在V2中，各结点最多有有2个结点与V1中结点相邻），但是该图是完美匹配，因为匹配数为3（=V1）（如v1v2，v3v4 ，v5v7） 4.证明：n阶简单二部图的边数不能超过[n2/4]。

证明：对于简单二部图，当为完全二部图时边数最多，边数为V1?V2，又V1?V2?n，当V1?V2即V1?V2?n/2时，V1?V2有最大值n2/4，故边数取整，故边数不能超过[n2/4]。得证。 5.

解：可能，如下图：

P1P5P6P2P3P4

6. 解：

张明王同李林赵丽数学物理电工计算机科学

7. 图7-35是否存在{v1,v2,v3,v4}到{u1,u2,u3,u4,u5}的完美匹配？如果存在，指出它的一个完美匹配。 解：存在。如：v1u2，v2u1，v3u4，v4u5。

7.7第192页

1.对于下列情况，验证欧拉公式n-m+k=2 (1)图7-45中的多边形的图。

解：对a)点数7，面的个数3，边的个数8，7+3-8=2，成立。 对b)顶点个数8，面的个数3，边的个数9，8+3-9=2，成立。 (2)一个具有(r?1)2个结点的无向边，它描述了r2个正方形的网络，例如棋盘等。

解：顶点个数为(r?1)2，面的个数为r2?1，边的个数为r2，

(r?1)2+r2?1-2r(r?1)=2，成立。

2.试证明：图7-42b中的库拉图斯基图是个非平面图。 证明：

12534 对于基本环路：v1v2v3v4v5v1,考虑v2v5和v3v5在环的内侧，直线v1v4必定在外侧。对于直线v1v3和v2v4必定相交。故该图是非平面图。 3. 画图所有不同构的6阶非平面图。

解：根据分析图至少有9条边，最多为15条边。所有情况如下图：

9910111112131415

4.试用库拉斯基定理证明：图7-48中的图是个非平面图。 证明：图7-48中村子一个子图与阶数为6的库拉斯基图同构。将图7-48变形得到：

1236457

其中的由{v1,v2,v3,v4,v5,v6}构成的子图与阶数为6的库拉斯基图同构。故该图是非平面图。

5. 图7-49给出一个多边形的图，试构成该图的对偶。