集合论与图论（下）教学大纲
《集合论与图论》是计算机大类/软件工程大类专业的一门专业基础课。本课程为后继的专业基础课及专业课提供必要的数学工具，为描述离散模型提供数学语言。该课程的设置主要是为了培养学生的抽象思维和逻辑推理能力，提高学生提出问题、分析问题和解决问题的能力，提高学生的数学修养及计算机科学素质。
课程概述
要想用计算机解决问题就要为它建立数学模型，即描述研究对象及对象与对象之间的联系，并通过事物之间的联系找出事物的运动规律。集合论与图论为此提供了强有力的描述工具与推理理论。
本课程的目标是通过理论学习，使学生正确地理解概念，正确地使用概念进行推理，养成一个好的思维习惯，理解理论与实践的关系。引导学生观察生活、社会和大自然，分析事物间的联系，建立系统的模型，提出和解决其中的复杂工程问题。
本课程主要包含二部分内容：集合论与图论。集合论是整个数学的基础，也是计算机科学的基础，计算机科学领域中的大多数基本概念和理论，几乎均采用集合论的有关术语来描述和论证，而图论的基本知识则将始终陪伴着每一个计算机工作者的职业生涯。
计算学科以抽象、理论、设计为其学科形态，以数学方法和系统方法为其学科方法，本课程的核心目标就是在抽象和理论的基础上提供数学方法，因此，本课程是整个专业的基础课程，是计算机专业最重要的课程之一。
《集合论与图论》（上）主要讲述集合论部分，《集合论与图论》（下）主要讲述图论部分。
授课目标
课程具体目标如下：
课程目标1：掌握集合论与图论的基本概念、基本原理、基本方法等基本知识，培养形式化、模型化的抽象思维能力，使学生能够利用集合论与图论的概念、理论与方法识别、表达计算相关的复杂工程问题，逐步学会为计算类复杂工程问题建立数学模型；
课程目标2：掌握直接证明法、反证法、数学归纳法、构造法等常用的证明方法，培养机械化、自动化的逻辑推理能力，使学生能够利用集合论与图论的概念、理论与方法并通过文献研究分析复杂工程问题，并能获得有效的结论，理解并逐步设计求解这些问题的算法基本思想；
课程目标3：掌握资料查阅方法，学会对课堂所学理论知识进行扩展，培养自学能力。
课程目标4：能够利用本课所学知识分析工程实际问题或针对某些应用背景探讨所学知识的局限性，培养学生的独立思考与创新能力。
课程大纲
第1讲图的基本概念
1.1 课前准备-图论
1.2 简史
1.3 图
1.4 图的表示
1.5 图模型
1.6 子图
1.7 度
1.8 正则图
1.9 同构
第1讲测验
第2讲连通图、补图、偶图
2.1 路、圈
2.2 连通图
2.3 判定是否连通
2.4 几类证明方法
2.5 判定是否有圈
2.6 关于路和圈的一个定理2.7 补图
2.8 双图
2.9 图兰定理
2.10 极图理论
第2讲测验
第3讲欧拉图
3.1 欧拉图、欧拉定理
3.2 欧拉定理的扩展
第3讲测验
第4讲哈密顿图
4.1 背景
4.2 哈密顿图
4.3 哈密顿图判定的必要条件4.4 哈密顿图判定的充分条件第４讲测验
第5讲图的表示、带权图5.1 邻接矩阵
5.2 邻接表
5.3 关联矩阵
5.4 图解
5.5 带权图
第5讲测验
第6讲树、割集
6.1 树的定义
6.2 树的性质
6.3 极小连通图
6.4 树的中心
6.5 生成树
6.6 最小生成树
6.7 割点
6.8 割点的性质
第6讲测验
第7讲图的连通度
7.1 背景
7.2 顶点连通度和边连通度
7.3 顶点连通度和边连通度的关系7.4 n连通
7.5 明格尔定理
7.6 柯尼希定理
7.7 网络流问题
第7讲测验
第8讲匹配问题
8.1 独立集
8.2 偶图的匹配
8.3 偶图匹配的条件
8.4 相异代表系
第8讲测验
第9讲平面图
9.1 背景
9.2 平面图的定义
9.3 欧拉公式
9.4 例题
9.5 非哈密顿平面图
第9讲测验
第10讲图的顶点着色问题10.1 图的顶点着色
10.2 色数的上、下界
10.3 四色定理vs 五色定理第10讲测验
第11讲有向图的基本概念11.1 有向图的表示
11.2 有向图中顶点的度11.3 有向完全图
11.4 有向图的同构
11.5 有向路、有向圈
11.6 邻接矩阵
第11讲测验
第12讲有根树、有序树、比赛图12.1 有根树、有序树
12.2 比赛图
第12讲测验
预备知识
工科数学分析、线性代数
本试卷满分90分 （06级计算机、信息安全专业、实验学院） 一、判断对错（本题满分10分，每小题各1分） （ 正确画“√”，错误画“×”） 1．对每个集合A ，A A 2}{∈。 （×） 2．对集合Q P ,，若?==Q P Q Q P ,，则P =?。 （√） 3．设,,:X A Y X f ?→若)()(A f x f ∈，则A x ∈。 （×） 4．设,,:Y B Y X f ?→则有B B f f ?-))((1。 （×） 5．若R 是集合X 上的等价关系，则2R 也是集合X 上的等价关系。 （√） 6．若:f X Y →且f 是满射，则只要X 是可数的，那么Y 至多可数的。（√） 7．设G 是有10个顶点的无向图，对于G 中任意两个不邻接的顶点u 和v, 均有9deg deg ≥+v u ，则G 是哈密顿图。 （×） 8．设)(ij a A =是 p 个顶点的无向图G 的邻接矩阵，则对于G 的顶点i v , 有∑==p j ij i a v 1deg 成立。 （√） 9. 设G 是一个),(q p 图，若1-≥p q ，则]/2[)(q p G ≤χ。 （×） 10．图G 和1G 同构当且仅当G 和1G 的顶点和边分别存在一一对应关系。（×）
二.填空(本题40分，每空各2分) 1．设}},{,{φφ=S 则=S 2 }}}{,{}},{{},{,{φφφφφ 。 2．设B A ,是任意集合，若B B A =\，则A 与B 关系为 φ==B A 。 3．设1)(,0)()(,:};3,2{},1,0{},,,{===→===c f b f a f Y X f Z Y c b a X , 3)1(,2)0(,:==→g g Z Y g ,则)()(c f g a f g ，分别为 2，3 。 4．设X 和Y 是集合且X m =，Y n =，若n m ≤，则从X 到Y 的单射的 个数为 !m C m n 。 5．设}2,1{},,,2,1{==B n X ，则从X 到Y 的满射的个数为 22-n 。 6．设)}2,4(),1,3(),3,2{()},4,3(),2,2(),2,1{(},4,3,2,1{===S R X ，则 =)(R S R )}2,3(),4,2(),4,1{( 。 7． 设???? ??=???? ??=5123454321,415235432121σσ，则???? ??=235411234521σσ 。 8. 设)},(),,(),,{(},,,,{a c c b b a R d c b a X ==，则 )},(),,(),,(),,(),,(),,(),,(),,(),,{(b c a c a b c b c a b a c c b b a a R =+ 。 9. 设X 为集合且X n =，则X 上不同的自反或对称的二元关系的个数 为 22222222n n n n n n +--+- 。 10．设}}{},{},,{{},,,,{d c b a A d c b a X ==是X 的一个划分，则由A 确定的 X 上的等价关系为 )},(),,(),,(),,(),,(),,{(d d c c a b b a b b a a 。 11．}10,,2,1{ =S ，在偏序关系“整除”下的极大元为 6，7，8，9，10 。 12．给出一个初等函数)(x f ，使得它是从)1,0(到实数集合R 的一一对应， 这个函数为 x ctg π或-x ctg π或)2/(ππ-x tg 。 13. 设G 是),(p p 连通图，则G 的生成树的个数至多为 p 。
一、用真值表证明德*摩根律（证明其中一条即可）。 二、设A,B,C是集合，试问在什么条件下(A-B)-C=A-(B-C)？给出证明。 三、设A={a,b,c}，问A上有多少种不同的：二元关系？自反关系？对称关系？传递关系？等价关系？偏序关系？良序关系？ 四、用花括号和空集来表示1?2（注意?表示集合的叉乘）. 五、设R是实数集，Q是有理数集，试构造出R-Q与R之间的双射. 1．简单叙述构造的思路； 2．给出双射f：R-Q -> R 或f：R -> R-Q的严格定义。 2008年期末考题： 一、在有向图中，如果存在从顶点u到顶点v的有向通路，则说u可达v；如果顶点u和顶点v互相可达，则说u双向可达v。回答下列问题： 1．顶点集上的可达关系是不是等价关系？为什么？ 2．顶点集上的双向可达关系是不是等价关系？为什么？ 3．对于上述两个关系，如果是等价关系，其等价类的导出子图称为什么？ 二、一棵树有13个顶点，除了3个2度顶点和若干个树叶之外，其余顶点都是5度。 1．求出5度顶点的个数（写出计算过程）； 2．画出所有互不同构的这种树。 三、计算出右图中v1到v4长度为4的通路数（要写出计算过程 的主要步骤），并写出一个最小支配集、一个最大团、一个最小 边覆盖、一个最大匹配。 四、如果一个图中所有顶点度数都为k，则称为k正则图。8阶3 正则简单图一定是平面图吗？一定不是平面图吗？为什么？ 五、证明：如果正则简单图G和补图G都是连通图，则G和G中至少有一个是欧拉图。 六、证明：如果n阶（n≥3）简单图G中，对于任何1≤j
哈工大 2007 年 秋季学期 本试卷满分90分 （06级计算机、信息安全专业、实验学院） 一、判断对错（本题满分10分，每小题各1分） （ 正确画“√”，错误画“×”） 1．对每个集合A ，A A 2}{∈。 （×） 2．对集合Q P ,，若?==Q P Q Q P ,，则P =?。 （√） 3．设,,:X A Y X f ?→若)()(A f x f ∈，则A x ∈。 （×） 4．设,,:Y B Y X f ?→则有B B f f ?-))((1。 （×） 5．若R 是集合X 上的等价关系，则2R 也是集合X 上的等价关系。 （√） 6．若:f X Y →且f 是满射，则只要X 是可数的，那么Y 至多可数的。（√） 7．设G 是有10个顶点的无向图，对于G 中任意两个不邻接的顶点u 和v, 均有9deg deg ≥+v u ，则G 是哈密顿图。 （×） 8．设)(ij a A =是p 个顶点的无向图G 的邻接矩阵，则对于G 的顶点i v , 有∑==p j ij i a v 1deg 成立。 （√） 9. 设G 是一个),(q p 图，若1-≥p q ，则]/2[)(q p G ≤χ。 （×） 10．图G 和1G 同构当且仅当G 和1G 的顶点和边分别存在一一对应关系。（×）
二.填空(本题40分，每空各2分) 1．设}},{,{φφ=S 则=S 2 }}}{,{}},{{},{,{φφφφφ 。 2．设B A ,是任意集合，若B B A =\，则A 与B 关系为 φ==B A 。 3．设1)(,0)()(,:};3,2{},1,0{},,,{===→===c f b f a f Y X f Z Y c b a X , 3)1(,2)0(,:==→g g Z Y g ,则)()(c f g a f g ，分别为 2，3 。 4．设X 和Y 是集合且X m =，Y n =，若n m ≤，则从X 到Y 的单射的 个数为 !m C m n 。 5．设}2,1{},,,2,1{==B n X ，则从X 到Y 的满射的个数为 22-n 。 6．设)}2,4(),1,3(),3,2{()},4,3(),2,2(),2,1{(},4,3,2,1{===S R X ，则 =)(R S R )}2,3(),4,2(),4,1{( 。 7． 设???? ??=???? ??=5123454321,415235432121σσ，则???? ??=235411234521σσ 。 8. 设)},(),,(),,{(},,,,{a c c b b a R d c b a X ==，则 )},(),,(),,(),,(),,(),,(),,(),,(),,{(b c a c a b c b c a b a c c b b a a R =+ 。 9. 设X 为集合且X n =，则X 上不同的自反或对称的二元关系的个数 为 22222222n n n n n n +--+- 。 10．设}}{},{},,{{},,,,{d c b a A d c b a X ==是X 的一个划分，则由A 确定的 X 上的等价关系为 )},(),,(),,(),,(),,(),,{(d d c c a b b a b b a a 。 11．}10,,2,1{ =S ，在偏序关系“整除”下的极大元为 6，7，8，9，10 。 12．给出一个初等函数)(x f ，使得它是从)1,0(到实数集合R 的一一对应， 这个函数为 x ctg π或-x ctg π或)2/(ππ-x tg 。 13. 设G 是),(p p 连通图，则G 的生成树的个数至多为 p 。
集合论与图论习题册 软件基础教研室 刘峰 2015.02
第一章 集合及其运算 8P 习题 1. 写出方程2210x x ++=的根所构成的集合。 2.下列命题中哪些是真的，哪些为假 a)对每个集A ，A φ∈； b)对每个集A ，A φ?； c)对每个集A ，{}A A ∈； d)对每个集A ，A A ∈； e)对每个集A ，A A ?； f)对每个集A ，{}A A ?； g)对每个集A ，2A A ∈； h)对每个集A ，2A A ?； i)对每个集A ，{}2A A ?； j)对每个集A ，{}2A A ∈； k)对每个集A ，2A φ∈； l)对每个集A ，2A φ?； m)对每个集A ，{}A A =； n) {}φφ=； o){}φ中没有任何元素； p)若A B ?，则22A B ? q)对任何集A ，{|}A x x A =∈； r)对任何集A ，{|}{|}x x A y y A ∈=∈； s)对任何集A ，{|}y A y x x A ∈?∈∈； t)对任何集A ，{|}{|}x x A A A A ∈≠∈。 答案： 3.设有n 个集合12,,,n A A A 且121n A A A A ???? ，试证：12n A A A === 。 4.设{,{}}S φφ=，试求2S ？ 5.设S 恰有n 个元素，证明2S 有2n 个元素。
16P 习题 6.设A 、B 是集合，证明:(\)()\A B B A B B B φ=?= 。 7.设A 、B 是集合，试证A B A B φ=?=?。 9.设A ，B ，C 为集合，证明：\()(\)\A B C A B C = 。 10.设A ，B ，C 为集合，证明：()\(\)(\)A B C A C B C = 。 11.设A ，B ，C 为集合，证明：()\(\)(\)A B C A C B C = 。 12.设A ，B ，C 都是集合，若A B A C = 且A B B C = ，试证B=C 。 15.下列命题是否成立？说明理由（举例）。 (1)(\)\(\)A B C A B C = ；(2)(\)()\A B C A B C = ； (3)\()()\A B C A B B = 。（答案：都不正确）
-- 本试卷满分90分 (计算机科学与技术学院0９级各专业) 一、填空（本题满分１0分,每空各1分) 1.设B A ,为集合,则A B B A = )\(成立的充分必要条件是什么？(A B ?) ２.设}2,1{},,,2,1{==Y n X ,则从X 到Y 的满射的个数为多少?（22-n ) ３．在集合}11,10,9,8,4,3,2{=A 上定义的整除关系“|”是A 上的偏序关系， 则 最大元是什么? ( 无 ） 4．设{,,}A a b c =，给出A 上的一个二元关系,使其同时不满足自反性、反自 反性、对称性、反对称和传递性的二元关系。({(,),(,),(,),(,)}R a a b c c b a c =） ５．设∑为一个有限字母表,∑上所有字(包括空字）之集记为*∑，则*∑是 否是可数集? （ 是 ) ６.含5个顶点、3条边的不同构的无向图个数为多少？ （ ４ ） 7.若G 是一个),(p p 连通图，则G 至少有多少个生成树? （ 3 ） 8. 如图所示图G ,回答下列问题： (１）图G 是否是偶图? ( 不是 ) (2）图G 是否是欧拉图? ( 不是 ） (3)图G 的色数为多少？ ( 4 ) 二、简答下列各题（本题满分40分） 1．设D C B A ,,,为任意集合，判断下列等式是否成立?若成立给出证明，若不 成立举出反例。(6分) (1))()()()(D B C A D C B A ??=? ； （2）()()()()A B C D A C B D ?=??。 解:（1）不成立。例如}{,a c B D A ====φ即可。 （2）成立。(,)x y ?∈()()A B C D ?，有,x A B y C D ∈∈，即 ,,,x A x B y C y D ∈∈∈∈。所以(,),(,)x y A C x y B D ∈?∈?,因此 (,)()()x y A C B D ∈??,从而()()A B C D ??()()A C B D ??。 反之,(,)x y ?∈()()A C B D ??，有,,,x A x B y C y D ∈∈∈∈。即 (,)x y ∈()()A B C D ?，从而()()A C B D ???()()A B C D ?。
《集合论与图论》课堂练习3 学号姓名 一、判断下列命题是否正确，并说明理由。（括号内写“是”或“否”）（40分，每题8分，是非判断4分，证明或反例4分） 1 存在7个结点的自补图。 （否） /*西安交通大学1999*/ 自补图对应的完全图的边数必须是偶数，而7个结点的完全图的边数为21。 n≥的连通图。则G没有割点当且仅当G的剖分也没有割点。 2 设G是顶点数3 （真） 如果G的剖分有割点，则G有割点，矛盾；所以G没有割点，则G的剖分也没有割点。 如果G有割点，则该割点为G的剖分的割点，所以G的剖分有割点，矛盾；所以G的剖分也没有割点则G没有割点。 3 若G是简单连通图，边数为e，结点数为n。若e≥n，则G至少有3棵生成树。 （是） /*复旦大学1998*/ /*只需证明e=n时，命题成立*/ 若e=n-1，因为G是连通的，所以为一棵树；再添加一边时，因为G是简单图，所以图中必存在一个长度大于等于3的回路，则在这个回路上任意删除一条边就得到一棵树。 4 一个有向图D中仅有一个顶点的入度为0，其余顶点的入度均为1，则D是有根树。 （否） 一个自环和孤立点 /*北京大学1991*/ 5 设C是简单连通图G的回路，若删去C中任一边后所得到的路C’为G中的最长路，则C是图G的哈密顿回路。 （是） /*复旦大学1999*/ /*反证法证明*/ 令C的长度为m。若C不是哈密顿回路，则圈外必存在一点u，它与圈上一点v邻接（因为G是连通图）。圈上与v关联的一边为e，则C-e的长度为m-1；而C-e+uv的长度为m；得C-e不是最长路。矛盾。 二、综合题（60分）
1．证明：任何平面图是5-可着色的。 证明：p125-126 2．如果有一群人，其中有k个人彼此认识或者有l个人彼此不认识。我们用r(k, l)表示这群人至少是有几个人的人数，称为Ramsey数。证明：r(3, 3)=6。 证明：6个点v1, v2, v3, v4, v5, v6表示6个人，两人认识时，在对应的两点连一条绿边，否则连一条红边。根据鸽笼原理，与v1相连的5条边中，必有3条同色。不访设v1 v2，v1 v3和v1 v4是3条绿边。如果三角形v2, v3, v4上有一条绿边，则此绿边与v1构成一个绿色三角形，于是有3人彼此认识，否则v2, v3, v4构成红色三角形，有3人彼此不认识。则r(3, 3) 6。5个点构成的完全图中，可以既无绿色三角形也无红色三角形，则r(3, 3)>5。则r(3, 3)=6。 3．如果为一个无向图的每一条边确定一个方向，使得所得到的有向图是强连通的，称该无向图是可定向的。证明：欧拉图和哈密顿图都是可定向。 解：构造性证明，沿欧拉/哈密顿回路。 4．设G为非平凡有向图，V为G的结点集合，若对V的任一非空子集S，G中起始结点在S 中，终止结点在V-S中的有向边至少有k条，则称G是k边连通的。 证明：非平凡有向图是强连通的充要条件为它是一边连通的。 证明： /*中国科学院计算所1999考研*/ /*必要性证明*/ 因为设G为强连通的，假设从S到V-S没有有向边，则S中的任一顶点u到V-S中的任一顶点v均没有有向道路，从而与G为强连通的相矛盾。所以从S到V-S至少有一条有向边，即G为一边连通的。 /*充分性证明*/ 设G为一边连通的，对任意的u, v V, 则{u}到V(G-u)至少有一条边，设为(u, u1)，而{u, u1}到V-{u, u1}至少有一条有向边(u, u2)或(u1, u2)。无论哪种情况都有从u到u2的有向道路，因为G中结点数有限，所以通过如上递归地求解，一定有从u到v的有向道路。所以G为强连通的。 5．证明：任何一个竞赛图是半哈密顿图。 证明： 归纳基础：若竞赛图的顶点数小于4，显然有一条哈密顿有向图。 归纳步骤：假设n个顶点的任一竞赛图是半哈密顿有向图。设G是n+1个顶点的竞赛图，从G中删去顶点v及其关联边，得到有向图G’，由归纳假设，G’有哈密顿有向路(v1,v2,…, v n)，G有3种情况： （1）在G中有一条弧(v,v1)，则有哈密顿有向路(v,v1,v2,…,v n)； （2）在G中没有弧(v,v1)，则必有弧(v1,v)。若存在v i，v i是v1之后第一个碰到并且有弧(v, v i)的顶点，则显然得到一条哈密顿有向路(v1,v2,…,v i-1,v,v i,…v n)； （3）在G中没有弧(v,v i)，而对所有v i，均有弧(v i,v)，i=1,2,…,n，则得一条哈密顿有向路(v1,v2,…,v n,v)。
一、（20分）对于任意集合A和B， （1）证明：P(A)?P(B) = P(A?B)；（14分） 对任意的x∈P(A)?P(B)，有x∈P(A)且x∈P(B)。即x?A并且x?B，则x?A?B。所以x∈P(A?B)。故P(A)?P(B)?P(A?B)。（7分）对任意的x∈P(A?B)，有x?A?B，即x?A并且x?B，所以x∈P(A)且x∈P(B)。因此P(A?B)?P(A)?P(B)。（7分）综上所述，P(A)?P(B)=P(A?B) （2）举例说明P(A)?P(B) ≠ P(A?B). （6分） A={1}, B={2}, A?B={1, 2}; P(A)={?, {1}}, P(B)={?, {2}}, P(A)?P(B)= {?, {1}, {2}}, P(A?B)= {?, {1}, {2}, {1, 2}}; 所以P(A)?P(B)≠P(A?B) 二、（20分）设R, S是A上的等价关系且R?S=S?R，证明： R?S是A上的等价关系. 自反性和对称性容易证明，略。（5分） 传递性证明： 对任意a, b, c∈A，如果(a, b)∈R?S, (b, c)∈R?S，要证明(a, c)∈R?S。 因为R?S=S?R，则有(b, c)∈S?R，即存在e, f∈A，使(a, e)∈R，(e, b)∈S，(b, f)∈S，(f, c)∈R。 因为S是传递的，(e, b)∈S，(b, f)∈S，所以(e, f)∈S；因为(a, e)∈R，所以(a, f)∈R?S；R?S是对称的，则(f, a)∈R?S；因为R是对称的，(f, c)∈R，则(c, f)∈R。因为(f, a)∈R?S，则存在g∈A，使得(f, g)∈R，(g, a)∈S；因为R是传递的，
《集合论与图论》课程示范性教学设计 1 本课程教学方法 （一）教学方法 在这里，仅总结一下我的教学方法，不细展开，因此不涉及专业术语和与专业有关的例子。以下仅是一些指导思想： （1 ）启发式、由浅入深、从直观到抽象。要用些生动的例子帮助学生理解抽象概念的含义，但要做到生动而有趣又不失概念的准确性和推理的严格性，使学生易于接受，又了解直观背景。 （2 ）突出基本思想及方法，强调规律性，提高学生的抽象能力。要从哲学的高度强调概念是第一位的，引导学生思考问题时必须清楚理解所涉及的概念，使问题有一个明确的提法，引导学生掌握从问题到建立数学模型这一抽象过程的方法。 （3 ）利用集合论某些概念和理论与方法总结已学过的知识（如微积分、线性代数）找出本质的规律或主线，使学生认识事物内部的深刻规律。其次，随时指出在后继课如何应用这些知识、在科技论文中将怎样出现这些知识的应用。这不仅提高了学习的积极性，也使学生增强了学习的目的性。 （4 ）只要有可能就要以建立数学模型组织教学，讲习题也不例外。这样，能使学生加深印象—任何时候都要抓住事物的本质与事物之间的联系。 （5 ）鼓励学生多问为什么，为什么会是这样子而不是那个样子。不是教会学生怎样去使用工具、去模仿或复制，而是要教会学生独立思考，发现问题，提出问题和解决问题的思考，否则思维会退化。 （5 ）适当地提出一些未解决的问题。尚无答案的问题是摆在我们及学生面前的有无限价值的东西，因为支持大学的最高准则是探究未知领域。事实上，在每年教此课时，提一些问题确实有学生在思考。 （6 ）注意每个学科（内部）的美。如果某部分很丑或太复杂，人们倾向于认为是不清楚的和暂时的，它没有真正反映客观规律，因为我们相信，越接近终极真理，我们的解释中的不自然的东西就越少。科学是以越来越完美、有力的理论向终极真理发展的。 （二）关于素质教育、培养创新精神的人才的思考 素质教育应该是各类教育的核心，而培养创新人才则是高等教育的任务（见高等教育法，第五条）。在这里讨论这个题目不太合适，因为题太大。其实，在（五）中就本课的特点贯穿了素质教育和培养创新人才的思想。以下只扼要地总结一下。 1 ）教会学生如何进行逻辑推理，如何进行正确地思维，如何在纷繁的事物中抓住主要的联
08信安专业离散数学期中考试试题 1.设A, B, C, D为4个集合. 已知A?B且C?D.证明: A∪C?B∪D; A∩C?B∩D . (15分) 2.化简以下公式: A∪((B―A)―B) (10分) 3.设R是非空集合A上的二元关系.证明:R∪R-1是包含R的 最小的对称的二元关系. (15分) 4.设A={1,2,…,20},R={
期中考试试题解答 1.证明: ?x, x∈A∪C x∈A∩C ?x∈A∨x∈C ?x∈A∧x∈C ?x∈B∨x∈D (A?B,C?D) ?x∈B∧x∈D (A?B,C?D) ?x∈B∪D ?x∈B∩D ∴A∪C?B∪D ∴A∩C?B∩D 2.解: A∪((B―A)―B) =A∪((B∩∽A)∩∽B) =A∪(∽A∩(B∩∽B)) =A∪(∽A∩φ) =A∪ф =A . 3.证明:首先证R∪R-1是对称关系. ?
集合论图论复习题 1、填空题 ⑴ 设A={2，a ，{3}，4}，B={Φ，4，{a}，3}，则A ⊕B= ； ⑵ 设A={2，3，4}，则P （A ）= ； ⑶ 设A={{2}，{2，4}}，则 A — A= ； ⑷ 设
《集合论与图论》期中考试 （2007年4月30日复旦大学计算机科学与工程系06级） 学号姓名成绩 一、是非判断题 3．非空集合A上不存在二元关系R，使得R既是A上的等价关系，又是A上的偏序关系。（假） 反例：恒等关系。 4．设（A，≤）是偏序集，?≠B?A，若B有上界，则B必有上确界。 （假） 反例：（{2，3，24，36}，/）。 二、综合题 设R是集合A上的二元关系 1）求A上包含R的最小等价关系E的表达式; 2）证明E的最小性; 3）以A={1, 2, 3, 4, 5, 6}, R={(1, 2), (1, 3), (4, 4), (4, 5)}为例验证你的结果. （建议评分：15分，每小题5分） /* 解题分析： 求A上包含R的最小等价关系，就是求R的自反、对称和传递闭包。 因为，所以E的表达式应该是E=tsr(R)=rts(R)，而E=str(R)=rst(R)是不成立的。 最小性结合闭包的定义进行证明。*/ 解： 1）E=tsr(R)=rts(R) 证明： 2）假设P是集合A上包含R的任一等价关系。 因为P是自反的，所以r(R)?P； 因为P是对称的，所以sr(R) ?P； 因为P是传递的，所以tsr(R) ?P； 所以E?P，从而保证了E的最小性。 3) E=tsr(R)=rts(R)=rt({(1, 2), (2, 1), (1, 3), (3, 1), (4, 4), (4, 5), (5, 4)})=r({(1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2), (4, 5), (5, 4), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5)})= {(1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2), (4, 5), (5, 4), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6,
精品文档 本试卷满分90分 （计算机科学与技术学院09级各专业） 一、填空(本题满分10分，每空各1分) 1．设B A ,为集合，则A B B A =Y )\(成立的充分必要条件是什么？（A B ?） 2．设}2,1{},,,2,1{==Y n X Λ，则从X 到Y 的满射的个数为多少？（22-n ） 3．在集合}11,10,9,8,4,3,2{=A 上定义的整除关系“|”是A 上的偏序关系， 则最大元是什么？ （ 无 ） 4．设{,,}A a b c =，给出A 上的一个二元关系，使其同时不满足自反性、反自 反性、对称性、反对称和传递性的二元关系。（{(,),(,),(,),(,)}R a a b c c b a c =） 5．设∑为一个有限字母表，∑上所有字（包括空字）之集记为*∑，则*∑是 否是可数集？ （ 是 ） 6．含5个顶点、3条边的不同构的无向图个数为多少？ （ 4 ） 7．若G 是一个),(p p 连通图，则G 至少有多少个生成树? （ 3 ) 8. 如图所示图G ，回答下列问题： （1）图G 是否是偶图？ （ 不是 ） （2）图G 是否是欧拉图？ （ 不是 ） （3）图G 的色数为多少？ （ 4 ） 二、简答下列各题（本题满分40分） 1.设D C B A ,,,为任意集合，判断下列等式是否成立？若成立给出证明，若不 成立举出反例。（6分） （1）)()()()(D B C A D C B A ??=?Y Y Y ； （2）()()()()A B C D A C B D ?=??I I I 。 解：（1）不成立。例如}{,a c B D A ====φ即可。 （2）成立。(,)x y ?∈()()A B C D ?I I ，有,x A B y C D ∈∈I I ，即 ,,,x A x B y C y D ∈∈∈∈。所以(,),(,)x y A C x y B D ∈?∈?，因此 (,)()()x y A C B D ∈??I ，从而()()A B C D ?I I ?()()A C B D ??I 。 反之，(,)x y ?∈()()A C B D ??I ，有,,,x A x B y C y D ∈∈∈∈。即 (,)x y ∈()()A B C D ?I I ，从而()()A C B D ??I ?()()A B C D ?I I 。 因此，()()A B C D ?I I ＝()()A C B D ??I 。 2. 设G 是无向图，判断下列命题是否成立？若成立给出证明，若不成立举出 反例。（6分） （1）若图G 是连通图，则G 的补图C G 也是连通图。
例： 1、设A,B是两个集合,B≠￠,试证:若A×B=B×B, 则A=B。 2、设A,B,C,D是任意四个集合，证明： （A∩B)×(C∩D)=(A×C)∩(B×D) 3、某班30名学生中学英语有7人，学日语有5人，这两科都选有3人，问两科都不选的有多少人？ (|AC∩BC|+|A∪B|=30, |AC∩BC|=21人) 4、令N={1,2,3,…}，S:N→N，则 (1)?n∈N,S(n)=n+1,Ｓ称为自然数集N上的后继函数。 (2)S(1)=1,?n∈N,S(n)=n-1,n≥2,Ｓ称为自然数集N 上的前仆函数。 5、设f:N×N →N,f((x,y))=xy。则 （1）说明f是否是单射、满射或双射？ （2）求f(N×{1}),f-1({0})。 (1,4)≠(2,2),f((1,4))=f((2,2))=4； ?y∈N,f((1,y))=1·y=y,任一元都有原象； [f不是单射,f是满射] f(N×{1})={n·1|n ∈N}=N； f-1({0})={(x,y)|xy=0}={N×{0}}?{{0}×N}。 6、设R、I、N是实数、整数、自然数集合，下面定义映射f1,f2,f3,f4,f5,f6，试确定它们的性质。（0 ∈N） （1）f1:R→R,f1(x)=2x； （2）f2:I→N,f2(x)=|x|； f1单射，不是满射。f2不是单射，满射。 （3）f3:N→N,f3(n)=n(mod3)； （4）f4:N→N×N,f4(n)=(n,n+1)； f3不是单射，不是满射；f4单射，不是满射。 （5）f5:R→R,f5(x)=x+2； （6）f6:R→R,f6(x)=x2,x≥0,f6(x)=-2,x<0；
哈工大 2008 年 秋季学期 题号 一 二 三 四 五 六 总分 分数 班号 姓名 本试卷满分90分 （计算机科学与技术学院07级） 一、填空（本题满分10分，每小题各1分） 1.设B A ,是集合，若B B A =?，则A 等于什么？ （ Φ=A ） 2．设X 为集合，R 为X 上的偏序关系，计算1i i R ∞ =U 等于什么？ （ R ） 3．把置换??? ? ??436987251123456789分解成循环置换的乘积。 （（149）（2367）（58）） 4．什么是无穷集合？ （凡能与自身的一个真子集对等的集称为无穷集合） 5．设T 是一棵树，2p ≥，则p 个顶点的树T 至多有多少个割点？ （p -2 ） 6．设D 是一个有p 个顶点q 条弧的有向图，若D 是连通的，则q 至少是多大？（ p -1 ） 7．设},,2,1{n V Λ=，则以V 为顶点集的无向图共有多少个？ （2/)1(2-p p ） 8．设},,2,1{n V Λ=，则以V 为顶点集的有向图共有多少个？)1(2-p p ）
9．每个有3个支的不连通图，若每个顶点的度均大于或等于2，则该图至少有多少个圈？ （ 3 ） 10．设T 是一个正则二元树，它有0n 个叶子，则T 有多少条弧？（2（0n -1）） 二、判断对错（本题满分10分，每小题各1分） 1.设B A ,是两个集合，则A B ?且A B ∈不可能同时成立。 （ 错 ） 2．在集合}10,,2,1{Λ上可以定义102个二元运算。 （ 错 ） 3． 设:f X Y →，若 是可逆的。 （ 错 ）
4．设是一个集合，则 上的自反和反自反的二元关系个数相同。 （对）5.设∑为一个有限字母表，∑上所有字（包括空字）之集记为*∑。则*∑不是可数集。（错） 6.设G是一个(,) ≥，则G中必有圈。（对） p q图，若q p
集合论与图论（下）教学大纲 《集合论与图论》是计算机大类/软件工程大类专业的一门专业基础课。本课程为后继的专业基础课及专业课提供必要的数学工具，为描述离散模型提供数学语言。该课程的设置主要是为了培养学生的抽象思维和逻辑推理能力，提高学生提出问题、分析问题和解决问题的能力，提高学生的数学修养及计算机科学素质。 课程概述 要想用计算机解决问题就要为它建立数学模型，即描述研究对象及对象与对象之间的联系，并通过事物之间的联系找出事物的运动规律。集合论与图论为此提供了强有力的描述工具与推理理论。 本课程的目标是通过理论学习，使学生正确地理解概念，正确地使用概念进行推理，养成一个好的思维习惯，理解理论与实践的关系。引导学生观察生活、社会和大自然，分析事物间的联系，建立系统的模型，提出和解决其中的复杂工程问题。 本课程主要包含二部分内容：集合论与图论。集合论是整个数学的基础，也是计算机科学的基础，计算机科学领域中的大多数基本概念和理论，几乎均采用集合论的有关术语来描述和论证，而图论的基本知识则将始终陪伴着每一个计算机工作者的职业生涯。 计算学科以抽象、理论、设计为其学科形态，以数学方法和系统方法为其学科方法，本课程的核心目标就是在抽象和理论的基础上提供数学方法，因此，本课程是整个专业的基础课程，是计算机专业最重要的课程之一。 《集合论与图论》（上）主要讲述集合论部分，《集合论与图论》（下）主要讲述图论部分。 授课目标 课程具体目标如下： 课程目标1：掌握集合论与图论的基本概念、基本原理、基本方法等基本知识，培养形式化、模型化的抽象思维能力，使学生能够利用集合论与图论的概念、理论与方法识别、表达计算相关的复杂工程问题，逐步学会为计算类复杂工程问题建立数学模型；
北京大学信息科学技术学院期末试卷考试科目：集合论与图论姓名：学号： 考试时间：2018 年 1 月 2 日任课教师: 参考答案 以下为试题和答题纸，共 5 大题。
一、（20分）设n是某个自然数，N是自然数集，回答下列 问题并给出证明： (1) P(n)是否传递集？ 证明：n为传递集，A为传递集当且仅当P(A)为传递集 所以P(n)为传递集 (2) P(N)是否归纳集？ P(N)不是归纳集，N+=N?{N}?P(N)，因为P(N)的任意元素A都是N的子集，所以A的元素都是自然数。因此是有限集，所以P(N)对后继运算不封闭，故P(N)不是归纳集 二、（20分）对于无向图G1=(V1,E1)和G2=(V2,E2)，如果有 函数f:V1→V2满足以下性质：对于任意的u,v∈ V1， (u,v) ∈ E1 ? ( f(u), f(v) ) ∈ E2， 则说f是从G1到G2的同态。把同态看作全体无向图上的二元关系，试回答下列问题并给出证明。 (1) 同态关系是否自反的？ 是，恒等映射 (2) 同态关系是否反自反的？ 不是，实际是自反的
(3) 同态关系是否对称的？ 不是，K1同态到K2，反之不然。 (4) 同态关系是否反对称的？ 不是，K2和K1,2互相同态 (5) 同态关系是否传递的？ 是，由定义可知同态的合成还是同态 (6) 证明：图G可以k-着色当且仅当G可以同态到k个顶点的完全图。（?）设颜色集为{1,2,…,k}，设完全图的顶点集为{u1,u2,…,u k}，设k-着色为g: V→{1,2,…,k}，则同态为f:V→{u1,u2,…,u k}， f(v)=u g(v)，即着g(v)色的同色顶点都对应到完全图同一个点u g(v)上。（?）设完全图的顶点集为{u1,u2,…,u k}，设同态为f:V→{u1,u2,…,u k}，则给f-1(u i)中的顶点都着颜色i。
哈工大 2007 年 秋季学期 本试卷满分90分 （06级计算机、信息安全专业、实验学院） 一、判断对错（本题满分10分，每小题各1分） （ 正确画“√”，错误画“×”） 1．对每个集合A ，A A 2}{∈。 （ ） 2．对集合Q P ,，若?==Q P Q Q P ,，则P =?。 （ ） 3．设,,:X A Y X f ?→若)()(A f x f ∈，则A x ∈。 （ ） 4．设,,:Y B Y X f ?→则有B B f f ?-))((1。 ( ) 5．若R 是集合X 上的等价关系，则2R 也是集合X 上的等价关系。 （ ） 6．若:f X Y →且f 是满射，则只要X 是可数的，那么Y 是至多可数的。 （ ） 7．设G 是有10个顶点的无向图，对于G 中任意两个不邻接的顶点u 和v, 均有9deg deg ≥+v u ，则G 是哈密顿图。 （ ） 8．设)(ij a A =是p 个顶点的无向图G 的邻接矩阵，则对于G 的顶点i v , 有∑==p j ij i a v 1deg 成立。 （ ） 9. 设G 是一个),(q p 图，若1-≥p q ，则]/2[)(q p G ≤χ。 （ ） 10．图G 和1G 同构当且仅当G 和1G 的顶点和边分别存在一一对应关系。( ）
二.填空(本题40分，每空各2分) 1．设}},{,{φφ=S 则=S 2 。 2．设B A ,是任意集合，若B B A =\，则A 与B 关系为 。 3．设1)(,0)()(,:};3,2{},1,0{},,,{===→===c f b f a f Y X f Z Y c b a X , 3)1(,2)0(,:==→g g Z Y g ,则)()(c f g a f g ，分别为 。 4．设X 和Y 是集合且X m =，Y n =，若n m ≤，则从X 到Y 的单射的 个数为 。 5．设}2,1{},,,2,1{==B n X ，则从X 到Y 的满射的个数为 。 6．设)}2,4(),1,3(),3,2{()},4,3(),2,2(),2,1{(},4,3,2,1{===S R X ，则 =)(R S R 。 7． 设??? ? ??=???? ??=5123454321,415235432121σσ，则 =21σσ 。 8. 设)},(),,(),,{(},,,,{a c c b b a R d c b a X ==，则 =+R 。 9. 设X 为集合且X n =，则X 上不同的自反或对称的二元关系的个数 为 。 10．设}}{},{},,{{},,,,{d c b a A d c b a X ==是X 的一个划分，则由A 确定的 X 上的等价关系为 。 11．}10,,2,1{ =S ，在偏序关系“整除”下的极大元为 。 12．给出一个初等函数)(x f ，使得它是从)1,0(到实数集合R 的一一对应， 这个函数为 。 13. 设G 是),(p p 连通图，则G 的生成树的个数至多为 。
第六章图的基本概念 P习题 206 1．画出具有4个顶点的所有无向图(同构的只算一个)。 11个 2．画出具有3个顶点的所有有向图(同构的只算一个)。 16个 3．画出具有4个、6个、8个顶点的三次图。 略 4．某次宴会上，许多人互相握手。证明：握过奇数次手的人数为偶数(注意，0是偶数)。 把实际问题转化为图论问题，然后用握手定理的推论。 P习题 209 1．设u与v是图G的两个不同顶点。若u与v间有两条不同的通道(迹)，则G 中是否有圈？ 若u与v间有两条不同的通道，G中无圈 若u与v间有两条不同的迹，G中有圈 2．证明：一个连通的(p，q)图中q≥p-1。 数学归纳法 3．设G是一个（p，q）图，且2/)2 >p - q，则G是连通的。 p )( 1 (- 6．在一个有n个人的宴会上，每个人至少有m个朋友(2≤m≤n)。试证：有不少于m+1个人，使得他们按某种方法坐在一张圆桌旁，每人的左、右均是他的朋友。证明：把实际问题转化为图论问题，就和下面的题一样了。 8．设G是图。证明：若δ(G)≥2，则G包含长至少是δ(G)+1的圈。 这两个题和这个题一样的证明方法。
P习题 216 1．证明：若图G不是连通图，则G c 是连通图。 2．证明：每一个自补图有4n或4n+1个顶点。 P习题 228 1.给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点u和v，均有：degu+degv≥9。 下图中任意一对不邻接的顶点u和v，均有：degu+degv≥9。
2．试求Kp中不同的哈密顿圈的个数。 (p-1)!/2 4．完全偶图Km，n为哈密顿图的充分必要条件是什么？ 10．证明具有奇数顶点的偶图不是哈密顿图。