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