復試離散生期末題2011s

1、哈工大 2011 年 春季學期集合論與圖論題本試卷滿分 100 分（計算機學院、英才學院 10 級）一、填空(本題滿分 10 分，每空各 1 分)1.設 f : X Y , g : Y Z ，若 g o f 是單射，則 f 與 g 哪個是單射？（f）2.集合 A a, b, c, d ， A 上的關系 R (a, b), (b, c),(c, a) ，則 R 等于什么？（ R =(a, a), (b, b), (c, c), (a, b), (a, c), (b, a)(b, c), (c, a), (c, b)）2( n 2 n ) / 2 2(n n) / 22）3設 X 是集合，Xn，則

2、反自反或對稱的關系有多少？（ 2n2 n4. 設A1 , A2 ,L, An 是集合 A 的劃分，若 Ai I B ，1 i n ，則 A I B 的劃分是什么？（ A1B ）5.集合 A 1, 2, 3, 4, 6,12上的整除關系“|”是 A 上偏序關系，畫出 Hasse 圖。（）6.什么是無窮集合？（凡能與自身真子集對等的集合都稱為無窮集合 ）7.設G 為 p 階簡單無向圖， p 2 且 p 為奇數， G 和G 的補圖Gc 中度數為奇數的頂點的個數是否一定相等？（ 一定）8.已知 p 階簡單無向圖G 中有q 條邊，各頂點的度數均為 3，又2 p q 3 ，則圖G 在同構的意義下是否唯一？

3、9. 若G 是一個( p, q) 連通圖，則G 至少有多少個圈？（不唯一）-p+1 ）第 1 頁 （共 7 頁）題號一二三四總分分數學號試 題：班號：10. 設 是一個有 個葉子的二元樹，出度為 2 的頂點為 ，則 與滿足什么關系？（n0=n2+1）二、簡答下列問題(本題滿分 30 分，1-6 小題 3 分，7-9 小題 4 分)1設 是集合，則 充分必要條件是什么？說明理由。（3 分）： 。2設 ，則 與 滿足什么關系？說明理 由。解解：相相相等等等。 =( ()（ () 。3. 寫出無向樹的特征性質（至少 5 個）。（3 分）（11）G 是樹；（22）G 的任兩個不同頂點間有唯一的一條路聯(lián)

4、結；（33）G 是連通的且 p=q+1；（44）G 中無回路且 p=q+1；（55）G 中無回路且一條邊，得到有唯一回路的圖；（66）G 是連通的，并且若 p3，則 G 不不是是是 Kppp。又若 G 的任兩個不鄰接的頂點間加一條邊，則得到一個恰有唯一的一個回路的圖；（77）G 是極小連通圖。4設 是一個 圖，若 ，則 與 哪個 正確？說明理由。（3 分）： 。5. 是否是可平面圖？說明理由。（3 分）解： 不是平面圖。若 是可平面圖，則由公式成立有，510f2，即 f 7。第 頁 （共 頁）試 題：班號：而每個面至少 3 條邊，所以 3f2q ，從而 2120，。因此， 不是可平面圖。6.已

5、知有向圖 的鄰接矩陣 ，則（3 分 ）（1）畫出鄰接矩陣為 的有向圖 的圖解；（2）寫出 的可達矩陣 ；（3）寫出計算兩頂點之間長為 的有向通道條數的計算方法。（2） （1）（3） 。7每個自補圖有多少個頂點？說明理由。（4 分）解：每個自補圖都有或 個頂點因為每個自補圖 的對應的完全圖的邊數必為偶數，即 為偶數。而 當 時，圖 無自補圖，只有 時，圖 才有自補圖。于是 可寫成如下形式 ： ，其中 為正整數；代入 中，只有 才 能使 q為偶數，故每個自補圖必有或 個頂點。8. 設 ，試構造兩 個 和 ： ，使得 但 。（4 分 ）解： 。9設 ，令 在 中的余集 ，則（4 分 ）（1）當 是單

6、射時，給出 和 之間的關系，并給予證明 。（2）當 是滿射時，給出 和 之間的關系，并給予證明 。（1）、（2）任選一種情況證明即可第 頁 （共 頁）試 題：班號：解: 由定理知， = 。若 是滿射，即 ，有 。若 是單射時，有 。因為 ，故存在 ，使得 ，從而 ；由 是單射， 有）， 即 。于是 （否則存在 ，使 。三、證明下列各題（本題滿分 60 分，每小題各 6 分）1設 是兩個集合， ，試證：若 ，則 。證： ，因為 ，故在 B 中任取一元素 y，必有 ，因 而 ，故 。從而 。反之， ，因為 ，故在 中任取一元素 y，必有 ，因 而 ，故 。從而 。于是 。2.設 ，證明： 是單射

7、。證： ，則 ，于是 中必存在 ，使 得 。因為 是單射，故必有 。即 ，所 以 。反過來， ，從而有 ，所以 。因此 。 假設 不是單射，則 ，但 。令 ，于是 ，即 ，。因此， 為單射。第 頁 （共 頁）試 題：班號：3設 是 上的一個自反關系，證明： 是等價關系 若 且 ，則 。證： 是 上的等價關系。若 且 ，由 的對稱性有： 且 ，由 的傳遞性有： 。 R 是自反的，故 有 。若 ，由 有 ，所以 是對稱 的。若 且 ，由 的對稱性有 ： 且 ，故由題意得 ，所以 是傳 遞。因此， 是 上的等價關系。4. 設 是 上的二元關系，證明： 是傳遞的 。 ，則 ，使得 且 ，由 R 的傳遞

8、 性知： ，于是 。 且 ，有 ，故 R 是傳遞 的。55.令 ， 利用康托對 角證明 S 是不可數集。證:假設從 N 到0, 1的所有之集可數，則可排成無重復項的無窮序列。每個函數 確定了一個 0,1 序列 。構造序 列 ，若 ；否則 。該序列對應的函數 ， ， 不為 任一個，6. 設 。 個頂點的圖。若對 的任兩個不鄰接的頂點 和 ，有 ，證明： 是連通的 。第 頁 （共 頁）試 題：班號：證:若 不連通，則 至少有兩個支。設 是其中的一個支，其他各支的子圖為 ， ，則任意 ，有 。于是， 。這與假設相，所以 G 是連通的。7. 證明：完全圖 中至少存在彼此無公共邊的兩條圈和一條路。證：在

9、 中， ，由定理可知，必有一 條回路 ；令為 中刪除 中全部邊之后的圖，則 中每個頂點的度均為 ，故 仍 為圖，因而存在 中的回路 ，顯然 與 無公共邊。再設 為 中刪除中的全部邊后所得圖，則 每個頂點的度均為 。又由定理可知 為 半圖，因而 中存在路。設 為 中的一條路，顯然 無公共邊。8. 設 是一棵樹且( ) ，證明： 中至少有 個度為 1 的頂點。證證：設 中中有 個頂點， 個樹葉，則 中其余 個頂點的度數均大于等等于 2，且至少有一個頂點的度大于等于 。由握手手手定理： ，有 。所以 中至少有 個樹葉 。9. 證明：一個沒有有向圈的有向圖中至少有一個入度為零的頂點。 中任一條最長的有向路的第證：設 D=(V,A)是一個沒有有向回路的有向圖。一個頂點 v，則 id(v)=0。因為若 id(v)0，則必有一個頂點 u 使得(u,v)A。于是，若 u 不在此最長，則此最長路便不是 中的最長路，這是與前面的假設相。若 u 在此最長，則 D 中有有向回路，這與定理的假設。因此 id(v)=0。10. 設 是一個沒有三角形的平面圖，證明： 是 4-可的證：（1）假設 ， ，則由握手定理有： ；由于第 頁 （共 頁）試 題：班號：三角形的平面圖，故 ，即 ，頂點 ，使得 。 (2)對頂點 進行歸納。當 時，顯示成立。故假設不成立，即 中存在一