集合论与图论试卷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 。
14．含5个顶点、3条边的不同构的无向图个数为 4 。
15．设无向图G 有12条边，有6个3度顶点，其余顶点度数均小于3，则G 中
顶点数至少为 9 。
16．由6个顶点，12条边构成的平面连通图G 中，每个面由 3 条边围成。 17．若p K 为平面图，则p 的取值为 4≤ 。
18．包含完全图p K 作为子图的无向图的顶点色数至少为 p 。
19．有向图的可达矩阵)(ij r R =中，若1==ji ij r r ,则顶点i v 与j v 之间是 互达 。
20．高为h 的)2(≥r r 元正则树至多有 h r 片树叶。
三、证明和计算（本题40分，每小题各5分）
1.设,,A B C 是三个任意集合，证明：(\)()\()A B C A B A C ?=??。
证：设 (,)(\)x y A B C ∈?，则x A ∈，\y B C ∈，从而x A ∈,y B ∈,y C ?。
于是(,)x y A B ∈?，(,)x y A C ??,因此(,)()\()x y A B A C ∈??，即
(\)()\()A B C A B A C ????。
反之，设(,)()\()x y A B A C ∈??，有(,)()x y A B ∈?，(,)()x y A C ??，从而
x A ∈，y B ∈，y C ?，故x A ∈且\y B C ∈。于是(,)(\)x y A B C ∈?，
即()\()(\)A B A C A B C ????。
因此，(\)()\()A B C A B A C ?=??。
2.设N n N N g f N ∈?→=,:,},,2,1,0{ ，()(){}1,max 0,1f n n g n n =+=-。证明：
(1)f 是单射而不是满射；(2)g 是满射而不是单射；(3)N g f I = ，但N f g I ≠ ； 证：（1）若()()f n f m = ，则11n m +=+，从而n m =，故f 为单射；但0不存在
原象，故f 不是满射。
(2) n N ?∈，()1,0g n n n +=≥,故g 是满射；但()()01g g =，故g 不是单射。
(3) ()()()(){}{}()max 0,1max 0,N g f x g f x f x x x I x ==-=== ，故N f g I = 。
但()()()
001(0)N f g f g I ==≠ ，故N f g I ≠ 。
3．设R 是A 上的一个自反关系，证明：
R 是等价关系?若(,)a b R ∈且(,)a c R ∈，则(,)b c R ∈。
证：?R 是A 上的等价关系。
若(,)a b R ∈且(,)a c R ∈，由R 的对称性有：(,)b a R ∈且(,)a c R ∈，
由R 的传递性有：(,)b c R ∈。
?R 是自反的，故a A ?∈有(,)a a R ∈。
若(,)a b R ∈，由(,)a a R ∈有(,)b a R ∈，所以R 是对称的。
若(,)a b R ∈且(,)b c R ∈，由R 的对称性有：
(,)b a R ∈且(,)b c R ∈，故由题意得(,)a c R ∈，所以R 是传递。
因此，R 是A 上的等价关系。
4．设G 是一个),(q p 图，证明：G 是树?G 连通且1+=q p 。
证：?因为G 是树，所以G 是连通的；
其次对G 的顶点数p 进行归纳证明p=q+1。
当p 为1或2时，连通图G 中显然有p=q+1。
假设对一切少于p 个顶点的树结论成立；
今设G 是有p 个顶点树，从G 中去掉任一条边x ，则G-x 恰有两个支。由归纳假设，每个支中顶点数与边数之间有关系式：p 1=q 1+1，p 2=q 2+1。
所以，p=p 1+p 2=q 1+q 2+2=(q 1+q 2+1)+1=q+1。
?显然，只须证G 中无回路即可。
设G 中有一个长为n 的回路C n ，则回路上有n 条边，显然n 〈p 。于是，G 中还有p-n
个顶点不在C n 上。由于G 是连通的，所以不在C n 上的那些p-n 个点的每一个均关联一条
边，这些边互不相同，其中每一条都在该点与C n 的某点的最短路上。因此，除了Cn 上的
n 条边之外，G 至少还有p-n 条边。所以，G 至少有q ≥p 条边，这与p=q+1相矛盾，故G 中无回路。
5．设G 是一个),(q p 无向图，证明:（1）若]2
[)(p G ≥δ，则G 是连通的； （2）若G 是连通的，则是否一定有]2
[)(p G ≥δ成立？请说明理由。 证：(1)因为对G 的任一对不邻接顶点u 和v ，有1]2/[]2/[d e g d e g -≥+≥+p p p v u 。
假设G 不连通，则G 至少有两个支。设111(,)G V E =是其中的一个支，其他各支构成的子图为222(,)G V E =，其中，1121||,||,V n V p n ==-，则12,,u V v V ?∈∈，有
11deg 1,deg 1u n v p n ≤-≤--。
于是，11deg deg (1)(1)2u v n p n p +≤-+--=-。
矛盾，所以G 是连通的。
(2) 这个定理是一个充分条件，不是必要条件,即若G 是连通的，则]2
[)(p G ≥δ不一定成立。
例如：6个顶点的一条通路，每个顶点的度2deg ≤v ，不满足3]2
[)(=≥p G δ。 6．证明：每个自补图必有n 4或14+n 个顶点(n 为正整数)。
证：因为每个自补图G 所对应的完全图的边数必为偶数，即(1)/2q p p =-为偶数。而当1,2,3p =时，图G 无自补图，只有4p ≥时，图G 才有自补图。于是p 可写成如下形式：4,41,42,43n n n n +++，其中n 为正整数；代入(1)/2q p p =-中，只有4,41n n +才能使q 为偶数，故每个自补图必有441n n +或个顶点。
7．设T 是一棵树且k T ≥?)(，证明：T 中至少有k 个顶点的度为1。
证：设T 中有p 个顶点，s 个树叶，则T 中其余p s -个顶点的度数均大于等于2，且至少有一个顶点的度大于等于k 。由握手定理可得：
1222()2(1)p
i i q p deg v p s k s ==-=≥--++∑，有s k ≥。
所以T 中至少有k 个树叶 。
8．证明：一个没有有向回路（圈）的有向图中至少有一个入度为零的顶点。 证：设D=(V,A)是一个没有有向回路的有向图。考察D 中任一条最长的有向路的第一个顶点v ，则id(v)=0。因为若id(v)≠0，则必有一个顶点u 使得(u,v)∈A 。于是，
若u 不在此最长路上，则此最长路便不是D 中的最长路，这是与前面的假设相矛盾。 若u 在此最长路上，则D 中有有向回路，这与定理的假设矛盾。因此id(v)=0。
集合论与图论 试题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) 二路和连通性 (4) 第二章树 (4) 第三章图的连通度 (6) 第四章欧拉图与哈密尔顿图 (8) 一，欧拉图 (8) 二．哈密尔顿图 (10) 第五章匹配与因子分解 (14) 一．匹配 (14) 二．偶图的覆盖于匹配 (15) 三．因子分解 (16) 第六章平面图 (20) 二．对偶图 (24) 三．平面图的判定 (25) 四．平面性算法 (28) 第七章图的着色 (34) 一．边着色 (34) 二．顶点着色 (35)
第九章 有向图 (40) 二 有向树 (41) 第一章 图的基本概念 1. 点集与边集均为有限集合的图称为有限图。 2. 只有一个顶点而无边的图称为平凡图。 3. 边集为空的图称为空图。 4. 既没有环也没有重边的图称为简单图。 5. 其他所有的图都称为复合图。 6. 具有二分类（X, Y ）的偶图（或二部图）：是指该图的点集可以分解为两个（非空）子 集 X 和 Y ，使得每条边的一个端点在 X 中，另一个端点在Y 中。 7. 完全偶图：是指具有二分类（X, Y ）的简单偶图，其中 X 的每个顶点与 Y 的每个顶点 相连，若 |X|=m ，|Y|=n ，则这样的偶图记为 Km,n 8. 定理1 若n 阶图G 是自补的（即 ），则 n = 0, 1（mod 4） 9. 图G 的顶点的最小度。 10. 图G 的顶点的最大度。 11. k-正则图: 每个点的度均为 k 的简单图。 例如,完全图和完全偶图Kn,n 均是正则图。 12. 推论1 任意图中，奇点的个数为偶数。 ()G δ()G ?
13. 14.频序列：定理4 一个简单图G的n个点的度数不能互不相同。 15.定理5 一个n阶图G相和它的补图有相同的频序列。 16. 17. 18.对称差：G1△G2 = (G1∪G2) - (G1∩G2) = (G1-G2)∪(G2-G1) 19.定义：联图在不相交的G1和G2的并图G1+G2中，把G1的每个顶点和G2的每个 顶点连接起来所得到的图称为G1和G2的联图，记为G1∨G2 20.积图：积图设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1×V2中的任意两个点u = (u1,u2)和v = (v1,v2)，当(u1 = v1和u2 adj v2) 或(u2 = v2 和u1 adj v1) 时就把u 和v 连接起来所得到的图G称为G1和G2积图。记为G = G1×G2 设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1×V2中的任意两个点u = (u1,u2)和v = (v1,v2)，当(u1 adj v1) 或(u1= v1 和u2 adj v2) 时就把u 和v 连接起来所得到的图G称为G1和G2的合成图。记为G=G1[G2]。
集合论与图论试卷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 。
图论与组合数学期末复习题含答案
组合数学部分 第1章 排列与组合 例1： 1)、求小于10000的含1的正整数的个数； 2、)求小于10000的含0的正整数的个数； 解：1)、小于10000的不含1的正整数可看做4位数,但0000除外.故有9×9×9×9－1＝6560个.含1的有：9999－6560=3439个 2)、“含0”和“含1”不可直接套用。0019含1但不含0。在组合的习题中有许多类似的隐含的规定，要特别留神。不含0的1位数有19个，2位数有29个，3位数有39个，4位数有49个 不含0小于10000的正整数有() ()73801919999954321=--=+++个含0小于10000的正整数9999－7380=2619个。 例2： 从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种方案？ 解：将[1,300]分成3类： A={i|i ≡1(mod 3)}={1,4,7,…,298}, B={i|i ≡2(mod 3)}={2,5,8,…,299}, C={i|i ≡0(mod 3)}={3,6,9,…,300}. 要满足条件，有四种解法： 1)、3个数同属于A; 2)、3个数同属于B ； 3)、3个数同属于C; 4)、A,B,C 各取一数；故共有3C(100,3)+1003=485100+1000000=1485100。 例3：（Cayley 定理：过n 个有标志顶点的数的数目等于2-n n ） 1）、写出右图所对应的序列； 2）、写出序列22314所对应的序列； 解： 1）、按照叶子节点从小到大的顺序依次去掉节点（包含与此叶子 节点相连接的线），而与这个去掉的叶子节点相邻的另外一个点值则记入序列。如上图所示，先去掉最小的叶子节点②，与其相邻的点为⑤，然后去掉叶子节点③，与其相邻的点为①，直到只剩下两个节点相邻为止，则最终序列为51155.。 2）、首先依据给定序列写出（序列长度+2）个递增序列，即1234567，再将给出序列按从小到大顺序依次排列并插入递增序列得到：7。我们再将给出序列22314写在第一行，插入后的递增序列写在第二行。如下图第一行所示： ??→????? ??--②⑤67112223344522314??→???? ? ??--②⑥11223344672314 ??→????? ??--③②11233447314??→???? ? ??--①③11344714
集合论与图论
集合论与图论习题册 软件基础教研室 刘峰 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 ）教会学生如何进行逻辑推理，如何进行正确地思维，如何在纷繁的事物中抓住主要的联
电子科技大学2017年图论期末试卷
1 2017年图论课程练习题 一．填空题 1.图1中顶点a 到顶点b 的距离d (a ,b )= 。 a b 9 图1 1 2.已知图G 的邻接矩阵0 11011 01001 1010001011001 0A = ，则G 中长度为2的途径总条数为 。 3.图2中最小生成树T 的权值W (T )= 。 4.图3的最优欧拉环游的权值为 。 12 图 2
2 图3 5.树叶带权分别为1,2,4,5,6,8的最优二元树权值为 。 二．单项选择 1．关于图的度序列，下列说法正确的是( ) (A) 对任意一个非负整数序列来说，它都是某图的度序列； (B) 若非负整数序列12(,,,)n d d d π= 满足1n i i d =∑为偶数，则它一定是图序 列； (C) 若图G 度弱于图H ，则图G 的边数小于等于图H 的边数； (D) 如果图G 的顶点总度数大于或等于图H 的顶点总度数，则图G 度优 于图H 。 2．关于图的割点与割边，下列说法正确的是（ ） (A) 有割边的图一定有割点； (B) 有割点的图一定有割边； (C) 有割边的简单图一定有割点； (D) 割边不在图的任一圈中。 3.设()k G ，()G λ，()G δ分别表示图G 的点连通度，边连通度和最小度。下面说法错误的是( )
3 (A) 存在图G ，使得()k G =()G δ=()G λ； (B) 存在图G ，使得()()()k G G G λδ<<； (C) 设G 是n 阶简单图，若()2n G δ ≥ ，则G 连通，且()()G G λδ=； (D) 图G 是k 连通的，则G 的连通度为k 。 4.关于哈密尔顿图，下列命题错误的是( ) (A) 彼得森图是非哈密尔顿图； (B) 若图G 的闭包是哈密尔顿图，则其闭包一定是完全图； (C) 若图G 的阶数至少为3且闭包是完全图，则图G 是哈密尔顿图； (D) 设G 是三阶以上简单图，若G 中任意两个不邻接点u 与v ，满足 ()()d u d v n +≥，则G 是哈密尔顿图。 5.下列说法错误的是( ) (A) 有完美匹配的三正则图一定没有割边； (B) 没有割边的三正则图一定存在完美匹配； (C) 任意一个具有哈密尔顿圈的三正则图可以1因子分解； (D) 完全图21n K +是n 个哈密尔顿圈的和。 三、 设无向图G 有10条边，3度与4度顶点各2个，其余顶点度数均小于3，问G 中至少有几个顶点？在最少顶点数的情况下，写出G 的度序列，该度序列是一个图序列吗？。
集合论图论 期中考试试题及答案
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是对称关系. ?
2015电子科技大学_图论期末考试复习题
2015电子科技大学 图论考试复习题 关于图论中的图，以下叙述不正确的是 A ．图中点表示研究对象，边或有向边表示研究对象之间的特定关系。 B ．图论中的图，画边时长短曲直无所谓。 C ．图中的边表示研究对象，点表示研究对象之间的特定关系。 D ．图论中的图，可以改变点与点的相互位置，只要不改变点与点的连接关系。 一个图中最长的边一定不包含在最优生成树内。 下面哪个图形不与完全二分图K 3,3同构？ A ． B ． C ． D ． 有10条边的5顶单图必与K 5同构。 完全二分图K m ,n 的边数是 A ．m B ．n C ．m +n D ．mn 无向完全图K n 的边数为 A ．n B ．n 2 C ．n (n -1) D ．n (n -1)/2 若一个无向图有5个顶点，如果它的补图是连通图，那么这个无向图最多有 条边。 对于两个图，如果顶点数目相等，边数相等，次数相等的顶点数目也相等，则这两个图同构。 有15个顶的单图的边数最多是 A ．105 B ．210 C ．21 D ．45 图G 如右，则dacbeb A ．是G 中的一条道路 B ．是G 中的一条道路但不是行迹 C ．是G 中的一条行迹但不是轨道 D ．不是G 的一条道路 图G 如右，则befcdef A ．是G 的一个圈 B ．是G 的一条道路但不是行迹 C ．是G 的一条行迹但不是轨道 D ．是G 的一条轨道但不是圈
v1 36 7 图G如右图所示，则ω (G)= A．1 B．2 C．7 D．8 下列图形中与其补图同构的是 A．B．C．D． 求下图中顶u0到其余各顶点的最短轨长度。 u0v1=8，u0v2=1，u0v3=4，u0v4=2，u0v5=7，v1v2=7，v1v3=2，v1v6=4，v2v4=2，v2v7=3，v3v5=3，v3v6=6，v4v5=5，v4v7=1， v5v 6 =4，v 5 v7=3，v6v7=6， 请画出6阶3正则图。 请画出4个顶，3条边的所有非同构的无向简单图。 设图G={V(G)，E(G)}其中V ={ a1, a2, a3, a4, a5}，E(G)={(a1, a2)，(a2, a4)，(a3, a1)，(a4, a5)，(a5, a2)}，试给出G的图形表示并画出其补图的图形。 一个图的生成子图必是唯一的。 不同构的有2条边，4个顶的无向简单图的个数为 A．1 B．2 C．3 D．4 画出5个具有5个结点5条边的非同构的无向连通简单图。 u0到v1的最短轨长度为6，u0到v2的最短轨长度为1，u0 到v3的最短轨长度为4，u0到v4的最短轨长度为2，u0到v5的最短轨长度为6 ，u0到v6的最短轨长度为9，u0到v7的最短轨长度为3。
集合论与图论复习题
集合论图论复习题 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 也是连通图。
- 《集合论与图论》期中考试
- 集合论与图论
- 黑龙江省哈工大2006年秋季学期《集合论与图论》试题及参考答案
- 集合论与图论
- 离散数学教程(集合论与图论)-FudanUniversity
- 集合论与图论 第二章习题
- 集合论,图论总结
- 哈工大年集合论与图论试卷
- 答案08秋季集合论与图论试题A
- 集合论与图论(全套课件)
- 《集合论与图论》课堂练习1
- 北大集合论与图论往年考题.pdf
- 集合论与图论试题与参考答案哈工大本科
- 北大集合论与图论3
- 哈工大集合论与图论第六章作业题答案
- 集合论与图论试题与参考答案 哈工大本科
- 离散数学 集合证明讲解学习
- 《集合论与图论》课堂理解理解练习2
- 集合论与图论第二章
- 《集合论与图论》课程教学大纲