離散數(shù)學(xué)答案-(1,2,7章)陳志奎

1、第1章 命題邏輯P7 習(xí)題1. 給出下列命題的否定命題： （1）大連的每條街道都臨海。否命題：不是大連的每條街道都臨海。（2）每一個(gè)素?cái)?shù)都是奇數(shù)。否命題： 并非每一個(gè)素?cái)?shù)都是奇數(shù)。2. 對(duì)下述命題用中文寫出語句：（1）如果非P與R，那么Q。（2）Q并且R。3. 給出命題，我們把、分別稱為命題的逆命題、反命題、逆反命題。（1）如果天不下雨，我將去公園。解：逆命題：如果我去公園，則天不下雨； 反命題：如果天下雨，則我不去公園； 逆反命題：如果我不去公園，則天下雨了。（2）僅當(dāng)你去我才逗留。解：（此題注意：p僅當(dāng)q翻譯成） 逆命題：如果你去，那么我逗留。 反命題：如果我不逗留，那么你沒去。 逆反命題

2、：如果你沒去，那么我不逗留。（3）如果n是大于2的正整數(shù)，那么方程無整數(shù)解。解：逆命題：如果方程無整數(shù)解，那么n是大于2的正整數(shù)。 反命題：如果n不是大于2的正整數(shù)，那么方程有整數(shù)解。 逆反命題：如果方程有整數(shù)解，那么n不是大于2的正整數(shù)。（4）如果我不獲得更多的幫助，那么我不能完成這項(xiàng)任務(wù)。解：逆命題：如果我不完成任務(wù)，那么我不獲得更多的幫助。 反命題：如果我獲得了更多的幫助，那么我能完成任務(wù)。 逆反命題：如果我能完成任務(wù)，那么我獲得了更多的幫助。4. 給P和Q指派真值T，給R和S指派真值F，求出下列命題的真值。（1）=（2）=（3）=（4）=5. 構(gòu)成下來公式的真值表：（1）PQFFFTF

3、TTFTFFTTTTT（2）PQRFFFTFFFFTTFFFTFTFFFTTFTFTFFFTFTFTFTFTTFFTFTTTFTF（3）PQRFFFTFFFFTTFFFTFFFTFTTFFTTFFFTTTFTFFTTTFTTTTTTTFF（4）PQRFFFTTFFTFFFTFTTFTTFFTFFTTTFTFFTTFFTTTTFF6. 使用真值表證明：如果為，那么和都是，反之亦然。證明：PQFFTTTFTFTFTFFFTTTTTT由上表可知：當(dāng)為時(shí)，和都是；和為時(shí)，為。故命題得證。7. 使用真值表證明：對(duì)于和的所有值，與有同樣的真值。PQFFTTFTTTTFFFTTTT8. 一個(gè)有兩個(gè)運(yùn)算對(duì)象的

4、邏輯運(yùn)算符，如果顛倒其運(yùn)算對(duì)象的次序，產(chǎn)生一邏輯等價(jià)命題，則稱此邏輯運(yùn)算符是可交換的。（1）確定所給出的邏輯運(yùn)算符哪些是可交換的：，。（2）用真值表證明你的判斷。解：（1），是可交換的。（2）真值表如下：PQFFFFFFTTTTFTFFTTTFFFTFFFTTFTFFTTTTTTTTTT9.設(shè)是具有兩個(gè)運(yùn)算對(duì)象的邏輯運(yùn)算符，如果和邏輯等價(jià)，那么運(yùn)算符是可結(jié)合的。（1）確定邏輯運(yùn)算符，哪些是可結(jié)合的？（2）用真值表證明你的判斷。解：（1）是可結(jié)合的。 （2）真值表如下：PQRFFFFFFTFFTFTTTFTFFTFTFTTFTTFTFFFTTTTFTFTTFTTFFTFFTTTTTTTPQRFF

5、FFFTTFFTFTTTFTFFTTTFTTFTTFTFFFTTTTFTFTTFTTFFTFFTTTTTTT10. 令表示命題“蘋果是添的”，表示命題“蘋果是紅的”，表示命題“我買蘋果”。試將下列命題符號(hào)化：（1）如果蘋果甜而紅，那么我買蘋果。（2）蘋果不是甜的。（3）我沒買蘋果，因?yàn)樘O果不紅也不甜。解：（1）（2）（3）P15 習(xí)題1. 指出下面命題公式哪些是重言式、永假式或可滿足式。解：（1）重言式（2）永假式（3）重言式（4）重言式 （5）重言式（6）重言式 = （7）重言式 =（8）重言式=（9）重言式 =（10）可滿足式=，當(dāng)為真時(shí)公式為真，為假時(shí)公式為假。故為可滿足式。（11）重言

6、式（12）重言式 （13）可滿足式 的真值表如下：PQFFTTTFTTFFTFFFTTTTTT（14）可滿足式= 當(dāng)或有一個(gè)為真時(shí)公式為真；當(dāng)和均為假時(shí)，若和真值相同時(shí)，公式為真；真值不同時(shí)，公式為假。故公式是可滿足式。2. 寫出與下面給出的公式等價(jià)并且僅含有聯(lián)接詞與的最簡公式。（1）（2）（3）（4）（5）3. 寫出與下面的公式等價(jià)并且僅含聯(lián)結(jié)詞和的最簡公式。（1）（2）（3）4. 使用常用恒等式證明下列各式，并給出下列各式的對(duì)偶式。（1）證明： 對(duì)偶式：（2）證明：對(duì)偶式：（3）證明：對(duì)偶式：5. 試證明下列合式公式是永真式。（1）證明：（2）證明：（3）證明：（4）證明：6. 證明下列蘊(yùn)

7、含式。（1）證明：（2）證明：（3）證明：（4）證明：（5）證明：（6）證明：7. 對(duì)一個(gè)重言式使用代入規(guī)則后仍為一個(gè)重言式，對(duì)一個(gè)可滿足式和一個(gè)矛盾式，使用代入規(guī)則后，結(jié)果如何？對(duì)重言式、可滿足式和矛盾式，使用替換規(guī)則后，結(jié)果如何？解：對(duì)于代入規(guī)則：（1）如果是可滿足式，使用代入規(guī)則后可能是重言式、可滿足式或矛盾式。如：可滿足式，將分別替換為，分別得到重言式和可滿足式，對(duì)于可滿足式，將替換為得到矛盾式。（2）如果是矛盾式，使用代入規(guī)則后仍然是矛盾式。設(shè)是矛盾式，則是重言式。而對(duì)于重言式使用代入規(guī)則后仍為重言式，即是重言式，故是矛盾式。對(duì)于替換規(guī)則：由于替換規(guī)則是一種對(duì)子公式邏輯上等價(jià)的替換，

8、故對(duì)于重言式、可滿足式和矛盾式使用替換規(guī)則后其真值不變。8. 求出下列各式的代入實(shí)例。（1）；用代，用代。解：（2）；用代，用代解：P21 習(xí)題1.求下列各式的主合取范式。（1）解： （2）（3）2.求下列公式的主析取范式和主合取范式：（1）合取范式：析取范式：（2）合取范式：析取范式：（3）合取范式：析取范式：（4）析取范式：合取范式：P25 習(xí)題1.試用真值表法證明：不是,和的有效結(jié)論。解：構(gòu)造真值表如下：A B C D E0 0 0 0 0111000 0 0 0 1110100 0 0 1 0111000 0 0 1 1110100 0 1 0 0110000 0 1 0 111110

9、0 0 1 1 0100000 0 1 1 1101100 1 0 0 0001000 1 0 0 1000100 1 0 1 0001000 1 0 1 1000100 1 1 0 0000000 1 1 0 1001100 1 1 1 0010000 1 1 1 1011101 0 0 0 0010101 0 0 0 1010111 0 0 1 0010101 0 0 1 1010111 0 1 0 0011101 0 1 0 1011111 0 1 1 0001101 0 1 1 1001111 1 0 0 0100101 1 0 0 1100111 1 0 1 0100101 1 0

10、1 1100111 1 1 0 0101101 1 1 0 1101111 1 1 1 0111101 1 1 1 111111第6，31行前提取值均為1時(shí)，結(jié)論為0。故命題得證。2.，和是前提。在下列情況下，試確定結(jié)論C是否有效（可以使用真值表法證明。）（1）證明：真值表如下：P Q0 0110 1111 0001 111第1，2，4行當(dāng)前提取值為1時(shí)，結(jié)論都為1。故結(jié)論C是有效的。（2）證明：1（1）P規(guī)則1（2）T規(guī)則，（1），3（3）P規(guī)則1，3（4）T規(guī)則，（2），（3），5（5）P規(guī)則1，3，5（6）T規(guī)則，（4），（5），結(jié)論C是有效結(jié)論。（3）（4）證明：1（1）P規(guī)則（附加前

11、提）2（2）P規(guī)則1，2（3）T規(guī)則，（1），（2），4（4）P規(guī)則1，2，4（5）T規(guī)則，（3），（4），1，2，4（6）規(guī)則，（1），（5）3.不構(gòu)成真值表證明：不是、和的有效結(jié)論。證明：（1） P規(guī)則 （2） P規(guī)則 （3） T規(guī)則，(1)(2) （4） P規(guī)則 （5） T規(guī)則,(1)(4) （6） T規(guī)則(5) （7） T規(guī)則(3) （8） T規(guī)則(6)(7) （9） T規(guī)則(8)因此，是題目的有效結(jié)論，不是。4.使用推理的方法證明：是和的有效結(jié)論。證明：1（1）P規(guī)則1（2）T規(guī)則，（1），1（3）T規(guī)則，（2），1（4）T規(guī)則，（3），1（5）T規(guī)則，（1），1（6）T規(guī)則，（5）

12、，1（7）T規(guī)則，（6），1（8）T規(guī)則，（4），（7），9（9）P規(guī)則1，9（10）T規(guī)則，（8），（9），5.不構(gòu)成真值表證明下列命題公式不能同時(shí)全為真。（1），證明：1（1）P規(guī)則2（2）P規(guī)則1，2（3）T規(guī)則，（1），（2），4（4）P規(guī)則1，2，4（5）T規(guī)則，（3），（4），6（6）P規(guī)則1，2，4，6（7）T規(guī)則，（5），（6），8（8）P規(guī)則(1，2，4，6，8)（9）T規(guī)則，（7），（8），推出結(jié)論與前提矛盾，因此命題公式不能同時(shí)為真。（2），證明：1（1）P規(guī)則2（2）P規(guī)則1，2（3）T規(guī)則，（1），（2），4（4）P規(guī)則1，2，4（5）T規(guī)則，（3），（4），推出的結(jié)

13、論與命題公式矛盾，因此命題公式不能同時(shí)為真。6. ，和是前提，根據(jù)推理規(guī)則斷定，在下列情況下是否是有效結(jié)論。（1） 證明：1（1）P規(guī)則（假設(shè)前提）2（2）P規(guī)則1，2（3）T規(guī)則，（1），（2），4（4）P規(guī)則1，2，4（5）T規(guī)則，（3），（4），6（6）P規(guī)則1，2，4，6（7）T規(guī)則，（5），（6），1，2，4，6（8）T規(guī)則，（1），（7），1，2，4，6（9）F規(guī)則，（1），（8）因此是有效結(jié)論。（2）證明：因?yàn)椋儆汕疤?，得到、的值任意，即、的值任意。因此不是有效結(jié)論。7.證明下列結(jié)論的有效性。（1），證明：（1）P規(guī)則（2）P規(guī)則（3）T規(guī)則，（1），（2），（4）P規(guī)則（5）

14、T規(guī)則，（4），（6）T規(guī)則，（3），（5），（2），證明：（1） P規(guī)則 （2） P規(guī)則 （3） T規(guī)則（1）（2） （4） P規(guī)則 （5） T規(guī)則（3）（4） （6） T規(guī)則（5）（3），由得R為真，再由得真假任意，故無法推出P一定為真的結(jié)論。（題目有問題）8.導(dǎo)出下列結(jié)論（如果需要，就是用規(guī)則）（1）證明： （1） P P規(guī)則（假設(shè)前提） （2） P規(guī)則 （3） Q T規(guī)則（1）（2） （4） P規(guī)則 （5） R T規(guī)則（3）（4） （6） P規(guī)則 （7） S T規(guī)則（5）（6） （8） CP規(guī)則（1）（7）（2）證明： （1） P P規(guī)則（假設(shè)前提） （2） P規(guī)則 （3） Q T規(guī)則

15、（1）（2） （4） T規(guī)則（1）（3） （5） CP規(guī)則（1）（4）（3）證明： （1） P規(guī)則（假設(shè)前提） （2） P T規(guī)則（1） （3） Q T規(guī)則（1） （4） T規(guī)則（2）（3） （5） P規(guī)則 （6） R T規(guī)則（4）（5） （7） CP規(guī)則（1）（6）9.證明下列各式的有效性（如果需要，就使用間接證明法）。（1）證明： （1） P規(guī)則（假設(shè)前提） （2） P T規(guī)則（1） （3） P規(guī)則 （4） Q T規(guī)則（2）（3） （5） P規(guī)則 （6） T規(guī)則（4）（5） （7） P規(guī)則 （8） R T規(guī)則（6）（7） （9） P規(guī)則 （10） T規(guī)則（8）（9） （11） T規(guī)則（4）

16、（10） （12） F規(guī)則（1）（11）（2）證明： （1） P規(guī)則（假設(shè)前提） （2） P T規(guī)則（1） （3） P規(guī)則 （4） Q T規(guī)則（2）（3） （5） P規(guī)則 （6） T規(guī)則（4）（5） （7） P規(guī)則 （8） R T規(guī)則（6）（7） （9） P規(guī)則 （10） T規(guī)則（8）（9） （11） F規(guī)則（1）（10）（3）證明： （1） R P規(guī)則 （2） P規(guī)則 （3） T規(guī)則（1）（2） （4） T規(guī)則（1） （5） P規(guī)則 （6） T規(guī)則（4）（5） （7） T規(guī)則（6） （8） T規(guī)則（3）（7） （9） T規(guī)則（8）第2章 謂詞邏輯習(xí)題 P391.證明下列各式。（1），證明：（

17、1）P（2）US，（1）（3）P（4）US，（3）（5）T，（2），（4），（6）EG，（5）（2）證明： （1） P（假設(shè)前提） （2） T （3） T （4） T （5） T （6） T （7） P （8） T（5）（7） （9） ES（6） （10） US（8） （11） T（9）（10） （12） F（1）（11）（3），證明：（1）P（假設(shè)前提）（2）T，（1）（3）US，（2）（4）T，（3）（5）T，（3）（6）P（7）US，（6）（8）T，（5），（7）（9）P（10）US，（8）（11）T，（4），（10）（12）T，（8），（11）（4）證明： （1） P （2） US（1

18、） （3） P （4） US（3） （5） T（2）（4） （6） P （7） US（6） （8） T（5）（7） （9） UG（8）2.用CP規(guī)則證明下列各式。（1）證明： （1） P（假設(shè)前提） （2） US（1） （3） P （4） US（3） （5） T（2）（4） （6） UG（5） （7） CP（1）（6）（2）證明：由于 因此，原題等價(jià)于證明 （1） P（假設(shè)前提） （2） US（1） （3） P （4） US（3） （5） T（2）（4） （6） UG（5） （7） CP（1）（6）3.將下列命題符號(hào)化并推證其結(jié)論。（1）所有的有理數(shù)是實(shí)數(shù)，某些有理數(shù)是整數(shù)，因此某些實(shí)數(shù)是整數(shù)

19、。解：首先定義如下謂詞：是有理數(shù)是實(shí)數(shù)是整數(shù)于是問題符號(hào)化為：推理如下： （1） P （2） ES（1） （3） P （4） US（3） （5） T（2） （6） T（2） （7） T（4）（5） （8） T（6）（7） （9） EG（8）（2）任何人如果他喜歡步行，他就不喜歡乘汽車，每一個(gè)人或者喜歡乘汽車或者喜歡騎自行車，有的人不愛騎自行車，因而有的人不愛步行。解：首先定義如下謂詞：是人喜歡步行喜歡乘汽車x喜歡騎自行車于是問題符號(hào)化為：推理如下： （1） P （2） ES（1） （3） T（2） （4） T（2） （5） P （6） US（5） （7） T（3）（6） （8） T（4）（7）

20、 （9） P（10） US（9）（11） T（8）（10）（12） T（11）（13） T（3）（12）（14） T（3）（13）（15） EG（14）（3）每個(gè)科學(xué)工作者都是刻苦鉆研的，每個(gè)刻苦鉆研而且聰明的科學(xué)工作者在他的事業(yè)中都將獲得成功。華為是科學(xué)工作者并且他是聰明的，所以，華為在他的事業(yè)中將獲得成功。解：首先定義如下謂詞：是科學(xué)工作者是刻苦鉆研的是聰明的在他的事業(yè)中將獲得成功定義個(gè)體a：華為于是命題符號(hào)化為：推理如下： （1） P （2） US（1） （3） P （4） T（3） （5） T（3） （6） T（2）（4） （7） P （8） US（7） （9） T（3）（6）（10）

21、 T（8）（9）（4）每位資深名士或是中科院院士或是國務(wù)院參事，所有的資深名士都是政協(xié)委員。張偉是資深名士，但他不是中科院院士。因此，有的政協(xié)委員是國務(wù)院參事。解：首先定義如下謂詞：是資深名士是中科院院士是國務(wù)院參事是政協(xié)委員定義個(gè)體a：張偉于是命題符號(hào)化為：推理如下： （1） P （2） T（1） （3） T（1） （4） P （5） US（4） （6） T（2）（5） （7） P （8） US（7） （9） T（2）（8）（10） T（3）（9）（11） T（6）（10）（12） EG（11）（5）每一個(gè)自然數(shù)不是奇數(shù)就是偶數(shù)，自然數(shù)是偶數(shù)當(dāng)且僅當(dāng)它能被2整除。并不是所有的自然數(shù)都能被2所

22、整除。因此，有的自然數(shù)是奇數(shù)。解：首先定義如下謂詞：是自然數(shù)是奇數(shù)是偶數(shù)能被2整除于是命題符號(hào)化為：推理如下： （1） P （2） T（1） （3） ES（2） （4） T（3） （5） T（3） （6） P （7） US（6） （8） T（4）（7） （9） T（5）（8）（10） P（11） US（10）（12） T（4）（11）（13） T（9）（12）（14） T（4）（13）（15） EG（14）（6）如果一個(gè)人怕困難，那么他就不會(huì)獲得成功。每個(gè)人或者獲得成功或者失敗過。有些人未曾失敗過，所以，有些人不怕困難。解：首先定義如下謂詞：是人怕困難曾獲得成功曾獲得失敗于是命題符號(hào)化為：推理

23、如下： （1） P （2） ES（1） （3） T（2） （4） T（2） （5） P （6） US（5） （7） T（3）（6） （8） T（4）（7） （9） P （10） US（9） （11） T（8）（10） （12） T（11） （13） T（3）（12） （14） T（3）（13） （15） EG（14）4.下列推導(dǎo)步驟中哪個(gè)是錯(cuò)誤的？（1）1）P2）US，1）解：錯(cuò)誤。1）中改為。（2）1）P2）EG，1）解：錯(cuò)誤。（3）1）P2）EG，1）解：錯(cuò)誤。變量x不自由。（4）1）P2）EG，1）解：錯(cuò)誤。5.試找出下列推導(dǎo)過程中的錯(cuò)誤，并問結(jié)論是否有效？如果有效，寫出正確的推導(dǎo)過程。

24、 解：錯(cuò)誤，第2行的y是泛指，第4行的y是特制更改如下： （1） P （2） ES（1） （3） P （4） US（3） （5） T（2）（4） （6） EG（5）6.用構(gòu)成推導(dǎo)過程的方法證明下列蘊(yùn)含式。（1） 證明：（2）證明： （1） P （2） T（1） （3） T（2） （4） T（3） （5） T（4）習(xí)題 P421.將下列公式化為前束范式。（1）解： （2）解：（3）解：2.求等價(jià)于下面公式的前束主析取范式與前束主合取范式。（1）解：前束主析取范式：前束主合取范式：（2）解：前束析取范式由于是基本和，因此前束合取范式與前束析取范式一樣：（3）前束主析取范式：前束主合取范式與前束主析

25、取范式相同。（4）解：前束析取范式：前束合取范式：3.將下列公式化為斯柯林范式。（1）（2）第7章 圖論習(xí)題 P1351.畫出圖的圖示，指出其中哪些圖是簡單圖。（1）不是簡單圖。（2）不是簡單圖。（3）是簡單圖。2.寫出圖7-8的抽象數(shù)學(xué)定義。（1）解：，其中，（2）解：，其中， ， 3.證明：在n階簡單有向圖中，完全有向圖的邊數(shù)最多，其邊數(shù)為。證明：簡單有向圖是沒有自環(huán)，沒有平行邊的有向圖，只要兩個(gè)不同的結(jié)點(diǎn)之間才能有邊。完全有向圖是每個(gè)結(jié)點(diǎn)的出度和入度都是n-1的簡單有向圖，也就是每個(gè)結(jié)點(diǎn)都有到其他所有結(jié)點(diǎn)的邊，因此，完全有向圖的邊數(shù)最多。在完全有向圖中，所有結(jié)點(diǎn)的出度之和為n(n-1)，

26、所有結(jié)點(diǎn)的入度之和為n(n-1)，設(shè)邊的個(gè)數(shù)為m，由握手定理可知，2m= n(n-1)+ n(n-1)，即m= n(n-1)，得證。4.證明：3度正則圖必有偶數(shù)個(gè)結(jié)點(diǎn)。證明：設(shè)三度正則圖的結(jié)點(diǎn)個(gè)數(shù)為n，那么所有結(jié)點(diǎn)的度數(shù)之和為3n，由握手定理可知，邊的個(gè)數(shù)為3n/2=1.5n，由于邊的個(gè)數(shù)一定是整數(shù)，因此，n為偶數(shù)。得證。5.在一次集會(huì)中，相互認(rèn)識(shí)的人會(huì)彼此握手，試證明：與奇數(shù)個(gè)人握手的人數(shù)是偶數(shù)個(gè)。證明：設(shè)集會(huì)上的人一共有m個(gè)，可分為兩部分，一部分為與奇數(shù)個(gè)人握手的人，設(shè)為x個(gè)，另一部分為與偶數(shù)個(gè)人握手的人，為m-x個(gè)。由于握手是相互的，即一次握手，兩個(gè)人握手的次數(shù)都加1，一共加2，因此，集

27、會(huì)上所有人的握手次數(shù)之和為偶數(shù)。與偶數(shù)個(gè)人握手的人，這些人的握手次數(shù)之和為（其中，都是偶數(shù)），為偶數(shù)。與奇數(shù)個(gè)人握手的人，這些人的握手次數(shù)之和為（其中，為基數(shù)），由于所有人的握手次數(shù)之和偶數(shù)，因此也要為偶數(shù)，即又因?yàn)榧?，因此x為偶數(shù)，即與奇數(shù)個(gè)人握手的人是偶數(shù)個(gè)，得證。6.證明：圖7-7中的兩個(gè)圖同構(gòu)。證明：首先，給這兩幅圖標(biāo)上對(duì)應(yīng)的結(jié)點(diǎn)編號(hào)，如下兩個(gè)圖的結(jié)點(diǎn)和邊的數(shù)目都相同。假設(shè)函數(shù)，左圖中相鄰的結(jié)點(diǎn)是1和4，1和5，1和6，2和4，2和5，2和6，3和4，3和5，3和6，對(duì)應(yīng)的像點(diǎn)1和4，1和2，1和6，5和4，5和2，5和6，3和5，3和2，3和6在右圖中也相鄰，因此，兩圖同構(gòu)。7.證明

28、：在任意六個(gè)人中，若沒有三個(gè)人彼此認(rèn)識(shí)，則必有三個(gè)人彼此都不認(rèn)識(shí)。證明：分三種情況：（1）任何一個(gè)人最多認(rèn)識(shí)另外一個(gè)人將相互認(rèn)識(shí)的兩個(gè)人分成一組，則至少可以分3組，每組取一個(gè)人，則這三個(gè)必不認(rèn)識(shí)。（2）任何一個(gè)人最多認(rèn)識(shí)另外兩個(gè)人最糟糕的情況是當(dāng)每個(gè)人都認(rèn)識(shí)另外兩個(gè)人時(shí)，若認(rèn)識(shí)的人之間畫一條線可以構(gòu)成一個(gè)六邊形，取不相鄰的三個(gè)點(diǎn)即是不認(rèn)識(shí)的。（3）任何一個(gè)人最多認(rèn)識(shí)另外的三個(gè)人不妨設(shè)點(diǎn)A與B,C,E認(rèn)識(shí)（用實(shí)線連接）。因?yàn)锽,C,E之間只有有兩個(gè)人認(rèn)識(shí)就不滿足任何三個(gè)人都不認(rèn)識(shí)的條件，比如B,C認(rèn)識(shí)畫一條實(shí)線，那么A,B,C就相互認(rèn)識(shí)，與已知矛盾。所以B,C,E是所求的三個(gè)互補(bǔ)認(rèn)識(shí)的人。（4）

29、任何一個(gè)人最多認(rèn)識(shí)兩外4或5個(gè)人該情況與（3）類似，所求的人即與A認(rèn)識(shí)的兩外4或5個(gè)人中的三個(gè)人。證畢。8.證明：圖7-9的兩個(gè)圖不同構(gòu)。證明：給這兩幅圖標(biāo)上對(duì)應(yīng)的結(jié)點(diǎn)編號(hào)，如下：兩個(gè)圖的點(diǎn)數(shù)和邊數(shù)相同。假設(shè)函數(shù)：易證： a）中的子圖，與b）中的子圖，同構(gòu)。 a）中的子圖，與b）中的子圖，同構(gòu)。除這兩個(gè)子圖以外，對(duì)應(yīng)a）中的子圖，在b）無中對(duì)應(yīng)的同構(gòu)圖。因此a）和b）兩個(gè)圖不同構(gòu)。9圖7-10的兩個(gè)圖是否同構(gòu)？說明理由。解：對(duì)于圖b）中的點(diǎn)，其出度為：，入度：。而在a)圖中不存在這樣的結(jié)點(diǎn)。因此這兩個(gè)圖不同構(gòu)。10證明：任何階大于1的簡單無向圖必有兩個(gè)結(jié)點(diǎn)的度數(shù)相等。證明：考慮一個(gè)有n個(gè)結(jié)點(diǎn)的

30、連通圖（如果有一個(gè)孤立結(jié)點(diǎn)，去掉孤立結(jié)點(diǎn)考慮聯(lián)通子圖）。因?yàn)槭菬o向連通圖，每個(gè)結(jié)點(diǎn)的最大度數(shù)是n-1，最小度數(shù)是1。即對(duì)n個(gè)點(diǎn)賦值，共n-1種取值，由抽屜原理，必有兩個(gè)結(jié)點(diǎn)的取值相同，即必有兩個(gè)點(diǎn)的度數(shù)相同。11設(shè)n階無向圖G有m條邊，其中個(gè)結(jié)點(diǎn)的度數(shù)為k，其余結(jié)點(diǎn)的度數(shù)為k+1，證明：。證明：由題意，結(jié)點(diǎn)數(shù)為n，由總邊數(shù)建立關(guān)系：，由此可得：。習(xí)題 P1391畫出的所有不同的子圖，并說明其中哪些是生成子圖，找出互為補(bǔ)圖的生成子圖。解：其中，（1）和（7），（2）和（6），（3）和（5），（4）中的后兩個(gè)圖可以構(gòu)成互補(bǔ)的生產(chǎn)子圖。2設(shè)是完全有向圖。證明：對(duì)于的任意非空子集，是完全有向圖。證明：

31、（1）當(dāng)中只有一個(gè)結(jié)點(diǎn)時(shí)，是完全有向圖。（2）當(dāng)中有多于一個(gè)結(jié)點(diǎn)時(shí)，對(duì)其中任意兩個(gè)結(jié)點(diǎn)是的子集，即。因?yàn)閳DG是完全有向圖，因此間存在兩條有向邊和。是由非空子集生成的子圖，故，即中任意兩個(gè)結(jié)點(diǎn)間存在兩條有向邊，故是完全有向圖。3畫出圖7-15的兩個(gè)圖的交、并和環(huán)和。解：交： 并： 環(huán)和：4設(shè)G是任意6階簡單無向圖，證明：G或必有一個(gè)子圖是3階無向圖。證明：取G或任意取三個(gè)點(diǎn)，取與這三個(gè)點(diǎn)相關(guān)聯(lián)的變構(gòu)成一個(gè)3階的無向子圖。5我們稱與補(bǔ)圖同構(gòu)的簡單無向圖為自補(bǔ)圖。證明：每個(gè)自補(bǔ)圖的階能夠被4整除或被4整除余數(shù)為1。證明：設(shè)圖的頂點(diǎn)數(shù)為n，Kn的邊數(shù)為,由自補(bǔ)圖的定義知該圖與其子圖的邊數(shù)相同（同構(gòu)），

32、故其邊數(shù)為，由該數(shù)是整數(shù)得：，。故每個(gè)自補(bǔ)圖的階能夠被4整除或被4整除余數(shù)為1。6證明：沒有3階完全有向圖的子圖的n階簡單無向圖，最多有條邊。證明：用數(shù)學(xué)歸納法：（1） 當(dāng)n=3時(shí)，顯然成立。最多有2條邊。（2） 設(shè)當(dāng)n=k（）時(shí)成立，即最多有條邊，當(dāng)n=k+1時(shí)，若k是偶數(shù)，則第k+1個(gè)結(jié)點(diǎn)最多k/2個(gè)邊（否則會(huì)構(gòu)成K3），成立。當(dāng)k是奇數(shù)時(shí)，則第k+1個(gè)結(jié)點(diǎn)最多有個(gè)邊，成立。綜上，原命題成立。習(xí)題 P1441考慮圖7-21（1）從A至F的路徑有多少條？找出所有長度小于6的從A至F的路徑。解：A到F的路徑有無數(shù)條。長度小于6的有24條。（c f h:4,c g h:4, c e i:4, b

33、 d e f h:2, b d e g h:2, b d i:4）（2）找出從A至F的所有簡單路徑。解：12條。(c f h, c g h, c e I, b d e f h, b d e g h, b d i),還有一個(gè)自環(huán)，需乘以2.（3）找出從A至F的所有基本路徑。解：6條。(c f h, c g h, c e I, b d e f h, b d e g h, b d i)（4）求出從A至F的距離。求出該圖的直徑。解：距離為3。直徑為3。（5）找出該圖的所有回路。解：AaA, AbDdEeBcA, BeEiFhCgB; BgCfB; AbDdEiFhCgBcA; BeEiFhCfB;2證

34、明：圖7-21中基本路徑必為簡單路徑。證明：基本路徑要求途經(jīng)的頂點(diǎn)不重復(fù)，簡單路徑要求途經(jīng)的邊不重復(fù)。在圖7-21中，對(duì)于所有的基本路徑，邊不重復(fù)出現(xiàn)。所以基本路徑必是簡單路徑。3考慮圖7-22（1）對(duì)于每個(gè)結(jié)點(diǎn)，求。解： （2）找出所有強(qiáng)分支、單向分支和弱分支。解：強(qiáng)分支7個(gè)，分別是單項(xiàng)分支4個(gè)，分別是弱分支3個(gè)，分別是4設(shè)是任意無向圖（有向圖）G的三個(gè)任意結(jié)點(diǎn)，以下三個(gè)公式是否成立？如果成立，給出證明；如果不成立，舉出反例。（1），并且等號(hào)成立，當(dāng)且僅當(dāng)。解：成立。當(dāng)時(shí)，距離必定大于1。（2）解：成立。因?yàn)闊o向圖是無方向的。5. 證明：有向圖的每個(gè)結(jié)點(diǎn)和每條邊恰處于一個(gè)弱分支中。反證法：若任意結(jié)點(diǎn)V處于兩個(gè)或兩個(gè)以上的弱分支中，不妨設(shè)兩個(gè)弱分支為G1, G2, 則G1, G2是G的極大聯(lián)通子圖。設(shè)，又,故聯(lián)通。這與G1, G2是極大聯(lián)通子圖矛盾，故命題得證。6. 有向圖的每個(gè)結(jié)點(diǎn)（每條邊）是否恰處于一個(gè)強(qiáng)分支中？是否恰處于一個(gè)單向分支中？解：有向圖中的每個(gè)結(jié)點(diǎn)處于一個(gè)強(qiáng)分支中，而邊不一定。有向圖的結(jié)點(diǎn)和邊可能出現(xiàn)在兩個(gè)單向分支中。圖見書上（P141 圖7-18）7. 證明同階的回路必同構(gòu)。證明：同階表明兩個(gè)圖的頂點(diǎn)個(gè)數(shù)相同，設(shè)為V; 又聯(lián)通二度正則圖稱為回路。即兩個(gè)圖的每個(gè)頂點(diǎn)的度數(shù)相同為2. 邊數(shù)為