例：
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；
f5是双射(单射,满射)；f6不是单射,不是满射。
7、证明：在52个正整数中，必有两个整数，使得这两个整数之和或差能被100整除。
8、已知m个整数a1，a2，…，am，试证：存在两个整数k,l,0≤k 9、设N={1,2,3,…},试构造两个映射f,g:N→N，使得fg=IN，但gf≠IN。 10、设N={1,2,3,…},试构造两个映射f,g:N→N，使得gf=IN，但fg≠IN。 11、设f:X→Y，证明： (1)f是单射??F∈2X，f–1(f(F))=F； (2)f是满射??E∈2Y，f(f–1(E))=E。 12、设f:X→Y，则 (1)若存在唯一的一个映射g:Y→X,使得gf=IX,则f是可逆的吗？ (2)若存在唯一的一个映射g:Y→X,使得fg=IY,则f是可逆的吗？ 13、(1)设X={1,2,3},Y={a,b},求X到Y满射的个数; (2)设X={1,2,3,4,5},Y={a,b},求X到Y的满射的个数; (3)设X={1,2,…,n},Y={a,b}，求X到Y的满射的个数; (4)设X={1,2,…,n},Y={y1,y2,…,ym},n≥m,若f:X→Y，求X到Y的满射的个数。 14、设X是一个集合，|X|＝n，求： (7) X上既不是自反的也不是反自反的关系有多少？ (9) X上自反的或对称的关系有多少？ (12)X上既不是对称的也不是反对称的关系有多少？ 15、设A={1,2,3}，R是A的幂集2A上的二元关系且R={(a,b)|a∩b≠￠}，则R不满足下列哪些性质？为什么？[aRb ?a∩b≠￠] (1) 自反性(2) 反自反性(3) 对称性 (4) 反对称性(5) 传递性 16、设R是复数集合C上的一个二元关系且满足 xRy?x-y=a+bi，a,b为非负整数，试确定R的性质。 17、设R为X上的二元关系，显然若R＝￠，则R是反自反的、对称和传递的；但若R≠￠且R是反自反的和对称的，则R不是传递的。 此题可变形为：但若R≠￠且R是反自反的和传递的,则R是反对称的。 18、设R是集合A上的反对称关系，则t(R)一定是反对称的吗？ 19、设R是集合A上的一个自反的和传递的关系； T是A上的一个关系，使得(a,b)∈T?(a,b)∈R且(b,a)∈R。证明：T是A上的等价关系。 20、设R是A上的二元关系，S={(a,b)|?c∈A,使得(a,c)∈R且(c,b)∈R}。证明：若R是等价关系，则S也是等价关系。 说明：本题可以证明R＝S。 21、设{A1,A2,…,An}是集合A的划分，若Ai∩B≠φ，1≤i≤n，证明：{A1∩B,A2∩B,…,An∩B}是集合A∩B的划分。 22、设S={1,2,3,4},并设A＝S×S,在A上定义关系R为: (a,b)R(c,d) a+b=c+d。 证明:(1) R是A上的等价关系；(2) 计算A/R。 23、设集合A={a,b,c,d,e}上关系R定义如下： R={(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c),(b,e), (c,c),(c,e),(d,d),(d,e),(e,e)}。 1.写出R的关系矩阵； 2.验证(A,R)是偏序集; 3.画出Hasse图; 4.若A上的关系如下： R={(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c),(b,e), (c,c), (c,d),(c,e),(d,d),(d,e),(e,e)}，则有如何？ 24、用对角线方法证明：若A是可数集，则2A是不可数集。 25、用对角线方法证明：所有0,1的无穷序列所构成的集合是不可数集。 26、设T是一棵树,T有3个度为3顶点,1个2度顶点，其余均是1度顶点。则（1）求T有几个1度顶点？ （2）画出满足上述要求的不同构的两棵树。 27、设T是一棵树且△(T)≥k，证明T中至少有k个度为1顶点。 28、设G是一棵树且Δ(G)≥k，证明：G中至少有k个度为1的顶点。 29、一棵树T有n2个度为2的顶点，n3个度为3的顶点，…，nk个度为k的顶点，则T有多少个度为1的顶点？ 30、如图所示是彼德森图，回答问题： （1）图是否是自补图？（2）图是否是偶图？ （3）图是否是欧拉图？（4）图是否是哈密顿图？ （5）图是否是平面图？（6）图的色数是多少？ 31、证明：若每个顶点的度数大于等于3时，则不存在有7条边的平面连通图。 (等价命题：证明：不存在7条棱的凸多面体) 32、设G是顶点p≥11的平面图，证明：G的补图Gc是非平面图。 (设G是顶点p≥11的图，证明：G与G的补图Gc至少有一个是非平面图。) 33、设G是边数q<30的平面图,证明:G中存在顶点v，使得degv≤4。 34、设G是(p,q)平面连通图，f个面，证明： （1）若p≥3，则f≤2p-4； （2）若δ(G)=4，则G中至少有6个顶点的度数 小于等于5。 证: (1) p-q+f=2,q≤3p-6,从而有:f≤2p-4。 (2) 假设G中至多含有5个顶点的度数≤5，又δ(G)=4,所以5×4+6×(p-5)≤2q ，得q≥3p-5。 而q≤3p-6，从而有：3p-5≤3p-6，矛盾。 故假设不成立，因此G中至少有6个顶点的度数≤5 35、把平面分成n个区域，每两个区域都相邻,问n最大为多少？ 证：在每个区域放一个顶点，当两区域相邻时，就在相邻的两个顶点间连一条边，如此构造了一个平面图且是完全平面图，而最大的完全平面图为K４，所以n最大为4。 36、证明:当每个顶点的度数大于等于3时，不存在有7条边的简单连通平面图。 证：设G=(n，m)为简单连通平面图，有r个面。若m=7，由欧拉公式知n+r=m+2=9 (1) 而每个面至少由3条边围成，有3r≤2m，则r≤2m/3，因r是整数,故r≤４。 又对任意得顶点v∈V，degv≥3，有3n≤2m，故n≤2m/3，因为n是整数，故n≤４。所以n+r≤４＋４=８与（１）矛盾，所以结论正确。 37、设G是一个没有三角形的平面图，则 （1）证明：G中存在一个顶点v，使得degv≤3； （2）证明：G是4-可着色的。 38、设树T中有2n个度为1的顶点,有3n个度为2的顶点,有n个度为3的顶点,则这棵树T有几个顶点和几条边？ 39、设T是一棵树且△(T)≥k,证明:T中至少有k个度为1的顶点。 40、设G是一个(p,q)图, 若q≥p,证明G中必有圈。 41、证明:任一非平凡树最长路的两个端点都是树叶。(任一非平凡树中至少有两个度为1的顶点。) 42、证明:恰有两个顶点度数为1的树必为一条通路。 43、设T=(V,A)是一个有根树,其每个顶点的出度不是0就是2。若T有n0个叶子，试求T的弧的条数。 44、设T=(V,A)是一个正则二元树,若T有n0个叶子，试求的弧的条数。 45、设T是有n0个叶子的正则二元树，n2个出度为2的顶点，证明：n0=n2+1。 46、设T是有n0个叶子的二元树，出度为2的顶点为n2，证明：n0=n2+1。 47、设T是一个有p个顶点的正则二元树，求T的叶子数，其中p奇数。 48、证明：任一棵正则(满)二元树必有奇数个顶点。 49、菱形12面体的表面上有无哈密顿回路？ 50、设G=(V,E)是连通图且顶点数为p,最小度数为δ，若p>2δ,则G中有一长至少为2δ的路。 51、设G=(V,E)是p(p>3)个顶点的简单无向图,设G中最长路L的长度为l(l≥2)，起点与终点分别为u,v，而且degu+degv≥p。证明：G中必有与L不完全相同但长度也为L的路。 52、已知a,b,c,d,e,f,g7个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g 会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？ 53、设G为p个顶点的简单无向图。则 (1) 若G的边数q= (p-1)·(p-2)/2+2，证明G为哈密顿图。 (2) 若G的边数q= (p-1)·(p-2)/2+1，则G是否一定为哈密顿图？ 54、已知9个人v1,v2,…,v9，其中v1和两个人握过手，v2,v3,v4,v5各和3个人握过手，v6和4个人握过手，v7,v8各和5个人握过手，v9和6个人握过手。证明:这9个人中一定可以找出3个人互相握过手。 55、(1)一棵无向树有ni个度数为i的顶点,i=1,2,…,k。n2,n3,….nk均为已知数，问n1应为多少？ (2)在(1)中，若nr(3≤r≤k)未知，nj(j≠r)均为已知数，问nr应为多少？ 56、设G是平面连通图，顶点为p面数f，证明: (1)若p≥3，则f≤2p-4。(2)若δ(G)=4,则G中至少有6个顶点的度数≤5。 57、设d=(d1,d2,…,dn),其中di为非负整数，i=1,2,…,n。若存在n个顶点的(简单)无向图,使得顶点vi的度为di，则称d是可图解的。下面给出的各序列中哪些是可图解的？哪些不是，为什么？ （1）（1,1,1,2,3）；（6）（1,3,3,3）； （2）（0,1,1,2,3,3）；（7）（2,3,3,4,5,6）； （3）（3,3,3,3）；（8）（1,3,3,4,5,6,6）； （4）（2,3,3,4,4,5）；（9）（2,2,4）； （5）（2,3,4,4,5）；（10）(1,2,2,3,4,5）。 58、设G是有个p顶点，q条边的无向图，各顶点的度数均为3。则 (1)若q=3p-6,证明:G在同构意义下唯一，并求p,q。 (2)若p=6，证明:G在同构的意义下不唯一。 59、已知p阶(简单)无向图中有q条边，各顶点的度数 均为3，又2p=q+3，试画出满足条件的所有不同 构的G。 60、证明：在一个连通图中，两条最长的路有一个公共的顶点。 61、若G是一个恰有两个奇度顶点u和v的无向图，则 G连通?G+uv连通。 62、证明：若无向图G是不连通的，则G的补图GC是连通的。（逆命题不成立） 63、某工厂生产由6种不同颜色的纱织成的双色布。双色布中，每一种颜色至少和其他3种颜色搭配。证明:可以挑出3种不同的双色布,它们含有所有6种颜色。 64、设G是一个有p(p≥3)个顶点的连通图。u和v是G的两个不邻接的顶点,并且degu+degv≥p。证明：G是哈密顿图?G+uv是哈密顿图。 65、证明：完全图K9中至少存在彼此无公共边的两条哈密顿圈和一条哈密顿路？ 66、把平面分成p个区域，每两个区域都相邻，问p最大为多少？ 67、证明：不存在具有5个面，每两个面都共享一条公共边的平面图G。 68、设T为任一棵正则二元树，q为边数，n0为树叶数，证明：q=2n0-2。其中n0≥2。 69、设图G中有9个顶点，每个顶点的度不是5就是6。证明:G中至少有5个6度顶点或至少有6个5度顶点。 70、将无向完全图K6的边随意地涂上红色或绿色,证明:无论何种涂法,总有红色的K3 或绿色K3。 71、给无向完全图Kp(p ≥7)的各边随意地涂上红色或绿色，若已知从某点v0引出的p-1条边中至少有6条边涂红色，则Kp 存在红色的K4或绿色的K3。 72、有17位学者，每2位讨论3篇论文中的一篇且仅一篇，证明：至少有3位学者，他们相互讨论的是同一篇论文。 73、设d1,d2,…,dp 是p 个正整数,p ≥2,且 。 证明:存在一棵顶点度数为d1,d2,…,dp 的树。 74、判断下面命题是否正确，并说明理由。 任意平面图G 的对偶图G*的对偶图G**与G 同构。 75、设G*是平面图G 的对偶图，证明：p*=f ，q*=q ， f*=p-k+1。其中k(k ≥1)为G 的连通分支数。 76、证明：若G 是自对偶的平面图，则q=2p-2。其中p 和q 是G 的边与顶点数。 定义、定理及推论： 1、对于“5”这个数。世界上有“5”这个事物吗？没有。有的只是具体的5个事物，如5个人，5只笔，5张桌子等等，而这个“5”无非就是一个符号，它表明具有5个事物所形成的集合的共性。它们的共性就是它们相互对等，即它们的元素之间可以建立起一一对应。于是， “5”这个符号就是赋给每个含有五个元素的集合的一个记号，即若与含有五个元素的集对等，则都赋以相同的记号“5”。实际上，这就是“5”的本质。 2、设X ，Y ，Z 为三个非空集合。一个从X ×Y 到Z 的映射称为X 与Y 到Z 的一个二1 22p i i d p ==-∑ 元运算或二元代数运算。 当X＝Y＝Z时，即若?:X→X?X，则称?为X上的二元运算。 3、设X，Y是两个非空集合，一个从X到Y的映射称为X到Y的一个一元运算。 若X=Y，则?称为X上的一元运算。也称X的一个变换。 4、设A1,A2,…,An,D为非空集合，一个从A1×A2×…×An到D的映射?称为A1,A2,…,An到D的一个n元（代数）运算。 若A1=A2=…=An=D=A，则称?为A上的n元运算。 说明：1. 最常用的是一元运算和二元运算。 5、七桥问题就变成了如下的一笔画问题： 能否笔不离开纸，把图2的“图”一笔画成，使每条线画一次且只画一次，最后笔又回到出发点？ 欧拉证明了这个图不能一笔画成。 6、若G的图解已画在平(曲)面S上，而且任何两条边均不相交(除可能在端点相交外)，则图G称为嵌入平(曲)面S内。 已嵌入平面S内的图称为平面图。 若一个图可以嵌入平面，则称此图是可平面的 说明：可平面图：能画在平面上，但还没有画；平面图：已经画在平面上了。以后这两个概念不加区分。 7、任一非平凡树中至少有两个度为1的顶点(两片叶子)。 8、每个非平凡的连通图至少有两个顶点不是割点。 9、设G是一个(p,q)图，则 (1) 若q (2) 若q≥p-1，则χ(G)≤[2q/p] 10、若G的图解已画在平面S上，而且任何两条边均不相交(除可能在端点相交外)，则图G称为被嵌入平面S内。 已嵌入平面S内的图称为平面图。 若一个图可以嵌入平面，则称此图是可平面的 说明：可平面图：能画在平面上，但还没有画； 平面图：已经画在平面上了。以后这两个概念不加区分。 例如：图K4是可平面的，图K5没有平面嵌入法； K5画不出来，并不等于就是非平面图，必须证明。实际上，K5是典型的不可平面图，还有K3,3。 11、平面图G把平面分成了若干个区域，这些区域都是连通的，称之为G的面，其中无界的那个连通区域称为G的外部面，其余的单连通区域称为G的内部面。 说明： (1) 平面图的每个内部面都是G的某个圈围成的单连通区域； (2) 一个平面图可以没有内部面，但必有外部面，而且外部面唯一； 例如：树作为平面图就没有内部面。 (3) K4有4个面，f4是外部面，f1，f2，f3都是内部面。 12、(欧拉公式)设G是(p,q)平面连通图，有f个面，则p-q+f=2。 证：用数学归纳法证明，施归纳于面f的个数： 注意：定理中的连通性是必要的。若G不连通，则定理不成立。但却有下面的结论。推论:设G是一个具有f个面、k个分支的(p,q)平面图，则p-q+f=k+1 13、每个比赛图必有一条有向哈密顿路(即生成有向路)。 [用数学归纳法证明每个比赛图中必有有向哈密顿路] 证：设D是p个顶点的比赛图。施归纳于p: 当p=1,2时结论显然成立。 假设当有p(p≥2)时结论成立，往证对p+1个顶点的比赛图也成立。从中去掉一个顶点u，则得到一个具有p个顶点的比赛图D-u。由归纳假设D-u有哈密顿路u1,u2,…,up。 在D中，若(u,u1)∈A或(up,u)∈A，则结论成立。 今设(u1,u)∈A及(u,up)∈A，由于D是比赛图，所以u与uk(k=2,3,…,p-1)之间有且仅有一条弧，于是必有一个最大i使(ui,u)∈A且(u,ui+1)∈A。于是，u1u2…uiuui+1…up为D的一条哈密顿路。由归纳法原理知对任何p本题结论成立。 本试卷满分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 。 目录 第一章图的基本概念 (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]。 一、用真值表证明德*摩根律（证明其中一条即可）。 二、设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 《运筹学》试题样卷（一） 一、判断题（共计10分，每小题1分，对的打√，错的打X ） 1. 无孤立点的图一定是连通图。 2. 对于线性规划的原问题和其对偶问题，若其中一个有最优解， 另一个也一定有最优解。 3. 如果一个线性规划问题有可行解，那么它必有最优解。 4．对偶问题的对偶问题一定是原问题。 5．用单纯形法求解标准形式（求最小值）的线性规划问题时，与0 >j σ对应的变量 都可以被选作换入变量。 6．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷 多个最优解。 7. 度为0的点称为悬挂点。 8. 表上作业法实质上就是求解运输问题的单纯形法。 9. 一个图G 是树的充分必要条件是边数最少的无孤立点的图。 二、建立下面问题的线性规划模型（8分） 某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日；春夏季4000人日。如劳动力本身用不了时可外出打工，春秋季收入为25元 / 人日，秋冬季收入为20元 / 人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养每头奶牛需投资800元，每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲料，并占用人工秋冬季为100人日，春夏季为50人日，年净收入900元 / 每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季0.6人日，春夏季为0.3人日，年净收入2元 / 每只鸡。农场现有鸡舍允许最多养1500只鸡，牛栏允许最多养200头。三种作物每年需要的人工及收入情况如下表所示： 试决定该农场的经营方案，使年净收入为最大。 三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中54,x x 为 (1)写出原线性规划问题；（4分） (2)写出原问题的对偶问题；（3分） (3)直接由上表写出对偶问题的最优解。（1分） 四、用单纯形法解下列线性规划问题（16分） 3212max x x x Z +-= s. t. 3 x 1 + x 2 + x 3 ≤ 60 x 1- x 2 +2 x 3 ≤ 10 x 1+ x 2- x 3 ≤ 20 x 1 , x 2 , x 3 ≥0 五、求解下面运输问题。 （18分） 某公司从三个产地A 1、A 2、A 3 将物品运往四个销地B 1、B 2、B 3、B 4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示： 问：应如何调运，可使得总运输费最小? 六、灵敏度分析（共8分） 线性规划max z = 10x 1 + 6x 2 + 4x 3 s.t. x 1 + x 2 + x 3 ≤ 100 10x 1 +4 x 2 + 5 x 3 ≤ 600 2x 1 +2 x 2 + 6 x 3 ≤ 300 x 1 , x 2 , x 3 ≥ 0 哈工大 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 ?。 一、（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是传递的， 一、判断题（共计10分，每小题1分，对的打√，错的打X） 1.无孤立点的图一定是连通图。 2.对于线性规划的原问题和其对偶问题，若其中一个有最优解， 另一个也一定有最优解。 3.如果一个线性规划问题有可行解，那么它必有最优解。 4．对偶问题的对偶问题一定是原问题。 5．用单纯形法求解标准形式（求最小值）的线性规划问题时，与 > j σ 对应的变量都可以被选作换入变量。 6．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷 多个最优解。 7. 度为0的点称为悬挂点。 8. 表上作业法实质上就是求解运输问题的单纯形法。 9. 一个图G 是树的充分必要条件是边数最少的无孤立点的图。 二、建立下面问题的线性规划模型（8分） 某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日；春夏季4000人日。如劳动力本身用不了时可外出打工，春秋季收入为25元/ 人日，秋冬季收入为20元/ 人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养每头奶牛需投资800元，每只鸡投资3元。 养奶牛时每头需拨出1.5公顷土地种饲料，并占用人工秋冬季为100人日，春夏季为50人日，年净收入900元 / 每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季0.6人日，春夏季为0.3人日，年净收入2元 / 每只鸡。农场现有鸡舍允许最多养1500只 三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中5 4 ,x x 为松弛变量，问题的约束为?形式（共8分） (1)写出原线性规划问题；（4分） (2)写出原问题的对偶问题；（3分） (3)直接由上表写出对偶问题的最优解。（1分） 四、用单纯形法解下列线性规划问题（16分） 3212max x x x Z +-= s. t. 3 x 1 + x 2 + x 3 ≤ 60 x 1- x 2 +2 x 3 ≤ 10 x 1+ x 2- x 3 ≤ 20 x 1, x 2 , x 3 ≥0 五、求解下面运输问题。 （18分） 某公司从三个产地A 1、A 2、A 3 将物品运往四个销地B 1、B 2、B 3、B 4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示： 六、灵敏度分析（共8分） 线性规划max z = 10x 1 + 6x 2 + 4x 3 s.t. x 1 + x 2 + x 3 ≤ 100 10x 1 +4 x 2 + 5 x 3 ≤ 600 2x 1 +2 x 2 + 6 x 3 ≤ 300 x 1 , x 2 , x 3 ≥ 0 的最优单纯形表如下： 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 本课程教学方法 （一）教学方法 在这里，仅总结一下我的教学方法，不细展开，因此不涉及专业术语和与专业有关的例子。以下仅是一些指导思想： （1 ）启发式、由浅入深、从直观到抽象。要用些生动的例子帮助学生理解抽象概念的含义，但要做到生动而有趣又不失概念的准确性和推理的严格性，使学生易于接受，又了解直观背景。 （2 ）突出基本思想及方法，强调规律性，提高学生的抽象能力。要从哲学的高度强调概念是第一位的，引导学生思考问题时必须清楚理解所涉及的概念，使问题有一个明确的提法，引导学生掌握从问题到建立数学模型这一抽象过程的方法。 （3 ）利用集合论某些概念和理论与方法总结已学过的知识（如微积分、线性代数）找出本质的规律或主线，使学生认识事物内部的深刻规律。其次，随时指出在后继课如何应用这些知识、在科技论文中将怎样出现这些知识的应用。这不仅提高了学习的积极性，也使学生增强了学习的目的性。 （4 ）只要有可能就要以建立数学模型组织教学，讲习题也不例外。这样，能使学生加深印象—任何时候都要抓住事物的本质与事物之间的联系。 （5 ）鼓励学生多问为什么，为什么会是这样子而不是那个样子。不是教会学生怎样去使用工具、去模仿或复制，而是要教会学生独立思考，发现问题，提出问题和解决问题的思考，否则思维会退化。 （5 ）适当地提出一些未解决的问题。尚无答案的问题是摆在我们及学生面前的有无限价值的东西，因为支持大学的最高准则是探究未知领域。事实上，在每年教此课时，提一些问题确实有学生在思考。 （6 ）注意每个学科（内部）的美。如果某部分很丑或太复杂，人们倾向于认为是不清楚的和暂时的，它没有真正反映客观规律，因为我们相信，越接近终极真理，我们的解释中的不自然的东西就越少。科学是以越来越完美、有力的理论向终极真理发展的。 （二）关于素质教育、培养创新精神的人才的思考 素质教育应该是各类教育的核心，而培养创新人才则是高等教育的任务（见高等教育法，第五条）。在这里讨论这个题目不太合适，因为题太大。其实，在（五）中就本课的特点贯穿了素质教育和培养创新人才的思想。以下只扼要地总结一下。 1 ）教会学生如何进行逻辑推理，如何进行正确地思维，如何在纷繁的事物中抓住主要的联 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 的度序列，该度序列是一个图序列吗？。 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 也是连通图。集合论与图论 试题A
图论期末考试整理复习资料
北大集合论与图论往年考题.pdf
运筹学期末试题
集合论与图论试卷2
图论与组合数学期末复习题含答案
集合论与图论
哈工大年集合论与图论试卷
集合论与图论SG2017-期中试题-答案(1)
运筹学期末试题
集合论图论 期中考试试题及答案
集合论与图论
电子科技大学2017年图论期末试卷
2015电子科技大学_图论期末考试复习题
集合论与图论复习题
集合论与图论期中考试
最新哈工大集合论与图论试卷
相关主题
文本预览