【正文】 證明： ① ② ①③ ④ ③⑤ ②④⑥ ⑦ ⑥⑧ ③⑦⑩ ⑤⑧⒒ ⑩5. (10分) 設(shè)是連通簡單圖，其中每個頂點的度數(shù)都是偶數(shù)，則對于任一頂點，圖的連通分支數(shù)小于等于的度數(shù)的一半。證明：由于中每個頂點的度數(shù)都是偶數(shù)，所以中奇頂點的數(shù)目等于的度數(shù)，并且在中與相鄰，其余的頂點的度數(shù)仍為偶數(shù)。由于是連通的，所以的每個連通分支中都有原來在中與相鄰的頂點。然而，的每個連通分支都可以看作是一個完整的圖，所以每個分支中原來與相鄰的頂點至少有兩個，并且不同的連通分支中沒有公共的奇頂點，所以的連通分支數(shù)小于等于奇頂點數(shù)目的一半，也就是的度數(shù)的一半。6．設(shè)是格，其中是45的所有正因數(shù)的集合，是上的整除關(guān)系，則 (1) 求每個元素的余元素； (2) 是否為有余格，是否為分配格？并說明理由。解：(1)，1與45與9互為余元素；3與15不存在余元素。(2) 因為3與15不存在余元素，所以不是有余格。 因為中不存在與五元素格同構(gòu)的子格，所以是分配格。蘭2紅3 白4白 5蘭6紅7紅 17．洛杉磯地區(qū)有7家汽車旅游公司，在一天中每家公司最多參觀下列景點中的三個不同景點，這些景點是好萊塢、貝弗利山、迪斯尼樂園和通用電影制片廠，同一天中，參觀一個景點的旅游公司不能超過一個，第一家旅游公司只參觀好萊塢，第二家公司只參觀好萊塢和迪斯尼樂園，第三家公司只參觀通用電影制片廠，第四家只參觀迪斯尼樂園和通用電影制片廠，第五家只參觀好萊塢和貝弗利山，第六家只參觀貝弗利山和通用電影制片廠，第七家只參觀迪斯尼樂園和貝弗利山。請問這些游覽可以只安排在星期一、星期三和星期五嗎？解：在平面上畫七個點分別表示七家旅游公司，如果兩家公司參觀同一個景點，則在這兩家公司所對應(yīng)的頂點之間連一條邊，從而得到一個無向圖，現(xiàn)對該圖的頂點著色，如圖所示，用了三種顏色，所以這些游覽可以只安排在三天里，星期一安排第二家和第六家；星期三安排第一家、第三家和第七家；星期五安排第四家和第五家。8．設(shè)、是命題公式，試用兩種方法分別證明等價式：。證明：等價演算法：真值表法：1101001010110101000011009．設(shè)是非空集合上的二元關(guān)系，若是自反的，證明：是自反的。證明：因為是自反的，所以，又，則，所以是自反的。10. 設(shè)為實數(shù)集，：，對任意的，令，證明：是滿射，并說明不是單射。證明：對任意的，存在，使得，所以是滿射。由于，而，所以不是單射。11. 證明：任一序集都是格。證明：設(shè)是序集，對任意的，則或，于是 (1) 若，因為，所以是與的下界，是與的上界。設(shè)是與的任一下界，則，所以是與的最大下界。設(shè)是與的任一上界，則，所以是與的最小上界。 (2) 若，同理可證，是與的最大下界，是與的最小上界。所以是格。12. 求帶權(quán)1，2，3，4，5，6，7，8，9，10的最優(yōu)二叉樹。解：2113. 設(shè)和都是群的子群，令，證明是的子群的充要條件是。證明：必要性。對任意的，因為是的子群，所以，不妨令，從而有所以。 對任意的，有因為，和都是的子群，所以，，所以，綜上有。 充分性。對任意的，則有而，因為，故，不妨令，則有由子群判定定理，是的子群。14. 設(shè)為實數(shù)集，：，對任意的，令，證明：是滿射，并說明不是單射。證明：對任意的，存在，使得，所以是滿射。由于，而，所以不是單射。15．設(shè)、是命題公式，試用兩種方法分別證明等價式：。證明：等價演算法：真值表法：11010010101101010000110016. 證明：三個元素以上的鏈不是有余格。證明：設(shè)是鏈，則是格。假設(shè)是有余格，則中每個元素都存在余元素，因為0與1互為余元素，而中至少有三個元素，設(shè)，且，的余元素為，由于是鏈，則或，于是(1) 若，則有，又的余余元素為，有，與矛盾。(2) 若，則有，又的余余元素為，有，與矛盾。所以不是有余格。17. 求帶權(quán)1，2，3，4，5，6，7，8，9，10的最優(yōu)二叉樹。解：2118．設(shè)是非空集合上的二元關(guān)系，若是自反的，證明：是自反的。證明：因為是自反的，則，而，所以，故是自反的。19. 設(shè)，其中是整數(shù)集合，證明：是整環(huán)，其中運算“+”和“ ”是關(guān)于數(shù)的普通加法和乘法。證明：(1)對任意的，(其中)，有所以運算“+”和“ ”在上是封閉的。(2)顯然運算“+”和“ ” 在上滿足交換性、結(jié)合性；運算“ ”對“+”滿足分配性；運算“ ” 滿足消去律。(3)關(guān)于運算“+”的幺元。(4)關(guān)于運算“ ”的幺元。(5)對任意的(其中)，關(guān)于運算“+”的逆元為。20．(10分)用推理規(guī)則證明：。證明： (1) (附加前提) (2) (1) (3) (4) (2)(3) (5) (4) (6) (5) (7) (8) (6)(7) (9) 21. (20分) 設(shè)是含幺環(huán),且*滿足等冪律,在上定義運算+,,ˉ如下:, , 證明:是一個布爾代數(shù)，其中0和1分別是關(guān)于運算和*的幺元。證明：(1) 由題設(shè)條件可知，運算+和在上是封閉的。(2) 對任意的，由書上習題結(jié)論，有 從而有 即，運算+和在上是可交換的。(3) 對任意的，有 即所以運算對+是可分配的。另外即所以運算+對是可分配的。(4) 對任意的，有 (5) 對任意的，有綜上，由亨廷頓公理，是布爾代數(shù)。22. (15分)證明：在中任意刪去條邊后所得到的圖是哈密爾頓圖。證明：設(shè)是在中任意刪去條邊后所得到的圖，是中任意兩個不相鄰的頂點，則在中都關(guān)聯(lián)著條邊，現(xiàn)由于刪去條邊，設(shè)其中有條所關(guān)聯(lián)的邊，條所關(guān)聯(lián)的邊，于是，則因為總共刪去條邊，所以，則因此是哈密爾頓圖。23．(5分) Gladbrook飼料公司有7個谷物箱，要通過谷物管道將它們連接起來，以使谷物能從任意一個箱子轉(zhuǎn)移到其它箱子，為了使建造費用最少，希望建造盡可能少的管道，在兩個箱子之間建造管道的費用(以10萬美元計)由下表給出，其中“”表示不能建造管道，應(yīng)該怎樣建造管道才能使費用最少。12345671462325231372244151627 5 1 7 2 4 6 3或者 6 4 2 7 1 5 324．(15分)給定群，其中，是上的模6加法運算，試求： (1) 的所有生成元； (2) 的所有子群； (3) 每個子群的所有右陪集。解：(1) ，所以的所有生成元為，即1，5。(2) ，(3) ，，，，25. (5分)設(shè)集合，是上的二元關(guān)系，試求的關(guān)系圖與關(guān)系矩陣。解：關(guān)系矩陣為關(guān)系圖為： 工aaaaaaaaaaa 26. (5分)設(shè)集合，是上的二元關(guān)系，試求的關(guān)系圖與關(guān)系矩陣。工aaaaaaaaaaa解：關(guān)系矩陣為關(guān)系圖為：27. (15分)給定群，其中，是上的模15加法運算，試求： (1) 的所有生成元； (2) 的所有子群； (3) 每個子群的所有右陪集。解：(1) ，所以的所有生成元為即(2) ，(3) ，，…，，28．(5分)試用克魯斯卡爾算法求下列表格所確定的權(quán)圖的最小支撐樹。/47914632007695283479/96615676663011463966/837998126720071567837/121317246956669981213/41228330112671724412/29．(15分)證明：如果是一個具有奇數(shù)個頂點的偶圖，則不是哈密爾頓圖。證明：因為是偶圖，不妨設(shè)，且中任意兩個相鄰的頂點，必是一個取自于，另一個取自于，由于是奇數(shù)，而所以，不妨設(shè)，現(xiàn)在中刪除中所有的頂點，所得的子圖恰好是中所有的頂點，且都是孤立的頂點，所以，因此不是哈密爾頓圖。30．(10分)用推理規(guī)則證明：，證明：(1) (附加前提) (2) (3) (2) (4) (1)(3) (5) (6) (5) (7) (4)(6) (8) 31．(20分) 設(shè)是一個布爾代數(shù)，在上定義運算*，如下：，證明: 是含幺交換環(huán)。證明：因為是布爾代數(shù)，所以運算具有交換性、結(jié)合性以及分配性，1是最大元，0是最小元，則(1) 由運算*，的定義，顯然運算*，在上是封閉的。(2) 由運算的定義，顯然運算具有交換性和結(jié)合性。(3) 因為1是最大元，則對任意的，有，所以1是關(guān)于運算的幺元。(4) 對任意的，有所以運算*具有交換性。(5) 對任意的，有 同理可證，所以，因此運算*具有結(jié)合性。(6) 因為0是最小元，則對任意的，有所以0是關(guān)于運算*的幺元。(7) 對任意的，存在，有所以對于每個元素，關(guān)于運算*存在逆元。(8) 對任意的，有 所以，即運算對*滿足分配律。 綜上， 是含幺交換環(huán)。59