哈工大年集合論與圖論試卷-2023修改整理

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦哈工大年集合論與圖論試卷--

本試卷滿分90分

(計算機(jī)科學(xué)與技術(shù)學(xué)院0９級各專業(yè))一、填空（本題滿分１0分,每空各1分)

1.設(shè)BA,為集合,則ABBA=)\(成立的充分須要條件是什么？(AB?)２.設(shè)}2,1{},,,2,1{==YnX,則從X到Y(jié)的滿射的個數(shù)為多少?（22-n)３．在集合}11,10,9,8,4,3,2{=A上定義的整除關(guān)系“|”是A上的偏序關(guān)系，則

最大元是什么?(無）

4．設(shè){,,}Aabc=，給出A上的一個二元關(guān)系,使其同時不滿足自反性、反自反性、對稱性、反駁稱和傳遞性的二元關(guān)系。({(,),(,),(,),(,)}Raabccbac=）５．設(shè)∑為一個有限字母表,∑上全部字(包括空字）之集記為*∑，則*∑是否是可數(shù)集?（是)

６.含5個頂點(diǎn)、3條邊的不同構(gòu)的無向圖個數(shù)為多少？（４）

7.若G是一個),(pp連通圖，則G至少有多少個生成樹?（3）

8.如圖所示圖G,回答下列問題：

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

(2）圖G是否是歐拉圖?(不是）

(3)圖G的色數(shù)為多少？(4)

二、簡答下列各題（本題滿分40分）

1．設(shè)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.設(shè)G是無向圖,推斷下列命題是否成立？若成立給出證實，若不成立舉出

反例。（6分）

（1）若圖G是連通圖，則G的補(bǔ)圖CG也是連通圖。

(2)若圖G是不連通圖，則G的補(bǔ)圖CG是連通圖。

解：(1）CG不一定是連通圖。

(2）CG一定連通圖。

由于G不連通，故G至少有兩個分支,一個是1G,另外一些支構(gòu)成的子圖是2G。對于cG中隨意兩個頂點(diǎn)u和v:

（１）若12,uVvV∈∈,則u與v不在G中鄰接。由補(bǔ)圖的定義可知:u與v必在cG

中鄰接;

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

綜上可知,對cG中任兩個頂點(diǎn)u和v之間都有路銜接，故cG是連通的。

3.設(shè)集合{,,,,}Aabcde=,A上的關(guān)系定義如下：(6分）

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

(,),(,),(,),(,),(,),(,)}becccedddeee。則

（1)寫出R的關(guān)系矩陣;(2)驗證(,)AR是偏序集；（３)畫出Hasse圖。解：（１)R所對應(yīng)的關(guān)系矩陣為RM為:11111011

010*******

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

?(2）由關(guān)系矩陣可知：對角線上的全部元素全為1,故R是自反的;1ijjirr+≤，故R是反駁稱的;2R對應(yīng)的關(guān)系矩陣2RM為:21111101101001010

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

。因此R是傳遞的。

綜上可知：故R是A上的偏序關(guān)系，從而(,)AR是偏序集。

c

（3)(,)AR對應(yīng)的Hasse圖如圖所示。

4．設(shè)A是有限集合,AAf→:。則(３分)

（1)若f是單射，則f必是滿射嗎？反之如何？

（2)若A是無限集合，結(jié)論又如何？

解：(１)f是單射，則f必是滿射；反之也成立；

（2）若A是無限集合,結(jié)論不成立。

舉例:令N={1，２，3，…｝,則

(１）設(shè)NNs→:，,()1nNSnn?∈=+。明顯,S是單射，但不是滿射。

(2）設(shè)NNt→:,,(1)1,()1,2nNttnnn?∈==-≥。明顯,T是滿射，

但不是單射。

5．（4分）

（１）按照你的理解給出關(guān)系的傳遞閉包的定義；

(２）設(shè)},,,{dcbaA=,A上的關(guān)系{(,),(,),(,)}Rabbcca=，求關(guān)系R的傳遞閉包+R。解：（1)設(shè)R是集合A上的二元關(guān)系，則A上包含R的全部傳遞關(guān)系的交稱為

關(guān)系R的傳遞閉包。

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

６.由６個頂點(diǎn)，１2條邊構(gòu)成的平面連通圖G中,每個面由幾條邊圍成?說明理由。（４分)

解:每個面由3條邊圍成。

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

由于容易平面連通圖的每個面至少由3條邊圍成，所以假設(shè)存在某個面由大于３條邊圍成，則有:32fq<,即2424<，沖突。

故每個面至多由3條面圍成,于是G中每個面由3條邊圍成的。

7．設(shè)(,)GVE=是至少有一個頂點(diǎn)不是孤立點(diǎn)的圖。若,vV?∈degv為偶數(shù)，則G中是否必有圈?說明理由。(4分)

解:G中必有圈。

令P是G中的一條最長的路,12:nPvvv,則由1deg2v≥知，必有某個頂點(diǎn)u與iv鄰接。因為P是最長路，所以u必是34,,,nvvv中的某個,3ivi≥。于是，121ivvvv是G的一個回路。

8.設(shè)T是一個有0n個葉子的二元樹，出度為２的頂點(diǎn)為2n,則0n與2n有何關(guān)系？說明理由。（４分）

解:0n與2n的關(guān)系為：021nn=+

由()()iivVvV

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

9.已知有向圖D的鄰接矩陣0110010001000010010000010A????????=??????????

,則(3分)

（1)畫出鄰接矩陣為A的有向圖D的圖解；

（2)寫出D的可達(dá)矩陣R；

(3）寫出計算兩頂點(diǎn)之間長為k的有向通道條數(shù)的計算辦法。

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

??

???0011100111001111111111111;（3）ijkA)(。三、證實下列各題(本題滿分４0分,每小題各5分)

1．設(shè)G是一個),(qp圖,證實：G是樹?G無圈且1+=qp。

證：?由于G是樹,所以G是無圈；

第二對G的頂點(diǎn)數(shù)p舉行歸納證實p=q+1。

當(dāng)ｐ為１或2時，連通圖G中明顯有p=q+1。

假設(shè)對一切少于ｐ個頂點(diǎn)的樹結(jié)論成立；

今設(shè)G是有p個頂點(diǎn)樹,從G中去掉任一條邊x,則G-x恰有兩個支。由歸納假設(shè)，每個支中頂點(diǎn)數(shù)與邊數(shù)之間有關(guān)系式:p1=q1+１,p2=ｑ2+1。

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

?只須證實G連通即可。

假設(shè)G不連通,則必有k個支且ｋ≥2。因為每個支都是連通的且無回路,故每個支都是樹。于是，對每個支都有kiqpii,,2,1,1=+=。于是,∑∑==+=+==kikiiikqkqpp11。

由假設(shè)k≥2,這與p=q+1相沖突。因此，Ｇ是連通的。即G是樹。

2．設(shè):fXY→,證實：f是單射12,(())XFffFF-??∈=。

證：(1）?1(())xffF-?∈，則()()fxfF∈，于是F中必存在1x，使得1()()fxfx=。由于f是單射，故必有1xx=。即xF∈，所以1(())ffFF-?。反過來,,()()xFfxfF?∈∈，從而有1(())xffF-∈，所以1(())FffF-?。

因此1(())ffFF-=。

?假設(shè)f不是單射,則1212,,xxXxx?∈≠，但12()()fxfxy==。令1{}Fx=，于是111112(())(({})({}){,}ffFffxfyxx===,故有121{,}{}xxFx==，沖突。即f一定為單射。

３．設(shè)G是一個)3(≥pp個頂點(diǎn)的圖。u和v是G的兩個不鄰接的頂點(diǎn),并且

pvu≥+degdeg。

證實:G是哈密頓圖uvG+?是哈密頓圖。

證實：?明顯成立。

?假設(shè)G不是哈密頓圖，則有題意知在G中必有一條從u到v的哈密頓路。不妨設(shè)此路為vvvuvp132-，令deｇv1＝k,degvp=l，則在G中與u鄰接的頂點(diǎn)為uｉ1,uｉ2,…，uik，其中２=i１<i2＜…＜ik≤ｐ-1。這時頂點(diǎn)ｕiｒ-1(r=2，３…,k)不能與頂點(diǎn)ｖp鄰接。

由于此時Ｇ有哈密頓回路ｕｖ2…vir-1vvp-1…ｖiｒu,因此vp至少與u，ｖ2,…，vｐ-1中的k個頂點(diǎn)不鄰接。于是，ｌ≤p-1－k，從而k+1≤p-1,與題設(shè)沖突,故Ｇ是哈密頓圖。

4.設(shè)R是A上的一個二元關(guān)系，證實：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是對稱的。

５．設(shè)R是A上的一個二元關(guān)系,令{(,)|SabcA=?∈,使得(,)acR∈且(,)cb}R∈。證實：若R是A上的等價關(guān)系,則S也是A上的等價關(guān)系；

證:由于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是等價關(guān)系。

6.利用康托對角線法證實:若A可數(shù)，則2A不行數(shù)。

證：由于(){}{}2~:0,1AChAffA=→，所以只須證實()ChA不行數(shù)即可。()fChA?∈，f可表為0,1的無窮序列。若()ChA可數(shù),則()ChA的元素可羅列成無重復(fù)項的無窮序列123,,,fff。每個if可表成０,１的無窮序列123,,,

iiifff。用對角線法構(gòu)造