集合论与图论
集合论与图论习题册
软件基础教研室
刘峰
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 = 。（答案：都不正确）
16．下列命题哪个为真？ 答案：_________ a)对任何集合A,B,C ，若A B B C = ，则A=C 。 b)设A,B,C 为任何集合，若A B A C = ，则B=C 。
c)对任何集合A,B ，222A B A B = 。 d)对任何集合A,B ，222A B A B = 。 e)对任何集合A,B ，\22\2A B A B =。 f)对任何集合A,B ，222A B A B ?=?。 17．填空：设A,B 是两个集合。
a)x A B ∈? ________________； b)x A B ∈? _________________ c)\x A B ∈?_________________； d)x A B ∈??_________________。 18．设A ，B ，C 为三个集合，下列集合表达式哪一个等于\()A B C ？答案：____
（a ）(\)(\)A B A C ；（b ）()\()A B A C ；
（c ）(\)(\)A B A C ；（d ）()\()A B A C ；（e ）()()A B A C 。
20P 习题
20．设A,B,C 为集合，并且A B A C = ，则下列断言哪个成立？
(1)B C =；(2)A B A C = ；(3)C C A B A C = ；(4)C C A B A C = 。 答案：
21．设A,B,C 为任意集合，化简
()()()()()()()C C C C
C
C
C
C
C
A B C A B C A B C A B C A B C A B C A B C
25P 习题
24．设{,,},{,,,},{,,}A a b c B e f g h C x y z ===。求2,,,A B B A A C A B ????。
25．设A,B 为集合，试证：A×B＝B×A 的充要条件是下列三个条件至少一个成立：（1）A φ=；（2）B φ=；（3）A B =。
26．设A,B,C,D 为任四个集合，证明：()()()()A B C D A C B D ?=??
29．设,,A B C 是三个任意集合，证明：()()()A B C A B A C ??=???。
30．设A,B 为集合，下列命题哪些为真？
（1）(,)x y A B x A ∈??∈且y B ∈； （2）(,)x y A B x A ∈??∈或y B ∈； （3）222A B A B ?=?； （4）若A C B C ?=?，则A B =； （5）若,A C B C C ?=?≠?，则A B =。 答案：______ 31．设A 有m 个元素，B 有n 个元素，则A×B 是多少个序对组成的？A×B 有多
少个不同的子集？ 答案：_______ 32．设,A B 是两个集合，B ≠?，试证：若B B B A ?=?，则A B =。
33P 习题
33．设A,B 是两个有限集，试求22
?A B
?=
34.某班学生中有45％正在学德文，65％正在学法文。问此班中至少有百分之几
的学生正同时学德文和法文？
第二章 映射习题
39P 习题
1. 设A ，B 是有穷集，,A m B n ==。则
（1）计算B A ； （2）从A 到A 有多少个双射？
43P 习题
3. 证明：从一个边长为1的等边三角形中任意选5个点，那么这5个点中必有2个点，它们之间的距离至多为1/2，而任意10个点中必有2个点其距离至多是1/3。
5. 证明在52个整数中，必有两个整数，使这两个整数之和或差能被100整除。
6.设12,,,n a a a 为1,2,3,,n 的任一排列，若
n
是奇数且
12(1)(2)()0n a a a n ---≠ ，则乘积为偶数。
46P 习题
7.设:f X Y →，,C D Y ?，证明111(\)()\()f C D f C f D ---=
8. 设:f X Y →，X B A ?,，，证明)(\)()\(B f A f B A f ?。
10.设:,,f X Y A X B Y →??。以下四个小题中，每个小题均有四个命题，这四个命题有且仅有一个正确，请找出正确的那个。
（1）（a ）若()()f x f A ∈，则x 未必在A 中；（b ）若()()f x f A ∈，则x A ∈；
（c ）若()()f x f A ∈，则x A ∈； （d ）若()()f x f A ∈，则c x A ∈。 （2）（a ）1(())f f B B -=； （b ）1(())f f B B -?；
（c ）1(())f f B B -?； （d ）1(())c f f B B -=。 （3）（a ）1(())f f A A -=； （b ）1(())f f A A -?；
（c ）1(())f f A A -?； （d ）上面三个均不对。 （4）（a ）()f A ≠?； （b ）()f B ≠?；
（c ）若1,()y Y f y x -∈∈则； （d ）若1,()y Y f y x -∈?则。
50P 习题
15. 设{,,},{0,1},{2,3},:,()()0X a b c Y Z f X Y f a f b ===→==，
()1;:f c g Y =→Z ，(0)2,(1)3g g ==，试求g f 。
55P 习题
17．设{1,2,3,}N = ，试构造两个映射f 和g ：N N →，使得
（1）N fg I =，但N gf I ≠；（2）N gf I =，但N fg I ≠。
18.设:f X Y →则
（1）若存在唯一的一个映射:g Y X →，使得X gf I =，则f 是可逆的吗？ （2）若存在唯一的一个映射:g Y X →，使得Y fg I =，则f 是可逆的吗？
20. 是否有一个从X 到X 的一一对应f ，使得1f f -=，但X f I ≠？
63P 习题
21.设1212345123454321532514σσ????= ? ?????，＝，求11
122112,,,σσσσσσ--。
22.将置换123456789791652348??
???分解成对换的乘积。
第三章 关系习题
86P 习题
1.给出一个既不是自反的又不是反自反的二元关系？
2.是否存在一个同时不满足自反性，对称性，反对称性，传递性和反自反性的 二元关系？
3.设R ，S 是X 上的二元关系，下列命题哪些成立：
a)若R 与S 是自反的，则,R S R S 分别也是自反的； b) 若R 与S 是对称的，则,R S R S 分别对称的； c) 若R 与S 是传递的，则R S 也是传递的；
d) 若R 与S 不是自反的，则R S 也不是自反的；
e) 若R 与S 是反自反的，则,R S R S 也是反自反的； f) 若R 是自反的，则c R 也是反自反的； g) 若R 与S 是传递的，则R\S 是传递的。
答案：________________________________________________
4.实数集合上的“小于”关系<是否是反自反的？集合X 的幂集上的“真包含”关系?是否是反自反的？为什么？
5.设R 、S 是X 上的二元关系。证明：
（1）11()R R --=； （2）111()R S R S ---= ； （3）111()R S R S ---= ； （4）若R S ?，则11R S --?；
6．设R 是X 上的二元关系，证明：1R R - 是对称的二元关系。
7．设R 为X 上的是反自反的和传递的二元关系,证明：R 是反对称的。
92P 习题
9.“父子“关系的平方是什么关系？ 答案：_____________
11.设R 与S 为X 上的任两个二元关系，下列命题哪些为真？ 答案：_______
a ）若R,S 都是自反的，则R S 也是自反的；
b ）若R,S 都是对称的，则R S 也是对称的；
c ）若R,S 都是反自反的，则R S 也是反自反的；
d ）若R,S 都是反对称的，则R S 也是反对称的；
e ）若R,S 都是传递的，则R S 也是传递的。
12．设R 1是A 到B ，R 2和R 3是B 到C 的二元关系，则一般情况下：
1231213(\)()\()R R R R R R R ≠ 。
但有人声称等号成立，他的证明如下：设123(,)(\)a c R R R ∈ ，则b X ?∈，使得1(,)a b R ∈且23(,)\b c R R ∈。于是2(,)b c R ∈且3(,)b c R ∈。从而12(,)a c R R ∈ 且
13(,)b c R R ? ，所以1213(,)()\()a c R R R R ∈ ，即1231213(\)()\()R R R R R R R ? 。同理可证相反的包含关系成立，故等式成立，这个证明错在什么地方？
13.设R ，S 是X 上的满足R S S R ? 的对称关系，证明R S S R = 。
113P 习题
25.设{1,2,3},{1,2},{|:}X Y S f f X Y ===→。?是S 上的二元关系：
)()(,,g I f I g f S g f m m =??∈?。
证明：（1）?是S 上的等价关系；（2）求等价类的集合。
26. 设{1,2,3},{1,2},{|:}X Y S f f X Y ===→。?是S 上的二元关系：
)3()2()1()3()2()1(,,g g g f f f g f S g f ++=++??∈?。
证明：（1）?是S 上的等价关系；（2）求等价类数。
27. 设{1,2,3},{1,2},{|:}X Y S f f X Y ===→。?是S 上的二元关系：
}|)({}|)({,,11Y y y g Y y y f g f S g f ∈=∈??∈?--。
证明：（1）?是S 上的等价关系；（2）求等价类。
28.由置换
12345678
36581274
σ
??
= ?
??
确定了{1,2,,8}
X= 上的一个关系
:,,
i j X i j
?∈?当且仅当i与j在σ的循环分解式中的同一循环置换中，证明：?是X上的等价关系，求/
X?。
29．给出X＝{1,2,3,4}上两个等价关系R与S，使得R S 不是等价关系。30．设R是X上的一个自反关系，证明：R是等价关系?若(,)
a b R
∈且(,)
a c R
∈，则(,)
b c R
∈。
35．设X是一个集合，X n
=，试求：
（1）X上自反二元关系的个数；（2）X上反自反二元关系的个数；
（3）X上对称二元关系的个数；（4）X上自反或对称关系的个数。
125
P习题
38.存在一个偏序关系≤，使得(,)
X≤中有唯一的极大元素，但没有最大元素？若有请给出一个具体例子；若没有，请证明之。
39．令S＝｛1，2，…，12｝，画出偏序集（S,|）的Hass图，
其中“|”是整除关系，它有几个极大（小）元素？列出这些
极大（小）元素。
第四章 无穷集合及其基数习题
1. 设A 为由序列12,,,,n a a a
的所有项组成的集合，则A 是否是可数的？为什么？
2.证明：直线上互不相交的开区间的全体所构成的集合至多可数。
3.证明：单调函数的不连续点的集合至多可数。
4.任一可数集A 的所有有限子集构成的集族是可数集合。
5．判断下列命题之真伪：
(1)若:f X Y →且f 是满射，则只要X 是可数的，那么Y 是至多可数的； (2)若:f X Y →且f 是单射，那么只要Y 是可数的，则X 也是可数的； (3)可数集在任一映射下的像也是可数的；
7. 设∑为一个有限字母表，∑上所有字（包括空字）之集记为*∑。证明*∑是 可数集
P习题
142
1.找一个初等可数()
f x，使得它是(0,1)到实数R的一一对应。
4. 利用康托的对角线法证明2A是不可数集，其中A为可数集。5．利用康托的对角线法证明所有的0，1的无穷序列是不可数集。
第六章图的基本概念
P习题
206
1．画出具有4个顶点的所有无向图(同构的只算一个)。
2．画出具有3个顶点的所有有向图(同构的只算一个)。
3．画出具有4个、6个、8个顶点的三次图。
4．某次宴会上，许多人互相握手。证明：握过奇数次手的人数为偶数(注意，0是偶数)。
P习题
209
1．设u与v是图G的两个不同顶点。若u与v间有两条不同的通道(迹)，则G 中是否有圈？
2．证明：一个连通的(p，q)图中q≥p-1。
3．设G是一个（p，q）图，且2/)2
p
>p
q，则G是连通的。
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。
2．试求Kp中不同的哈密顿圈的个数。
4．完全偶图Km，n为哈密顿图的充分必要条件是什么？
10．证明具有奇数顶点的偶图不是哈密顿图。
第七章树和割集
243
P习题
1．分别画出具有4、5、6个顶点的所有树(同构的只算一个)。
2．证明：每个非平凡树是偶图。
3．设G是一棵树且Δ(G)≥k，证明：G中至少有k个度为1的顶点。
4．令G是一个有p个顶点，k个支的森林，证明：G有p-k条边。
6．设树T中有2n个度为1的顶点，有3n个度为2的顶点，有n个度为3的顶点，则这棵树有多少个顶点和多少条边？
7一棵树T有n
2个度为2的顶点，n
3
个度为3的顶点，…，n
k
个度为k的顶点，
则T有多少个度为1的顶点？
257
P习题
1. P个顶点的图中，最多有多少个割点？
3．证明：有一座桥的三次图中至少有10个顶点。
4.设v是图G的一个割点，证明v不是G的补图G c的割点。
7.有割点的连通图是否一定不是欧拉图？是否一定不是哈密顿图？有桥的连通图是否一定不是欧拉图和哈密顿图。
第八章 连通度和匹配
264P 习题
1. 设G 是一个有p 个顶点的图，()(1)/2G p k δ≥+-2p ≥。试证：G 是k -连通的，
其中k p <。
6. G 是一个三次正则图，试证：k (G ) = λ(G )。
7. 设r ≥2, G 是r -正则图且k (G )=1。试证：λ(G )≤[2
r
]。
第九章 平面图和图的着色
281P 习题
1.设(,)G p q =是一个具有f 个面，k 个分支的平面图，则1p q f k -+=+。
2. 若G是顶点数p≥11的平面图，试证G c不是平面图。
4．证明：不存在7条棱的凸多面体。
P习题
294
1.设G是一个没有三角形的平面图。应用欧拉公式证明G中有一个顶点v，使得degv ≤3。
2.设G是一个没有三角形的平面图。应用数学归纳法证明G是4－可着色的。
第十章有向图
P习题
301
2.画出具有三个顶点的所有互不同构的有向图的图解。
3.具有p个顶点的完全有向图中有多少条弧？
P习题
307
1.设D是一个有p个顶点q条弧的有向图。若D是连通的，证明：p-1≤q≤p(p-1)。
2.设D是一个有p个顶点q条弧的强连通的有向图，则q至少是多大？
P习题
307
2.有向图D的图解如图10.4.3所示
(1)写出D的邻接矩阵及可达矩阵；(2)写出D关联矩阵。
3.设D为图10.
4.4中的有向图，试求v
到其余每个顶点的长≤4的所有通道的
2
条数。
P习题
321
1.设T是一个正则m元有序树，它有n
个叶子，T有多有多少条弧？
集合论与图论 试题A
本试卷满分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 。
北大集合论与图论往年考题.pdf
一、用真值表证明德*摩根律（证明其中一条即可）。 二、设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
集合论与图论试卷2
哈工大 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
《集合论与图论》课堂练习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)。
集合论与图论SG2017-期中试题-答案(1)
一、（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= ； ⑷ 设
《集合论与图论》课堂练习2
《集合论与图论》课堂练习3 （2013年12月18日 13:20-15:00 复旦大学计算机学院2012级） 学号姓名 一、判断下列命题是否正确，并说明理由。（括号内写“是”或“否”）（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不是最长路。矛盾。
集合论与图论期中考试
《集合论与图论》期中考试 （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 也是连通图。
答案08秋季集合论与图论试题A
哈工大 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
集合论与图论答案 第四章习题
第四章 无穷集合及其基数习题 136P 1.设A 为由序列 12,,,,n a a a 的所有项组成的集合，则是否市可数的？为什么？ 解：因为序列是可以重复的，故 若A 是由有限个数组成的集合，则A 是有限的集合； 若A 是由无限个数组成的集合，则A 是可数的。 故本题A 是至多可数的。 2.证明：直线上互不相交的开区间的全体所构成的集合至多可数。 证：在每个开区间中取一个有理数，则这些有理数构成的集合是整个有理数集合Q 的子集，因此是至多可数的。 3.证明：单调函数的不连续点的集合至多可数。 证：设A 是所有不连续点的集合，f 是一个单调函数，则00,x A x ?∈对应着一个区间0((0),(0))f x f x -+，于是由上题便得到证明。 4.任一可数集A 的所有有限子集构成的集族是可数集合。 证：设1212{,,,,},{,,,},n i i ik A a a a B a a a ==则B A ?且B k =<∞。 令{,}B B A B B =?<∞， 设:{0,1}A ?→，则?是Ａ的子集的特征函数。 ,()B B ??∈B =｛0，1的有穷序列｝ ，即i a A ?∈， 若i a B ∈，则对应1；若i a B ?则对应0。于是 ,()B B ??∈B 就对应着一个由0，1组成的有限序列0，1，1，0，…，0，1。此序列对应着一个二进制小数，而此小数是有理数。于是，可数集A 的所有有限子集B 对应着有理数的一个子集。 又121212,,,,B B B B B B ?∈B ≠对应的小数也不同，故?是单射。而可数集Ａ的所有有限子集B 是无穷的，故B 是可数的。
北京大学集合论与图论SG2017-期末考试题试题-final-答案
北京大学信息科学技术学院期末试卷考试科目：集合论与图论姓名：学号： 考试时间：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。
集合论与图论(下)教学大纲
集合论与图论（下）教学大纲 《集合论与图论》是计算机大类/软件工程大类专业的一门专业基础课。本课程为后继的专业基础课及专业课提供必要的数学工具，为描述离散模型提供数学语言。该课程的设置主要是为了培养学生的抽象思维和逻辑推理能力，提高学生提出问题、分析问题和解决问题的能力，提高学生的数学修养及计算机科学素质。 课程概述 要想用计算机解决问题就要为它建立数学模型，即描述研究对象及对象与对象之间的联系，并通过事物之间的联系找出事物的运动规律。集合论与图论为此提供了强有力的描述工具与推理理论。 本课程的目标是通过理论学习，使学生正确地理解概念，正确地使用概念进行推理，养成一个好的思维习惯，理解理论与实践的关系。引导学生观察生活、社会和大自然，分析事物间的联系，建立系统的模型，提出和解决其中的复杂工程问题。 本课程主要包含二部分内容：集合论与图论。集合论是整个数学的基础，也是计算机科学的基础，计算机科学领域中的大多数基本概念和理论，几乎均采用集合论的有关术语来描述和论证，而图论的基本知识则将始终陪伴着每一个计算机工作者的职业生涯。 计算学科以抽象、理论、设计为其学科形态，以数学方法和系统方法为其学科方法，本课程的核心目标就是在抽象和理论的基础上提供数学方法，因此，本课程是整个专业的基础课程，是计算机专业最重要的课程之一。 《集合论与图论》（上）主要讲述集合论部分，《集合论与图论》（下）主要讲述图论部分。 授课目标 课程具体目标如下： 课程目标1：掌握集合论与图论的基本概念、基本原理、基本方法等基本知识，培养形式化、模型化的抽象思维能力，使学生能够利用集合论与图论的概念、理论与方法识别、表达计算相关的复杂工程问题，逐步学会为计算类复杂工程问题建立数学模型；
集合论与图论试卷4
哈工大 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 的生成树的个数至多为 。
- 《集合论与图论》课堂练习3
- 集合论与图论试题与参考答案哈工大本科
- 北大集合论与图论3
- 集合论与图论试题与参考答案 哈工大本科
- 集合论与图论(全套课件)
- 北大集合论与图论PPT精选文档
- 集合论与图论
- 哈工大年集合论与图论试卷
- 集合论与图论期中考试
- 北大集合论与图论
- 集合论与图论试题与参考答案 哈工大本科
- 北大集合论与图论往年考题.pdf
- 复旦大学《集合论与图论》课堂练习1(2017年11月6日)(参考答案)
- 集合论与图论习题册
- 集合论与图论第九章
- 《集合论与图论》课程教学大纲
- 集合论与图论习题册
- 《集合论与图论》课堂理解理解练习2
- 集合论与图论参考答案
- 离散数学教程(集合论与图论)-FudanUniversity