1、本試卷滿分90分（計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院09級(jí)各專業(yè)）一、填空(本題滿分10分，每空各1分)1設(shè)為集合，則成立的充分必要條件是什么？（）2設(shè)，則從到的滿射的個(gè)數(shù)為多少？（ ）3在集合上定義的整除關(guān)系“|”是上的偏序關(guān)系， 則最大元是什么？ （ 無(wú) ）4設(shè)，給出上的一個(gè)二元關(guān)系，使其同時(shí)不滿足自反性、反自反性、對(duì)稱性、反對(duì)稱和傳遞性的二元關(guān)系。（）5設(shè)為一個(gè)有限字母表，上所有字（包括空字）之集記為，則是 否是可數(shù)集？ （ 是 ）6含5個(gè)頂點(diǎn)、3條邊的不同構(gòu)的無(wú)向圖個(gè)數(shù)為多少？ （ 4 ）7若是一個(gè)連通圖，則至少有多少個(gè)生成樹? （ 3 )8. 如圖所示圖，回答下列問(wèn)題： （1）圖是否是偶圖？ （

2、不是 ）（2）圖是否是歐拉圖？ （ 不是 ）（3）圖的色數(shù)為多少？ （ 4 ） 二、簡(jiǎn)答下列各題（本題滿分40分）1.設(shè)為任意集合，判斷下列等式是否成立？若成立給出證明，若不成立舉出反例。（6分）（1）；（2）。解：（1）不成立。例如即可。 （2）成立。，有，即。所以，因此，從而。反之，有。即，從而。因此，。2. 設(shè)是無(wú)向圖，判斷下列命題是否成立？若成立給出證明，若不成立舉出反例。（6分）（1）若圖是連通圖，則的補(bǔ)圖也是連通圖。（2）若圖是不連通圖，則的補(bǔ)圖是連通圖。解：（1）不一定是連通圖。 （2）一定連通圖。因?yàn)椴贿B通，故至少有兩個(gè)分支，一個(gè)是，另外一些支構(gòu)成的子圖是。對(duì)于中任意兩個(gè)頂點(diǎn)和

3、：（1）若，則與不在中鄰接。由補(bǔ)圖的定義可知：與必在中鄰接；（2）若，取，則與，與在都不鄰接，故與，與在必鄰接，于是就是中的一條路。綜上可知，對(duì)中任兩個(gè)頂點(diǎn)和之間都有路連接，故是連通的。3設(shè)集合，上的關(guān)系定義如下：（6分）。 則 （1）寫出的關(guān)系矩陣； （2）驗(yàn)證是偏序集； （3）畫出圖。cebad解：（1）所對(duì)應(yīng)的關(guān)系矩陣為為：（2）由關(guān)系矩陣可知：對(duì)角線上的所有元素全為1，故是自反的；，故是反對(duì)稱的； 對(duì)應(yīng)的關(guān)系矩陣為：。因此是傳遞的。綜上可知：故是上的偏序關(guān)系，從而是偏序集。（3）對(duì)應(yīng)的圖如圖所示。4設(shè)是有限集合，。則（3分）（1）若是單射，則必是滿射嗎？反之如何？（2）若是無(wú)限集合，結(jié)

4、論又如何？解：（1）是單射，則必是滿射；反之也成立；（2）若是無(wú)限集合，結(jié)論不成立。舉例：令N1，2，3，則（1）設(shè)，。顯然，是單射，但不是滿射。（2）設(shè)，。顯然，是滿射，但不是單射。5（4分）（1）根據(jù)你的理解給出關(guān)系的傳遞閉包的定義； （2）設(shè)，上的關(guān)系，求關(guān)系的傳遞閉包。解：（1）設(shè)是集合上的二元關(guān)系，則上包含的所有傳遞關(guān)系的交稱為關(guān)系的傳遞閉包。 （2）6由6個(gè)頂點(diǎn)，12條邊構(gòu)成的平面連通圖中，每個(gè)面由幾條邊圍成？說(shuō)明理由。（4分）解：每個(gè)面由3條邊圍成。在圖中，根據(jù)歐拉公式，得。因?yàn)楹?jiǎn)單平面連通圖的每個(gè)面至少由3條邊圍成，所以假設(shè)存在某個(gè)面由大于3條邊圍成，則有：，即，矛盾。故每個(gè)面

5、至多由3條面圍成，于是中每個(gè)面由3條邊圍成的。7設(shè)是至少有一個(gè)頂點(diǎn)不是孤立點(diǎn)的圖。若為偶數(shù)，則中是否必有圈？說(shuō)明理由。（4分）解: 中必有圈。令是中的一條最長(zhǎng)的路，則由知，必有某個(gè)頂點(diǎn)與鄰接。由于是最長(zhǎng)路，所以必是中的某個(gè)。于是，是的一個(gè)回路。8設(shè)是一個(gè)有個(gè)葉子的二元樹，出度為2的頂點(diǎn)為，則與有何關(guān)系？說(shuō)明理由。（4分）解：與的關(guān)系為：由且，得，得。9已知有向圖的鄰接矩陣，則（3分）（1）畫出鄰接矩陣為的有向圖的圖解；（2）寫出的可達(dá)矩陣；（3）寫出計(jì)算兩頂點(diǎn)之間長(zhǎng)為的有向通道條數(shù)的計(jì)算方法。解： （1） （2） ； （3）。 三、證明下列各題（本題滿分40分，每小題各5分）1設(shè)是一個(gè)圖，證明

6、：是樹無(wú)圈且。證：因?yàn)镚是樹，所以G是無(wú)圈；其次對(duì)G的頂點(diǎn)數(shù)p進(jìn)行歸納證明p=q+1。當(dāng)p為1或2時(shí)，連通圖G中顯然有p=q+1。假設(shè)對(duì)一切少于p個(gè)頂點(diǎn)的樹結(jié)論成立；今設(shè)G是有p個(gè)頂點(diǎn)樹，從G中去掉任一條邊x，則G-x恰有兩個(gè)支。由歸納假設(shè)，每個(gè)支中頂點(diǎn)數(shù)與邊數(shù)之間有關(guān)系式：p1=q1+1，p2=q2+1。所以，p=p1+p2=q1+q2+2=(q1+q2+1)+1=q+1。只須證明G連通即可。假設(shè)G不連通，則必有k個(gè)支且k2。由于每個(gè)支都是連通的且無(wú)回路，故每個(gè)支都是樹。于是，對(duì)每個(gè)支都有。于是，。由假設(shè)k2，這與p=q+1相矛盾。因此，G是連通的。即G是樹。2設(shè)，證明：是單射。證：（1），

7、則，于是中必存在，使得。因?yàn)槭菃紊?，故必有。即，所以。反過(guò)來(lái)， ，從而有，所以。因此。假設(shè)不是單射，則，但。令，于是，故有，矛盾。即一定為單射。3設(shè)是一個(gè)個(gè)頂點(diǎn)的圖。和是的兩個(gè)不鄰接的頂點(diǎn)，并且。證明：是哈密頓圖是哈密頓圖。證明：顯然成立。假設(shè)G不是哈密頓圖，則有題意知在G中必有一條從u到v的哈密頓路。不妨設(shè)此路為,令degv1=k，degvp =l,則在G中與u鄰接的頂點(diǎn)為ui1 ，ui2，uik，其中2=i1i2ikp-1。這時(shí)頂點(diǎn)uir-1(r=2，3，k)不能與頂點(diǎn)vp鄰接。因?yàn)榇藭r(shí)G有哈密頓回路uv2vir-1vvp-1viru，因此vp至少與u，v2，vp-1中的k個(gè)頂點(diǎn)不鄰接。于

8、是，lp-1-k，從而k+1p-1,與題設(shè)矛盾，故G是哈密頓圖。4設(shè)是上的一個(gè)二元關(guān)系，證明：是對(duì)稱的。證：，由R的對(duì)稱性有，即，從而RR-1反之，則。由R的對(duì)稱性有：，從而R-1R故RR-1，若，由RR-1，得，即，故R是對(duì)稱的。5設(shè)是上的一個(gè)二元關(guān)系，令，使得且。證明：若是上的等價(jià)關(guān)系，則也是上的等價(jià)關(guān)系；證：因?yàn)槭亲苑吹模?，有。根?jù)的定義，有，所以是自反的；若，則，使得且。因?yàn)槭菍?duì)稱的，所以且，根據(jù)的定義有，所以是對(duì)稱的；若，則，使得且。因?yàn)槭莻鬟f的，所以。則，使得且。因?yàn)槭莻鬟f的，所以。根據(jù)的定義有。所以是傳遞的。綜上可知：是等價(jià)關(guān)系。6. 利用康托對(duì)角線法證明：若可數(shù)，則不可數(shù)。證：因?yàn)?，所以只須證明不可數(shù)即可。，0，1的無(wú)窮序列。若可數(shù)，則的元素可排列成無(wú)重復(fù)項(xiàng)的無(wú)窮序列。每個(gè)可表成0，1的無(wú)窮序列。用對(duì)角線法構(gòu)造一個(gè)0，1序列：，則；則。一般地，若，則；如果，則，則確定的函數(shù)，但，矛盾。所以，不可數(shù)。7. 設(shè)是一個(gè)圖，若是一個(gè)正則偶圖