課后習(xí)題答案

1、部分習(xí)題答案及提示第1章1.1答案1 判斷下列語(yǔ)句是否為命題，若是，指出其真值。（1） 外面下雨嗎？ （否）（2） 7能被2 整除。（是，0）（3） 2x+3<4。 （否）（4） 請(qǐng)關(guān)上門。 （否）（5） 小紅在教室里。（是，視小紅是否在教室而定）2 指出下列命題是原子命題還是復(fù)合命題。（1） 小李一邊看書，一邊聽音樂。（復(fù)合命題）（2） 北京不是中國(guó)的首都。（復(fù)合命題）（3） 大雁北回，春天來(lái)了。（復(fù)合命題）（4） 不是東風(fēng)壓倒西風(fēng)，就是西風(fēng)壓倒東風(fēng)。（復(fù)合命題）（5） 張三與李四在吵架。（原子命題）1.2答案1指出下列命題的真值（1） 若2+2>4，則太陽(yáng)從西方升起。（1）（2

2、） 若a，則aA。 （1）（3） 胎生動(dòng)物當(dāng)且僅當(dāng)是哺乳動(dòng)物。 （0）（4） 指南針永指北方，除非它旁邊有磁鐵。（1）（5） 除非ABCD 是平行四邊形,否則它的對(duì)邊不都平行。（1）2令P：天氣好。Q：我去公園。請(qǐng)將下列命題符號(hào)化。（1） 如果天氣好，我就去公園。（PQ）（2） 只要天氣好，我就去公園。（PQ）（3） 只有天氣好，我才去公園。（QP）（4） 我去公園，僅當(dāng)天氣好。 （QP）（5） 或者天氣好，或者我去公園。（PQ）(6) 天氣好，我去公園。（PQ）1.3 答案：1（1）（2）是，其余都不是。2（1）（2）（3）（4）或（5）（6）（7）（8）（9）（10）1.4答案：1（1）0

3、00001010011100101110111111101110000100111010110111110000101111101111111（2）000001010011100101110111110111110001100111010000111110011101111100111111（3）0001101110010011111011100010001101101011（4）00011011100100011110101000100010011100012略3甲4上海申花第一，北京國(guó)安第二，大連實(shí)德第三，長(zhǎng)春亞泰第四。5否，否，是6（1）R (2) T (3) 1.5 答案：1（1）重言

4、式（2）可滿足式（3）重言式（4）重言式3（1）（2）（3）（4）假；（5）（6）（7）（8）真4（1）表示命題：如果8是偶數(shù)，則糖是甜的。（2）：如果糖是甜的，則8是偶數(shù)。（3）：如果8不是偶數(shù)，則糖不是甜的。（4）：如果糖不是甜的，則8不是偶數(shù)。5敘述下列各個(gè)命題的逆換式和逆反式，并以符號(hào)寫出。（1）設(shè)：天下雨。：我將留下。則原命題為； 其逆換式為：；其逆反式為：。（2）設(shè)：你走。：我不去。則原命題為； 其逆換式為：；其逆反式為：。（3）設(shè)：我不能獲得更多幫助。：我不能完成這個(gè)任務(wù)。則原命題為； 其逆換式為：；其逆反式為：。6檢驗(yàn)下列論證的有效性。如果我學(xué)習(xí)（），那么我數(shù)學(xué)不會(huì)不及格（）。

5、 如果我不熱衷于玩撲克（），那么我將學(xué)習(xí)。 但我數(shù)學(xué)不及格。 因此，我熱衷于玩撲克。 7用符號(hào)寫出下列各式并且驗(yàn)證論證的有效性。如果6是偶數(shù)（），則7被2除不盡（）。 或5 不是素?cái)?shù)，或7被2除盡。 但5是素?cái)?shù)（）。 所以6是奇數(shù)。 8 略1.6答案：1（1）（2） （3）2（1）（2）（3）1.7答案：1（1） （2）（3） （4）2（1） （2）3（1）析取范式；合取范式（2）析取范式；合取范式（3）析取范式；合取范式（4）析取范式；合取范式4（1）（2）（3）（4）50；16（1）主析取范式：(PQR)(PQR)(PQR)(PQR)(PQR) ；主合取范式：，(PQR)(PQR)(PQR

6、) （2）主析取范式：（PÙQ）Ú（QÙP） 主合取范式：(PQ)(PQ) （3）主析取范式： 主合取范式：=7（1）重言式（2）矛盾式（3）可滿足式（4）可滿足式8有三種選派方案：去，而、都不去；去，而、都不去；、都去，而不去.9（1）等價(jià)（2）不等價(jià)1.8答案：1證明證明：2用間接方法證明證明：3設(shè)如果2是偶數(shù)（），則3是奇數(shù)（）；或者2是偶數(shù)或者2整除3 （）；結(jié)果2不整除3。所以3 是奇數(shù)。 上述論斷符號(hào)化為：，。4某公司若拒絕增加工資，則罷工不會(huì)停止，除非罷工超過一年并且公司經(jīng)理辭職，問：如果公司拒絕增加工資，而罷工又剛剛開始，罷工是否會(huì)停止？5“如果下

7、雨，春游就會(huì)改期；如果沒有球賽，春游就不會(huì)改期。結(jié)果沒有球賽，所以沒有下雨?！弊C明上述論斷正確。6如果考試及格，那我高興。若我高興，那么我飯量增加。我的飯量沒增加，所以我考試沒有及格。試對(duì)上述論證構(gòu)造證明。7證明 RÚS是前提CÚD，CR，DS的有效結(jié)論。8證明PQ , Q®R, P®S , S Þ R(QP)9證明：(ABÚC)Ù(BA)Ù(DC) Þ (AD)第2 章2.1答案1（1） 其中，：是工人。 ：小王（2） 其中，：是田徑運(yùn)動(dòng)員。 ：是球類運(yùn)動(dòng)員。：他（3）其中，：聰明。 ：漂亮。：小麗（4

8、）其中，：是奇數(shù)。 ：， ：2（5）其中，：是有理數(shù)。 ：是實(shí)數(shù)。 （6）其中，：是函數(shù)。 ：是連續(xù)的。2.2 答案：1（1），其中：是自然數(shù)。：比大。（2）或，其中：是鳥。：能飛。（3）或，其中：是麒麟。：是動(dòng)物。（4）或，其中：是數(shù)。：是有理的。2令是人。（特性謂詞）（1）令為長(zhǎng)頭發(fā)。則符號(hào)化為：（2）令吸煙。則符號(hào)化為：（3）令登上過木星。則符號(hào)化為：（4令是清華大學(xué)的學(xué)生。是高素質(zhì)的。則符號(hào)化為：3（1），其中：是人。：是的外祖父。：是的父親。：是的母親。（2），其中：是人。：聰明。2.4 答案：1（1）（2）（3）2不正確，第三步的“”應(yīng)為 “”。3都成立2.5 答案：1（1）（2）

9、（3）（4） 2.6答案：2（1）任何人如果他喜歡步行，他就不喜歡乘汽車。每個(gè)人或者喜歡乘汽車或者喜歡騎自行車。有的人不愛騎自行車，因而有的人不愛步行。（設(shè)：喜歡步行，：喜歡乘汽車，：騎自行車） 該命題符號(hào)化為：證: (1) P (6) P (2) ES (1) (7) US (6) (3) P (8) T(5),(7) I (4) US (3) (9) EG(8) (5) T(2)(4) I （）某學(xué)術(shù)會(huì)議的每個(gè)成員都是專家并且是工人，有些成員是青年人，所以，有些成員是青年專家。（3）所有有理數(shù)是實(shí)數(shù)，某些有理數(shù)是整數(shù)，因此某些實(shí)數(shù)是整數(shù)（設(shè)：是有理數(shù)，：是實(shí)數(shù)，：是整數(shù)） 該命題符號(hào)化為：

10、（2分）證: (1) P (6) T(2) I （1分） (2) ES (1) （1分） (7) T(4),(5) I （1分） (3) P (8) T(6),(7) I （1分） (4) US (3) （1分）(9) EG(8) （1分） (5) T(2) I (4) 每個(gè)大學(xué)生不是文科生就是理科生，有的大學(xué)生是優(yōu)等生，小張不是理科生，但他是優(yōu)等生，因而如果小張是大學(xué)生，他就是文科生。第3章3.11 （1）； （2）； （3）； （4）2（1）； (2) ；無(wú)限集 (3) 3 （1）真； （2）假； （3）真； （4）真； （5）真； （6）假； （7）真； （8）真4 （1）是； （2）否

11、； （3）否； （4）否5 （1）假； （2）假； （3）假； （4）假； （5）真； （6）真； （7）假； （8）假； （9）假6 （1）； （2）； （3）； （4）； （5）7(1) 1）是，是； 2）是，是； 3）是，是； (2) 1）是，是，是，是； 2）是，否，否，是。8， ，3.41 (1) ；(2) ； 3 (1) 否； (2) 是； (3) 是； (4) 去掉；(5) 是； (6) 否； (7) 否； (8) 否； (9) 否；(10) 否 3.51 (1)， (2) ，2，34 3.61（1） 自反性、對(duì)稱性和傳遞性； （2）自反性、對(duì)稱性和傳遞性；（3）自反性、對(duì)稱性和

12、傳遞性；2 的給出證明，對(duì)每一個(gè)非的給出反例。 自反的反自反的對(duì)稱的反對(duì)稱的傳遞的3，是，不是，因?yàn)?但； 不是，因?yàn)?但。4， 5設(shè)，上的關(guān)系的關(guān)系矩陣如下，試問是不是自反的、反自反的、對(duì)稱的、反對(duì)稱的和傳遞的？（1）反自反的、反對(duì)稱的； （2）不具有任何性質(zhì)； （3）自反的、反對(duì)稱的；（4）自反的、對(duì)稱的 （5）自反的、傳遞的6（1） （2） （3） ？ （4）第4章4.11指出下列各關(guān)系是否為到的函數(shù)：（1）否 （2）是（3），是，否（4）是，是，否，否。3，4，4.21設(shè)分別表示正整數(shù)集、整數(shù)集、實(shí)數(shù)集、復(fù)數(shù)集，試指出下列映射中哪些是單射、滿射、雙射，并寫出定義域和值域。(1) 非單射

13、，非滿射， (2) 非單射，非滿射， (3) 非單射，滿射， (4) 單射 (5) 非單射，非滿射，（6）雙射，2（1）否， （2）是， (3) 否。3（1）能， （2）能， （3）不能，（4）能，第5章習(xí)題5.11（1）封閉 （2）封閉 （3）封閉 （4） 不封閉 （5）不封閉2 是否封閉集 合運(yùn) 算 是 是 是 是 是 是 是是 否 是 否 是 是 是是 否 是 是 是 是 是否 否 否 是 是 是 是否 否 否 否 是 是 是是 是 是 是 是 是 是3（1）否，乘法運(yùn)算在上不封閉（2）否，乘法運(yùn)算在上不封閉（3）是（4）是4（1）否 （2）是 （3）是5（1) 是 （2) 否 （3)

14、是6（1）否 （2）是7. 7個(gè)8 運(yùn)算表 運(yùn)算表 1 2 3 4 1 2 3 41 234 0 0 0 01 2 3 42 4 6 83 6 9 121 2341 2 3 42 2 3 43 3 3 44 4 4 49 0 1 2 3 4 5 6 0 1 2 3 4 5 60123456 0 1 2 3 4 5 61 2 3 4 5 6 02 3 4 5 6 0 13 4 5 6 0 1 2 4 5 6 0 1 2 3 5 6 0 1 2 3 4 6 0 1 2 3 4 5 0123456 0 0 0 0 0 0 00 1 2 3 4 5 60 2 4 6 1 3 50 3 6 2 5 1

15、40 4 1 5 2 6 30 5 3 1 6 4 20 6 5 4 3 2 110證 對(duì)于，由于所以，是上的代數(shù)運(yùn)算，因而是代數(shù)系統(tǒng)。習(xí)題5.21(1)可交換，不冪等，有幺元，每元均可逆：；(2) 不可交換，不冪等，有幺元，有左零元，可逆：，不可逆，但；(3) 不可交換，冪等，有左幺元：，有右零元：； (4)不可交換，不冪等，有左幺元：；2（1）不可結(jié)合，不可交換，無(wú)幺元，無(wú)零元，任何元素均無(wú)逆元。（2）可結(jié)合，可交換，有幺元0，有零元1，其它元素均無(wú)逆元。（3）可結(jié)合，可交換，有幺元0，有零元1，當(dāng)時(shí)，無(wú)逆元。（4）不可結(jié)合，可交換，有無(wú)幺元，無(wú)零元，任何元素均無(wú)逆元。（5）可結(jié)合，不可交

16、換，無(wú)幺元，無(wú)零元，任何元素均無(wú)逆元。（6）不可結(jié)合，可交換，無(wú)幺元，無(wú)零元，任何元素均無(wú)逆元。3 運(yùn) 算 可結(jié)合性可交換性存在幺元存在零元是 否 是 否 是 是 是 否 是 是 是 是 是 否 是 否 否 否 否 否 是 否 否 否 4 （1）上函數(shù)復(fù)合運(yùn)算的運(yùn)算表為： （2）是的幺元，無(wú)零元。（3）和有逆元，且5提示：對(duì)一切，記，由于是集合上的可結(jié)合的二元運(yùn)算，所以，故由題設(shè)有。6證明：，因?yàn)?，所?而 故 即“”對(duì)“+”是左可分配的。又因?yàn)?而 故 即“”對(duì)“+”是右可分配的。因此，“”對(duì)“+”是可分配的。7（1）滿足冪等律 （2）滿足冪等律 （3）不滿足冪等律習(xí)題5.3 1 不是半群，

17、因?yàn)檫\(yùn)算“”不滿足結(jié)合律)。2（2）、（4）和（5）的是半群。3證明：(1) 對(duì)封閉。因?yàn)槭前肴?，?(2) 具有結(jié)合律。因?yàn)椋簩?duì)， (是半群，具有結(jié)合律)所以具有結(jié)合律。故還是半群。5 是一個(gè)獨(dú)異點(diǎn)，因?yàn)殛P(guān)系的復(fù)合運(yùn)算“”是封閉、可結(jié)合的，且恒等映射是其幺元。它可交換。6（1）17，-32，14.5 。 2）是半群，可交換。 （3）0。 （4）當(dāng)時(shí)，有逆元素，。10提示：的幺元是4，而的幺元是1，且1。11（2）和都是獨(dú)異點(diǎn)，是的子獨(dú)異點(diǎn)，但不是的子獨(dú)異點(diǎn)。12（1）是半群。（2）的左幺元為，右幺元為。無(wú)左幺元，右幺元為。的左幺元為，右幺元為。的左幺元為，右幺元為。無(wú)左、右幺元。無(wú)左幺元，右

18、幺元為。的左幺元為，無(wú)右幺元。（3）左、右零元均為。其它的均無(wú)左、右零元。習(xí)題5.4 1 是群，因?yàn)檫\(yùn)算“”是封閉、可結(jié)合的，有幺元2，且有逆元，。2只有（1）的是群，其幺元是2，元素的逆元是。8提示：關(guān)于矩陣乘法滿足封閉性，且矩陣乘法具有結(jié)合律，幺元是，而每元的逆元均為自身。9提示：關(guān)于映射的復(fù)合運(yùn)算的運(yùn)算表為： 從該運(yùn)算表可知，運(yùn)算封閉，有幺元， ，；而映射復(fù)合是可結(jié)合的，所以關(guān)于映射的復(fù)合運(yùn)算構(gòu)成群。10提示：(1)設(shè)是的子群。 ，由的定義及，都是子群，并從得 ，即；，由是子群知，又由，都是子群，得，所以 ，即；所以。 （2）設(shè)。 對(duì)，有，使得并且 (結(jié)合律) 是子群) （） （結(jié)合律）

19、 即知是子群。11提示：因?yàn)榉强涨覍?duì)，都有，故是的子群。 12提示：既然在左幺元下，都有，使，當(dāng)然對(duì)，存在，滿足。于是 且對(duì)，有 可見，是的幺元，均有逆元。這就是說(shuō)是群。 習(xí)題5.5 3 是Abel群，而不是Abel群。5提示：因?yàn)槭欠茿bel群，必存在使得，這時(shí)有，令，則，且。6 的運(yùn)算表如下表所示。 1 3 4 5 913459 1 3 4 5 93 9 1 4 54 1 5 9 35 4 9 3 19 5 3 1 4從運(yùn)算表可知，在上封閉、有幺元1，且，再由是可結(jié)合的得是循環(huán)群，3，4，5和9均為其生成元。7提示：是，生成元有兩個(gè)：和。 8提示：設(shè)，則即為的唯一d階子群。習(xí)題5.6 1是

20、。因?yàn)槭堑降耐瑯?gòu)映射。2不是到同態(tài)映射，因?yàn)椤?例如：（1）設(shè)， 令，則是到的同態(tài)。的幺元是，但的幺元是；也是到的同態(tài)。的零元是，但的零元是。（2） 6是同構(gòu)映射，因?yàn)槭请p射。7同態(tài)象為或，同態(tài)核為。8 ，當(dāng)均為偶數(shù)或均為奇數(shù)時(shí)，有當(dāng)為一奇一偶時(shí)，有因此f是群的同態(tài)映射。因?yàn)?是的幺元，所以同態(tài)核，同態(tài)像為。9（1）是，因?yàn)椤＃?）不是，因?yàn)椤＃?）是，因?yàn)椤?10提示：是，因?yàn)?，若，則若，則11證明：首先證是入射。，則有其次證是滿射。對(duì)綜合以上兩點(diǎn)，知是雙射。 14證明：因?yàn)?，所以存在，使得。?duì)，若，即，則。由于是有限群，于是，因而，即。所以是單射。又因?yàn)槭怯邢奕?，所以是雙射。對(duì)于，即保持運(yùn)

21、算。因此，是上的自同構(gòu)映射。15證明：假設(shè)群和群同構(gòu)，同構(gòu)映射為，則,于是，從而，故不是雙射，與是同構(gòu)映射矛盾。所以，群和群不同構(gòu)。習(xí)題5.7 1 是Abel群，故其任一元素關(guān)于的左、右陪集均相等。 故對(duì)任何非零復(fù)數(shù)，它是復(fù)平面上以原點(diǎn)為圓心，為半徑的圓。2 1階子群有0，其陪集為0，1，2，3，4，5。2階子群有0，3，其陪集為0，3，1，4，2，5。3階子群有0，2，4，其陪集為0，2，4，1，3，5。 6階子群有，其陪集為。3 的左陪集共有個(gè)，它們分別是：。4的全部陪集是：，其中是過點(diǎn)以為斜率的直線，因此，的全部陪集是以為斜率的平行直線簇。 5提示：，是子群。但其它的左陪集中均不含，故都

22、不是子群。右陪集的情形一樣。6提示：首先證明：(1) ；(2) 對(duì)運(yùn)算“”封閉，且當(dāng)時(shí)，。然后用子群判定命題。7提示：由于左、右陪集集是的劃分，故存在使。 下證，即可。事實(shí)上，若，則。 若，則存在使，故(否則，由，得到，矛盾!)。習(xí)題5.8 1是3（1）不是環(huán)，因?yàn)槌?外，每個(gè)元素均無(wú)加法逆元。（2）不是環(huán)，因?yàn)榧臃ú环忾]。（3）是交換環(huán)、無(wú)零因子環(huán)，不是含幺環(huán)，不是整環(huán)。（4）不是環(huán)，因?yàn)槌朔ú环忾]。（5）是整環(huán)。（6）不是環(huán)，因?yàn)槌朔ú环忾]。6（1）（5）不是域，（6）（7）是域。習(xí)題6.11解 是格。不是格，因?yàn)椴淮嬖?。不是格，因?yàn)椴淮嬖凇２皇歉?，因?yàn)椴淮嬖凇?不是格，因?yàn)?，3無(wú)下確界

23、。3解 (1)是偏序集。 其哈斯圖為：(2)是格因?yàn)槠淙我鈨蓚€(gè)元素都有上確界（的最小公倍數(shù)）和下確界（的最大公約數(shù)）4解 是格，是的子格。5解 由于，的哈斯圖如下圖所示。根據(jù)子格的充要條件知，的所有子格分別為：1個(gè)元素的子格：1，2，3，6。2個(gè)元素的子格：1，2，1，3 1，6，2，6，3，6。3個(gè)元素的子格：1，2，6，1，3，64個(gè)元素的子格：.8答案：是格，因?yàn)椤?證明 設(shè)是一個(gè)格。若，則是一條只有一個(gè)點(diǎn)的鏈。若，由于，所以或，進(jìn)而有，于是是一條鏈。若，由于是的最大元，不妨設(shè)為，同時(shí)是的最小元，不妨設(shè)為，于是有，所以是一條鏈。習(xí)題6.21答案：（a）和(c)是分配格。2（是）4分配格：

24、非分配格：習(xí)題6.32答案：（a），(d)和(f)不是有補(bǔ)格。3答案：a與g互補(bǔ)，d與c互補(bǔ)，b和f無(wú)補(bǔ)元。4例如：下圖中的（a）是分配格不是有補(bǔ)格，而（b）是有補(bǔ)格不是分配格。5答案： 它們都不是有補(bǔ)格，它們都是分配格。習(xí)題6.41答案：（b），(e) 和(f) 是布爾代數(shù)。 （a）不是布爾代數(shù)，因?yàn)樗鼪]有個(gè)元素。 (c) 不是布爾代數(shù)，因?yàn)闆]有補(bǔ)元。 (d) 不是布爾代數(shù)，因?yàn)樗皇欠峙涓?。（g） 不是布爾代數(shù)，因?yàn)樗鼪]有個(gè)元素。（h） 不是布爾代數(shù)，因?yàn)闆]有補(bǔ)元。2（1）；（2）；（3）；(4) 。3證明 設(shè)是布爾代數(shù)且，則中存在唯一的異于0和1的元素，由于，所以，故在中不存在補(bǔ)元，這與

25、是布爾代數(shù)矛盾。所以不存在3個(gè)元素的布爾代數(shù)。4證明：（3）若，則。反之，若，則且，于是有，故有。5（7）若，其中是個(gè)不同的素?cái)?shù)，則是布爾代數(shù)。6設(shè)是一個(gè)布爾代數(shù)，上的二元運(yùn)算定義為：證明是一個(gè)Able群。證明：(1) 因?yàn)闉橐徊紶柎鷶?shù)，所以=()()，即關(guān)于 “”封閉。 （2）對(duì)，同理所以“”是可結(jié)合的。 （3）對(duì)， 所以0是，的幺元。（4）對(duì)，所以。（5），綜上，是一個(gè)交換群7設(shè)是一個(gè)布爾代數(shù)，上的二元運(yùn)算定義為：證明是一個(gè)以1為幺元的環(huán)。證明：1.先證是一個(gè)Able群。(1) 因?yàn)闉橐徊紶柎鷶?shù)，所以=()()，即關(guān)于 “+”封閉。（2）對(duì)，同理所以“+”是可結(jié)合的。 （3）對(duì)， 所以0是

26、的幺元。（4）對(duì)，所以。（5），綜上，是一個(gè)交換群2.再證為一個(gè)半群。(1) 因?yàn)闉橐徊紶柎鷶?shù)，所以，即關(guān)于 “”封閉。（2）對(duì)，所以“”是可結(jié)合的。故為一個(gè)半群。3. 證“”對(duì)“+”可分配。對(duì)， 4.又，所以1是的幺元。綜上知是一個(gè)以1為幺元的環(huán)。8證明 由于是同構(gòu)映射，所以。由于，所以。若不是的原子，則存在滿足，由于是同構(gòu)映射，所以存在，使得，又由于，所以，且，因此，這與是原子矛盾。 所以的原子。習(xí)題6.51（1）；（2）；（3）；（4）；（5）；（6）；（7）；（8）。2答案： 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 0 1 0 0 1 1 1

27、1 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 11 0 1 1 1 0 1 13的析取范式為：的合取范式為：4答案：的析取范式為： 的合取范式為：習(xí)題6.61第7章7.1 答案：1（3）不是簡(jiǎn)單圖。3由同構(gòu)定義具體地構(gòu)造同構(gòu)映射可證4（1）16；（2）137.2答案：1（3）3；（4）=24()是強(qiáng)連通圖，()是單側(cè)連通圖，()是弱連通圖5強(qiáng)分圖1，2，3，4，5，6 單側(cè)分圖1，2，3，4，5，6 弱分圖1，2，3，4，5，67.31（1）（2），（3）2200個(gè)34根據(jù)的主對(duì)角線元素是否為0可以判斷是否有經(jīng)過的回路。7.4答案：1不可以，可以2為奇數(shù)3（

28、1）最少加條邊；（2）由（1）即得。4構(gòu)造一個(gè)有9個(gè)結(jié)點(diǎn)、27條邊的具有有向歐拉回路的有向圖。5圖()、圖()是歐拉圖。6沒有。用漢密爾頓圖的必要條件判斷。7（1）一個(gè)結(jié)點(diǎn)的度數(shù)表示其對(duì)應(yīng)的人所認(rèn)識(shí)的人數(shù)。（2）是連通圖表示任意兩個(gè)人可以通過朋友的一次或多次介紹而相互認(rèn)識(shí)。（3）如果中任何一對(duì)結(jié)點(diǎn)的度數(shù)之和都大于等于，則中存在漢密爾頓路。 8設(shè)是的起點(diǎn)為終點(diǎn)為的漢密爾頓路，在中添加連接，的邊，得到一新圖，則此新圖為漢密爾頓圖。再利用定理7.4.3證明。7.51求下面兩個(gè)二部圖的最大匹配。答案：圖的最大匹配為；圖的最大匹配為；2假定是二部圖，如何安排中頂點(diǎn)的次序可使的鄰接矩陣呈 形式，0為零矩陣。3某單位有7個(gè)工作空缺要招聘，有10個(gè)應(yīng)聘者。他們能勝任的工作崗位集合分別為：，。如果規(guī)定每個(gè)應(yīng)聘者最多只能安排一個(gè)工作，試給出一種分配方案使落聘者最少？4設(shè)圖是二部圖，證明。證明：設(shè)，則，。 由，得