离散数学 第七章检测题及答案(4)

解：为保证每个城市石油的正常供应最少需5连士兵看守.

求看守的最短管道相当于求图的最小生成树问题，此图的最小生成树为：

因此看守的最短管道的长度为： Ｗ（Ｔ）＝１＋1＋2＋2＋2＝８． 4．以给定权1, 4, 9, 16, 25, 36, 49, 64, 81, 100构造一棵最优二叉树。

5．一次学术会议的理事会共有20个人参加，他们之间有的相互认识，但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20，说明能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人？根据是什么？

解：可以把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人。（1分） 根据是：分别用20个结点代表这20个人，将相互认识的人之间连一条线，便得到一个 无向简单

图G V,E，每个结点vi V的度数是与vi认识的人的数目，由题意知

vi,vj V，有degv(i )

devg( )，2于

是G V,中存在哈密尔顿回路，设j

C vi1vi2

vi20vG V,E中的一条哈密尔顿回路，按此回路安排园桌座位即符合要是i

求。（4分）

四．证明与应用题（10分）

1． 某次聚会的成员到会后相互握手，试用图论的知识说明与奇数个人握手的人数一定是一

个偶数。

证: 用结点代表成员, 握手的成员之间连一条线, 则所有聚会的成员之间的握手

情况可以用一个图来表示，其中每个结点的度数就是该结点所代表的成员握