哈工大年集合论与图论试卷-2023修改整理

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐哈工大年集合论与图论试卷--

本试卷满分90分

(计算机科学与技术学院0９级各专业)一、填空（本题满分１0分,每空各1分)

1.设BA,为集合,则ABBA=)\(成立的充分须要条件是什么？(AB?)２.设}2,1{},,,2,1{==YnX,则从X到Y的满射的个数为多少?（22-n)３．在集合}11,10,9,8,4,3,2{=A上定义的整除关系“|”是A上的偏序关系，则

最大元是什么?(无）

4．设{,,}Aabc=，给出A上的一个二元关系,使其同时不满足自反性、反自反性、对称性、反驳称和传递性的二元关系。({(,),(,),(,),(,)}Raabccbac=）５．设∑为一个有限字母表,∑上全部字(包括空字）之集记为*∑，则*∑是否是可数集?（是)

６.含5个顶点、3条边的不同构的无向图个数为多少？（４）

7.若G是一个),(pp连通图，则G至少有多少个生成树?（3）

8.如图所示图G,回答下列问题：

(１）图G是否是偶图?(不是)

(2）图G是否是欧拉图?(不是）

(3)图G的色数为多少？(4)

二、简答下列各题（本题满分40分）

1．设DCBA,,,为随意集合，推断下列等式是否成立?若成立给出证实，若不成立举出反例。(6分)

(1))()()()(DBCADCBA??=?；

（2）()()()()ABCDACBD?=??。

解:（1）不成立。例如}{,acBDA====φ即可。

（2）成立。(,)xy?∈()()ABC

D?，有,xAByCD∈∈，即,,,xAxByCyD∈∈∈∈。所以(,),(,)xyACxyBD∈?∈?,因此(,)()()xyACBD∈??,从而()()ABC

D??()()ACBD??。反之,(,)xy?∈()()ACBD??，有,,,xAxByCyD∈∈∈∈。即(,)xy∈()()ABCD?，从而()()ACBD???()()ABC

D?。

因此，()()ABCD?＝()()ACBD??。

2.设G是无向图,推断下列命题是否成立？若成立给出证实，若不成立举出

反例。（6分）

（1）若图G是连通图，则G的补图CG也是连通图。

(2)若图G是不连通图，则G的补图CG是连通图。

解：(1）CG不一定是连通图。

(2）CG一定连通图。

由于G不连通，故G至少有两个分支,一个是1G,另外一些支构成的子图是2G。对于cG中随意两个顶点u和v:

（１）若12,uVvV∈∈,则u与v不在G中邻接。由补图的定义可知:u与v必在cG

中邻接;

（2)若12,()uvVV∈或,取2wV∈2()V或,则u与w，w与v在G都不邻接，故u与w，w与v在cG必邻接,于是uwv就是cG中的一条路。

综上可知,对cG中任两个顶点u和v之间都有路衔接，故cG是连通的。

3.设集合{,,,,}Aabcde=,A上的关系定义如下：(6分）

{(,),(,),(,),(,),(,),(,),(,),Raaabacadaebbbc=

(,),(,),(,),(,),(,),(,)}becccedddeee。则

（1)写出R的关系矩阵;(2)验证(,)AR是偏序集；（３)画出Hasse图。解：（１)R所对应的关系矩阵为RM为:11111011

010*******

1100001RM?????=????

?(2）由关系矩阵可知：对角线上的全部元素全为1,故R是自反的;1ijjirr+≤，故R是反驳称的;2R对应的关系矩阵2RM为:21111101101001010

001100001RRMM?????==?????

。因此R是传递的。

综上可知：故R是A上的偏序关系，从而(,)AR是偏序集。

c

（3)(,)AR对应的Hasse图如图所示。

4．设A是有限集合,AAf→:。则(３分)

（1)若f是单射，则f必是满射吗？反之如何？

（2)若A是无限集合，结论又如何？

解：(１)f是单射，则f必是满射；反之也成立；

（2）若A是无限集合,结论不成立。

举例:令N={1，２，3，…｝,则

(１）设NNs→:，,()1nNSnn?∈=+。明显,S是单射，但不是满射。

(2）设NNt→:,,(1)1,()1,2nNttnnn?∈==-≥。明显,T是满射，

但不是单射。

5．（4分）

（１）按照你的理解给出关系的传递闭包的定义；

(２）设},,,{dcbaA=,A上的关系{(,),(,),(,)}Rabbcca=，求关系R的传递闭包+R。解：（1)设R是集合A上的二元关系，则A上包含R的全部传递关系的交称为

关系R的传递闭包。

（２))},(),,(),,(),,(),,(),,(),,(),,(),,{(bcaccbabcabaccbbaaR=+

６.由６个顶点，１2条边构成的平面连通图G中,每个面由几条边围成?说明理由。（４分)

解:每个面由3条边围成。

在图G中，6p=,12q=,按照欧拉公式2pqf-+=，得8f=。

由于容易平面连通图的每个面至少由3条边围成，所以假设存在某个面由大于３条边围成，则有:32fq<,即2424<，冲突。

故每个面至多由3条面围成,于是G中每个面由3条边围成的。

7．设(,)GVE=是至少有一个顶点不是孤立点的图。若,vV?∈degv为偶数，则G中是否必有圈?说明理由。(4分)

解:G中必有圈。

令P是G中的一条最长的路,12:nPvvv,则由1deg2v≥知，必有某个顶点u与iv邻接。因为P是最长路，所以u必是34,,,nvvv中的某个,3ivi≥。于是，121ivvvv是G的一个回路。

8.设T是一个有0n个叶子的二元树，出度为２的顶点为2n,则0n与2n有何关系？说明理由。（４分）

解:0n与2n的关系为：021nn=+

由()()iivVvV

idvodvq∈∈==∑∑且1qp=-，得22022()1npnnp?+?--=-，得021nn=+。

9.已知有向图D的邻接矩阵0110010001000010010000010A????????=??????????

,则(3分)

（1)画出邻接矩阵为A的有向图D的图解；

（2)写出D的可达矩阵R；

(3）写出计算两顶点之间长为k的有向通道条数的计算办法。

解:（1）（2)?????

??

???0011100111001111111111111;（3）ijkA)(。三、证实下列各题(本题满分４0分,每小题各5分)

1．设G是一个),(qp图,证实：G是树?G无圈且1+=qp。

证：?由于G是树,所以G是无圈；

第二对G的顶点数p举行归纳证实p=q+1。

当ｐ为１或2时，连通图G中明显有p=q+1。

假设对一切少于ｐ个顶点的树结论成立；

今设G是有p个顶点树,从G中去掉任一条边x,则G-x恰有两个支。由归纳假设，每个支中顶点数与边数之间有关系式:p1=q1+１,p2=ｑ2+1。

所以，p=p１＋ｐ2=q１＋q2+2=(q1+q2+1)+1=q+1。

?只须证实G连通即可。

假设G不连通,则必有k个支且ｋ≥2。因为每个支都是连通的且无回路,故每个支都是树。于是，对每个支都有kiqpii,,2,1,1=+=。于是,∑∑==+=+==kikiiikqkqpp11。

由假设k≥2,这与p=q+1相冲突。因此，Ｇ是连通的。即G是树。

2．设:fXY→,证实：f是单射12,(())XFffFF-??∈=。

证：(1）?1(())xffF-?∈，则()()fxfF∈，于是F中必存在1x，使得1()()fxfx=。由于f是单射，故必有1xx=。即xF∈，所以1(())ffFF-?。反过来,,()()xFfxfF?∈∈，从而有1(())xffF-∈，所以1(())FffF-?。

因此1(())ffFF-=。

?假设f不是单射,则1212,,xxXxx?∈≠，但12()()fxfxy==。令1{}Fx=，于是111112(())(({})({}){,}ffFffxfyxx===,故有121{,}{}xxFx==，冲突。即f一定为单射。

３．设G是一个)3(≥pp个顶点的图。u和v是G的两个不邻接的顶点,并且

pvu≥+degdeg。

证实:G是哈密顿图uvG+?是哈密顿图。

证实：?明显成立。

?假设G不是哈密顿图，则有题意知在G中必有一条从u到v的哈密顿路。不妨设此路为vvvuvp132-，令deｇv1＝k,degvp=l，则在G中与u邻接的顶点为uｉ1,uｉ2,…，uik，其中２=i１<i2＜…＜ik≤ｐ-1。这时顶点ｕiｒ-1(r=2，３…,k)不能与顶点ｖp邻接。

由于此时Ｇ有哈密顿回路ｕｖ2…vir-1vvp-1…ｖiｒu,因此vp至少与u，ｖ2,…，vｐ-1中的k个顶点不邻接。于是，ｌ≤p-1－k，从而k+1≤p-1,与题设冲突,故Ｇ是哈密顿图。

4.设R是A上的一个二元关系，证实：R是对称的1-=?RR。

证:?(,)xyR?∈，由R的对称性有(,)yxR∈,即1(,)xyR-∈,从而R?R－1

反之,1(,)yxR-?∈,则(,)xyR∈。由R的对称性有：(,)yxR∈,从而Ｒ-1?R故R=R-1

?x?,y∈X，若(,)xyR∈,由R＝Ｒ-1,得1(,)xyR-∈，即(,)yxR∈，故R是对称的。

５．设R是A上的一个二元关系,令{(,)|SabcA=?∈,使得(,)acR∈且(,)cb}R∈。证实：若R是A上的等价关系,则S也是A上的等价关系；

证:由于R是自反的，所以aA?∈,有(,)aaR∈。按照S的定义,有(,)aaS∈，所以

S是自反的；

若(,)abS∈，则cA?∈，使得(),acR∈且(),cbR∈。由于R是对称的，所以(),bcR∈且(),caR∈，按照S的定义有(),baS∈，所以S是对称的;

若(),abS∈,(),bcS∈,则dA?∈,使得(),adR∈且(),dbR∈。由于R是传递的，所以(),abR∈。

则eA?∈,使得(),beR∈且(),ecR∈。由于R是传递的,所以(),bcR∈。按照S的定义有(),acS∈。所以S是传递的。

综上可知:S是等价关系。

6.利用康托对角线法证实:若A可数，则2A不行数。

证：由于(){}{}2~:0,1AChAffA=→，所以只须证实()ChA不行数即可。()fChA?∈，f可表为0,1的无穷序列。若()ChA可数,则()ChA的元素可罗列成无重复项的无穷序列123,,,fff。每个if可表成０,１的无穷序列123,,,

iiifff。用对角线法构造