国开离散数学形考答案

选择题

　　1. 已知集合A = {1, 2, 3}，集合B = {2, 3, 4}，那么A ∩ B的结果是：

　　A. {1}

　　B. {2, 3}

　　C. {1, 2, 3, 4}

　　D. {}

　　正确答案：B

　　解析：集合A和集合B的交集包含两个集合的公共元素，即{2, 3}。

　　2. 如果图G的顶点数为5，边数为6，那么此图的补图的边数是多少？

　　A. 4

　　B. 5

　　C. 7

　　D. 9

　　正确答案：D

　　解析：完全图K5有10条边，补图的边数为10 - 6 = 4。

填空题

　　1. 在一个非空集合A上定义的关系R，如果对任意a, b, c ∈ A，aRb且bRc则aRc成立，那么关系R称为_________。

　　正确答案：传递性

　　解析：根据传递性的定义，若aRb且bRc，则必然有aRc。

　　2. 若简单图G的顶点数为n，且G是一个连通图，则最少有_________条边。

　　正确答案：n-1

　　解析：一个连通图在保持连通的前提下，最少需要n-1条边。

判断题

　　1. 对于任意两个集合A和B，A ∪ B = A ∩ B成立。

　　正确答案：错误

　　解析：A ∪ B表示A和B的并集，而A ∩ B表示A和B的交集，这两个操作不同，因此不可能相等。

　　2. 一个图的所有顶点的度数之和一定是偶数。

　　正确答案：正确

　　解析：因为每条边连接两个顶点，所以度数和等于边数的两倍，必然是偶数。

论述题

　　1. 论述如何使用哈密顿路径来解决旅行商问题（TSP）。

　　回答：哈密顿路径是通过图中的每个顶点一次且仅一次的一条路径，解决旅行商问题（TSP）需要找到这样一条哈密顿路径，使得总路径长度最短。虽然哈密顿路径和旅行商问题在概念上不同，但可以通过构造适当的权重图将TSP转化为寻找最短哈密顿路径的问题。然而，TSP是NP难题，没有已知的多项式时间算法能解决此问题，因此通常采用近似算法或启发式算法来求解。在实际应用中，常用的方法包括动态规划、分支定界法和遗传算法等。