信息科学技术学院2002-2003学年第二学期 本科生期末考试试卷 考试科目:集合论与图论 考试时间:2003年6月 专业 级班 姓名 学号 装 四五六七八九|十|总分 得 (注意:从下列1-5题中选做3道,从下列6-10题中选做3道,每题10分, 试卷总计60分,平时成绩40分,期末总评100分。) 1.证明或推翻下列命题:“设⊕表示集合的对称差运算,则对于任意集合A 和B成立:P(4)由P(B)=P(A)P(C心B=C”。(10分) 解答与评分标准 命题成立(2分)。 证明:⊕有消去律,P(A)P(B=P(A)P(C)→P(B=P(C)(3分)。 答 P(B)=P(C)→B=C(3分)。 其他细节(2分) 2.证明或推翻下列命题:“设R是从A到B的二元关系,则下列两个条件互 为充要条件。条件一:存在CcA且D=B”使得R=CxD。条件二:对于A 中任意x1x2和B中y12,有(x1RyAx2Ry2)x1R2” 解答与评分标准 命题成立(2分)。 条件一→条件二:x1∈C,y2∈D(3分)
- 0 - 信息科学技术学院 2002-2003 学年第二学期 本科生期末考试试卷 考试科目： 集合论与图论 考试时间：2003 年 6 月 专业 级 班 姓名 学号 毛 题 号 一 二 三 四 五 六 七 八 九 十 总分 得 分 （注意：从下列 1-5 题中选做 3 道，从下列 6-10 题中选做 3 道，每题 10 分， 试卷总计 60 分，平时成绩 40 分，期末总评 100 分。） 1． 证明或推翻下列命题：“设⊕表示集合的对称差运算，则对于任意集合 A 和 B 成立：P(A)⊕P(B)=P(A)⊕P(C)⇔B=C”。（10 分） 解答与评分标准： 命题成立（2 分）。 证明：⊕有消去律，P(A)⊕P(B)=P(A)⊕P(C)⇔P(B)=P(C)（3 分）。 P(B)=P(C)⇔B=C （3 分）。 其他细节（2 分） 2． 证明或推翻下列命题：“设 R 是从 A 到 B 的二元关系，则下列两个条件互 为充要条件。条件一：存在 C⊆A 且 D⊆B”使得 R=C×D。条件二：对于 A 中任意 x1,x2和 B 中 y1,y2，有(x1Ry1∧x2Ry2)→x1Ry2.” 解答与评分标准： 命题成立（2 分）。 条件一 ⇒ 条件二：x1∈C，y2∈D（3 分）。 装 订 线 内 请 勿 答 题
条件二→条件一:C=dom(R),D=an(R)(3分) 其他细节(2分) 3.设A={12,,10},定义A上的二元关系R={xy∈Ax+y=10},说明R 具有哪些性质并说明理由 解答与评分标准 讨论5种性质(各2分)。 非自反:不属于A 非反自反:∈A 对称:定义 非反对称:∈A但7不等于3。 非传递:,∈A但不属于A 4.比较下列集合的基数大小并给出证明:AxA,P(A),2→A,A→2 解答与评分标准: 4x4=12→4=团42(2分), P(A)=4→2|=21(2分) 分情况讨论: (1)A为空集:注意A→2={空关系} 4x4=12→A|=08=214=P(4)=1A→21。(1分) (5)A为有限集且44 4=12→4=|4 P(A)=14→2。(1分) (6)A为无限集: 4x4=12→4=团42=团<21(康托定理)=|P()=|4→21(1分)。 注(1)(2)(5)6)结果相同,可合并。 5.在一种计算机信息检索的模型中,一个文件是由一些关键字组成的,而 个倒排文件是由含有某个关键字的所有文件组成的。一次查询的输入是一 个关键字,输出是这个关键字的倒排文件,一次查询的开销就是包含这个 关键字的文件个数。多次查询就是查询一个关键字序列(其中可能有重复 关键字)中的每个关键字,多次查询的开销是各次查询的开销之和,其中
- 1 - 条件二 ⇒ 条件一：C=dom(R)，D=ran(R)（3 分）。 其他细节（2 分） 3． 设 A={1,2,…,10}，定义 A 上的二元关系 R={|x,y∈A∧x+y=10}，说明 R 具有哪些性质并说明理由。 解答与评分标准： 讨论 5 种性质（各 2 分）。 非自反：不属于 A。 非反自反：∈A。 对称：定义。 非反对称：,∈A 但 7 不等于 3。 非传递：,∈A 但不属于 A。 4． 比较下列集合的基数大小并给出证明：A×A，P(A)，2→A，A→2. 解答与评分标准： |A×A| = |2→A| = |A| 2 （2 分）， |P(A)| = |A→2| = 2|A| （2 分）。 分情况讨论： (1) A 为空集：注意 A→2={空关系}， |A×A| = |2→A| = 0 8 = 2|A| = |P(A)| = | A→2| 。（1 分） (5) A 为有限集且|A|>4： |A×A| = |2→A| = |A| 2 < 2|A| = |P(A)| = |A→2| 。（1 分） (6) A 为无限集： |A×A| = |2→A| = |A| 2 = |A| < 2|A| （康托定理）= |P(A)| = | A→2| （1 分）。 注(1)(2)(5)(6)结果相同，可合并。 5． 在一种计算机信息检索的模型中，一个文件是由一些关键字组成的，而一 个倒排文件是由含有某个关键字的所有文件组成的。一次查询的输入是一 个关键字，输出是这个关键字的倒排文件，一次查询的开销就是包含这个 关键字的文件个数。多次查询就是查询一个关键字序列（其中可能有重复 关键字）中的每个关键字，多次查询的开销是各次查询的开销之和，其中
重复查询同一个关键字的开销之只计算一次。假设关键字和文件的个数都 是有限的,试用集合论或图论的术语来描述这个模型,并给出上述斜体字 概念的形式化定义 解答与评分标准 集合论 文件集合D={dhdh2,dn},关键字集合K={k1,k2km},倒排文件集合 K={k1k2,km}与关键字集合K一一对应。D包含于P(K,K包含于 PD),k属于d当且仅当d属于k(4分)。查询是从K到P(D)的函数 Q:K→P(D),查询k是求Q(k)(2分),查询k的开销是Qk川(2分) 多次查询(s12S)就是求(Q(s1)Q(2),(s),多次查询的开销是对不 同的s求(Q(s之和(2分) 图论: 部图G=,D为文件集合,K为关键字集合,E为边集合,(d,k) 是E中的边当且仅当文件d含有关键字k(4分)。文件d的内容就是d 的相邻顶点集合(邻域),倒排文件k的内容就是k的邻域,查询k就是 求k的邻域(2分),查询k的开销就是k的度数(2分)。多次查询就 是求一组关键字的邻域,多次查询的开销就是这组关键字顶点的度数之 和,重复关键字只计算一次(2分)。 6.证明或推翻下列命题:“设平面上有100个点,其中任意两点间的距离至 少是1,则最多有300对点距离恰好是1” 解答与评分标准 命题成立(2分)。 无向图G=,V是平面上的这100个点,两个点相邻当且仅当这两点 距离恰好是1(2分)。 每个顶点的度数不超过6(3分) 根据握手定律(3分), 2E顶点度数之和≤100*6,所以这个图的边数不超过300(2分) 7.所谓n维网格就是一个无向图G=|1s≤m lssm},E={(v,n2)v1和n2恰好只在一个坐标上相差1}。讨论当m和n 哪些正整数值时,G是哈密顿图,并给出证明。 解答与评分标准 分情况讨论。注意G的顶点数是m1*m2*m3*,*mn (1)所有m都为1:G是平凡图,是哈密顿图(2分) (2)恰好有一个m大于1:G是长度大于1的初级路径,不是哈密顿图 (2分)
- 2 - 重复查询同一个关键字的开销之只计算一次。假设关键字和文件的个数都 是有限的，试用集合论或图论的术语来描述这个模型，并给出上述斜体字 概念的形式化定义。 解答与评分标准： 集合论： 文件集合 D={d1,d2,…,dn}，关键字集合 K={k1,k2,…,km}，倒排文件集合 K’={k1’,k2’,…,km’ }与关键字集合 K 一一对应。D 包含于 P(K)，K’包含于 P(D)，ki属于 dj当且仅当 dj属于 ki’（4 分）。查询是从 K 到 P(D)的函数 Q：K→P(D)，查询 k 是求 Q(k)（2 分），查询 k 的开销是|Q(k)|（2 分）。 多次查询(s1,s2,…,st)就是求(Q(s1),Q(s2),…,Q(st))，多次查询的开销是对不 同的 si求|Q(si)|之和（2 分）。 图论： 二部图 G=，D 为文件集合，K 为关键字集合，E 为边集合，(d,k) 是 E 中的边当且仅当文件 d 含有关键字 k（4 分）。文件 d 的内容就是 d 的相邻顶点集合（邻域），倒排文件 k 的内容就是 k 的邻域，查询 k 就是 求 k 的邻域（2 分），查询 k 的开销就是 k 的度数（2 分）。多次查询就 是求一组关键字的邻域，多次查询的开销就是这组关键字顶点的度数之 和，重复关键字只计算一次（2 分）。 6． 证明或推翻下列命题：“设平面上有 100 个点，其中任意两点间的距离至 少是 1，则最多有 300 对点距离恰好是 1”。 解答与评分标准： 命题成立（2 分）。 无向图 G=，V 是平面上的这 100 个点，两个点相邻当且仅当这两点 距离恰好是 1（2 分）。 每个顶点的度数不超过 6（3 分）。 根据握手定律（3 分）， 2|E|=顶点度数之和 ≤100*6, 所以这个图的边数不超过 300（2 分）。 7． 所谓 n 维网格就是一个无向图 G=，其中 V={ | 1≤ij≤mj, 1≤j≤n}，E={(v1,v2)| v1和 v2恰好只在一个坐标上相差 1}。讨论当 mj和 n 取 哪些正整数值时，G 是哈密顿图，并给出证明。 解答与评分标准： 分情况讨论。注意 G 的顶点数是 m1*m2*m3*…*mn。 (1) 所有 mj都为 1：G 是平凡图，是哈密顿图（2 分）。 (2) 恰好有一个 mj大于 1：G 是长度大于 1 的初级路径，不是哈密顿图 （2 分）
(3)至少有两个m大于1:G是偶图(无奇数长度回路)(2分) (3a)m*m2*m*…*mm是偶数:G是哈密顿图,用归纳法构造哈密顿回 路(2分)。 (3b)m*m2*m*,*mn是奇数:G不是哈密顿图,偶哈密顿图两部分顶 点数相等,总顶点数是偶数(2分) 8.证明或推翻下列命题:“任意给定平面上有限个点,则连接这些点的最短 哈密顿回路的长度不超过连接这些点的最小生成树(不添加额外顶点)的 长度的2倍。子图的长度就是这个子图上的边的长度之和 解答与评分标准 命题成立(2分) (课本图论部分最后一章定理)先求最小生成树奇数度顶点之间的“最 小”匹配,加入匹配“边”得到欧拉图(3分) 沿着欧拉回路前进,“抄近路”避开已经访问过的顶点,就得出哈密顿回 路(3分) 由于距离的三角形不等式,这条哈密顿回路长度不超过最小生成树长度的 2倍(2分)。 9.画出所有非同构的5阶根树 解答与评分标准 9种(每种1分,重复画扣0.5分,全画10分)。非同构的5阶树共有3 种,分别选一个顶点做根。 10.证明或推翻下列命题:“设连通简单平面图G的最小度8(G)≥4,则G的 点色数x(G≥3.” 解答与评分标准 假设X(G)<3.(反证法分情况讨论2分) x(G=1当且仅当G为n阶零图,与已知矛盾。(4分) x(G=2当且仅当G为二部图,因为G为平面图,只能为K2,或K2.此时 必有(G)=2,与已知矛盾。(4分)
- 3 - (3) 至少有两个 mj大于 1：G 是偶图（无奇数长度回路）（2 分）。 (3a) m1*m2*m3*…*mn是偶数：G 是哈密顿图，用归纳法构造哈密顿回 路（2 分）。 (3b) m1*m2*m3*…*mn是奇数：G 不是哈密顿图，偶哈密顿图两部分顶 点数相等，总顶点数是偶数（2 分）。 8． 证明或推翻下列命题：“任意给定平面上有限个点，则连接这些点的最短 哈密顿回路的长度不超过连接这些点的最小生成树（不添加额外顶点）的 长度的 2 倍。子图的长度就是这个子图上的边的长度之和。” 解答与评分标准： 命题成立（2 分）。 （课本图论部分最后一章定理）先求最小生成树奇数度顶点之间的“最 小”匹配，加入匹配“边”得到欧拉图（3 分）。 沿着欧拉回路前进，“抄近路”避开已经访问过的顶点，就得出哈密顿回 路（3 分）。 由于距离的三角形不等式，这条哈密顿回路长度不超过最小生成树长度的 2 倍（2 分）。 9． 画出所有非同构的 5 阶根树。 解答与评分标准： 9 种（每种 1 分，重复画扣 0.5 分，全画 10 分）。非同构的 5 阶树共有 3 种，分别选一个顶点做根。 10．证明或推翻下列命题：“设连通简单平面图 G 的最小度δ(G)≥4，则 G 的 点色数χ(G)≥3.” 解答与评分标准： 假设χ(G)<3.（反证法分情况讨论 2 分） χ(G)=1 当且仅当 G 为 n 阶零图，与已知矛盾。（4 分） χ(G)=2 当且仅当 G 为二部图，因为 G 为平面图，只能为 K2,s或 Kr,2. 此时 必有δ(G)=2, 与已知矛盾。（4 分）