答案08秋季集合論與圖論試題A

1、試 題： 班號： 姓名：本試卷滿分90分（計算機科學與技術(shù)學院07級）一、填空（本題滿分10分，每小題各1分）1.設(shè)是集合，若，則等于什么？ （ ）2設(shè)X為集合，為X上的偏序關(guān)系，計算等于什么？ （ ）3把置換分解成循環(huán)置換的乘積。 （149）（2367）（58）4什么是無窮集合？ （凡能與自身的一個真子集對等的集稱為無窮集合）5設(shè)是一棵樹，則個頂點的樹至多有多少個割點？ （-2 ）6設(shè)是一個有個頂點條弧的有向圖，若是連通的，則至少是多大？（ -1 ）7設(shè)，則以V為頂點集的無向圖共有多少個？ （）8設(shè)，則以V為頂點集的有向圖共有多少個？）9每個有3個支的不連通圖，若每個頂點的度均大于或等于2，

2、則該圖至少有多少個圈？ （ 3 ）10設(shè)是一個正則二元樹，它有個葉子，則有多少條?。浚?（-1）二、判斷對錯（本題滿分10分，每小題各1分）1.設(shè)是兩個集合，則且不可能同時成立。 （ 錯 ）2在集合上可以定義個二元運算。 （ 錯 ）3設(shè)，若存在唯一一個映射，使得，則一定是可逆的。 （ 錯 ）4設(shè)是一個集合，則上的自反和反自反的二元關(guān)系個數(shù)相同。 （ 對 ）5.設(shè)為一個有限字母表，上所有字（包括空字）之集記為。則不是可數(shù)集。 （ 錯 ）6.設(shè)是一個圖，若，則中必有圈。 （ 對 ）7.若G是一個連通圖，則至多有個生成樹。 （ 對 )8.設(shè)，是正則圖且頂點連通度為1，則。（ 對 ）9把平面分成個區(qū)域

3、，每兩個區(qū)域都相鄰，則最大為5。（ 錯 ）10.有向圖的每一條弧必在某個強支中。 （ 錯 ） 三、證明下列各題(本題滿分18分，每小題各6分)1設(shè)是三個任意的集合，則 （1）證明：；（2） 舉例說明。證：(1) 證明：，有，即但，從而，于是，即。 (2) 若，則。2設(shè)是三個任意的集合，證明：。證明：設(shè) ，則，從而,。于是，,因此，即。 反之，設(shè)，有，從而，故且。于是，即。因此，。3設(shè)是兩個任意的集合，證明：。證：，則若，則。因而且，故；若，則，同理可得。因此 。反之，因為，故。于是 ，有。若，則，故；若，則，故。因此。從而。四、回答下列各題(本題滿分14分)1如圖1所示是彼德森圖，回答下列問題

4、：（6分）（1）是否是偶圖？ （不是 ）（2）是否是歐拉圖？ （不是 ）（3）是否是平面圖？ （不是 ）（4）是否是哈密頓圖？ （不是 ）（5）的色數(shù)為多少？ （ 3 ） 圖12設(shè)G是如圖2所示的有向圖，則（8分）（1）寫出G的鄰接矩陣。（2）求頂點到間長為10的有向通道的條數(shù)的方法是什么？（不必算出具體的數(shù)）（3）寫出G的可達矩陣。（4）畫出對應(yīng)于表達式（AB*C）/（A-C）的二元樹表示。解：（1）；（2）元素的值；（3） （4）五、證明下列各題(本題滿分18分, 每小題各6分)1設(shè)。若是單射，則與哪個是單射？請證明之。解：是單射。因為是單射，所以，若，則。因此，故是單射。2設(shè)?！啊笔巧先?/p>

5、下的二元關(guān)系：，當且僅當。則(1) 證明：是等價關(guān)系；(2)求等價類數(shù)。證：(1)等價關(guān)系顯然；(2)等價類數(shù)為：。3令，利用康托對角線法證明S是不可數(shù)集。證:假設(shè)從N到0, 1的所有映射之集可數(shù)，則可排成無重復(fù)項的無窮序列。每個函數(shù)確定了一個0,1序列。構(gòu)造序列，若；否則。該序列對應(yīng)的函數(shù)，不為任一個，矛盾。六、證明下列各題（本題滿分20分，每小題各5分）1.設(shè)是一個恰有兩個不鄰接的奇度頂點和的無向圖，證明：連通連通。證： 顯然成立。 假設(shè)不連通，則恰有2個分支：。由題意不在一個分支上，于是含有的頂點的分支只有一個奇度數(shù)頂點與握手定理的推論矛盾。于是假設(shè)不成立，即是連通的。2證明：任意一棵非

6、平凡樹至少有兩個樹葉。證明：設(shè)為一棵非平凡的無向樹，中最長的路為。若端點和中至少有一個不是樹葉，不妨設(shè)不是樹葉，即有，則除與上的頂點相鄰?fù)?，必存在與相鄰，而不在上，否則將產(chǎn)生回路。于是仍為的一條比更長的路，這與為最長的路矛盾。故必為樹葉。 同理，也是樹葉。3證明：若每個頂點的度數(shù)大于或等于3，則不存在有7條邊的平面連通圖。證明：假設(shè)存在這樣的平面圖，則由，有而由；由；為整數(shù)，故，于是與(1)矛盾。4證明每個比賽圖中必有有向哈密頓路。（用數(shù)學歸納法證明）證：設(shè)是個頂點的比賽圖。施歸納于當時,結(jié)論顯然成立。假設(shè)當時結(jié)論成立，往證對個頂點的比賽圖也成立。從中去掉一個頂點，則得到一個具有個頂點的比賽圖。由歸納假設(shè)有哈密頓路。在中，若或為