2009-集合论与图论-期末试题及答案1

这篇资料是关于2009年哈尔滨工业大学秋季学期的“集合论与图论”课程的期末试题及答案。试题涵盖了集合论和图论的基础概念，包括集合的基本操作、关系的性质、图的理论等多个方面。 1. 题目中提到集合BA与BBAB的关系，若BBABBA\)()\(=，这意味着B与自身相交并且与A的关系是对称的。因此，B等于B与A的并集减去A本身，即B=B∪A-A，简化后得出B=∅。 2. 对于映射XAYXf→ ,:，其逆映射))((1Aff −表示将A中的元素通过f映射后得到的集合。如果))((1Aff −与 A有包含关系，那么1Aff 是A的真子集，即A中所有元素都能通过f映射到A的不同元素上，但不能有元素映射到自己。 3. 在集合S={1, 2, 3, 4, 5}上找一个等价关系R，能产生特定划分。等价关系R必须满足自反性、对称性和传递性。题目给出的划分表明R应该包含{(1, 2), (2, 1), (2, 2), (1, 1), (3, 3), (4, 4), (5, 5), (4, 5), (5, 4), (5, 5)}，这些对构成了R。 4. 定义了三个映射，分别在实数集、整数集和自然数集上。对于这些映射，要判断它们是否是单射、满射或双射。映射1是1到R的映射，显然是单射；映射2是整数到自身的映射，可以覆盖所有整数，所以是满射；映射3是整数到实数的双射，因为它把每个整数映射到一个唯一的实数对。 5. 在集合A={1, 2, ..., 11}上的整除关系是偏序关系，其极大元是1的因子，即集合{1, 2, 3, 5, 6, 11}。 6. 集合X上有n个元素，对称的二元关系是指关系R和它的逆R^-1是相同的。这样的关系有2^n - n种，因为每个元素都可以与自身关联，除了自身以外还可以与其他n-1个元素关联，共有2^n种可能，但减去不包含对称关系的情况，即不关联自身的情况n。 7. 关系R是传递的当且仅当对任何元素a, b, c在X中，如果(a, b)和(b, c)都在R中，那么(a, c)也在R中。对称的条件是R的逆关系R^-1与R相同。 8. K-正则偶图意味着每个顶点的度数都是偶数。如果有p个顶点，最小的p使得存在这样的图是2p，因为至少需要两个顶点相连以满足每个顶点的度数是偶数。 9. 每个药箱含有n种药的其中一种，总共n个药箱，意味着有n种药。每种药在两个药箱中，所以每个药箱有1-n种药，n个药箱共有2/(1-n)种药。 10. 无向图G有12条边，6个3度顶点，其余顶点度数小于3。要使边数最少，其余顶点应尽可能多为2度，所以至少有9个顶点。 11. 无向树T的最大度数范围是1≤Δ(T)≤p-1，如果Δ(T)=2，则最长路径的长度为p-1，因为树中路径的长度不可能超过顶点数减1。 12. 极大平面图是指可以平展在平面上的图，没有交叉边。有8个顶点的极大平面图的面数f是12，这是平面图欧拉公式V-E+F=2的应用。 13. 如果图G是(p, q)图且p<q-1，那么G的顶点连通度k(G)为0，因为没有足够的边来连接所有顶点。 14. 正则二元树中，边数q和树叶数t的关系是q=2(t-1)，所以如果t是树叶数，q=2(t-1)。 15. 当p和q都是偶数时，K_{p,q}是欧拉图，因为欧拉图要求所有顶点的度数都是偶数。 在简答题部分，涉及集合的交并差运算、反自反和传递关系的性质，以及构造满足特定条件的映射。这些题目进一步巩固了集合论和图论的基本概念。