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

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

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

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

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

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

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

8、故對于重言式、可滿足式和矛盾式使用替換規(guī)則后其真值不變。8. 求出下列各式的代入實例。（1）；用代，用代。解：（2）；用代，用代解：P21 習題1.求下列各式的主合取范式。（1）解： （2）（3）2.求下列公式的主析取范式和主合取范式：（1）合取范式：析取范式：（2）合取范式：析取范式：（3）合取范式：析取范式：（4）析取范式：合取范式：P25 習題1.試用真值表法證明：不是,和的有效結論。解：構造真值表如下：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時，結論為0。故命題得證。2.，和是前提。在下列情況下，試確定結論C是否有效（可以使用真值表法證明。）（1）證明：真值表如下：P Q0 0110 1111 0001 111第1，2，4行當前提取值為1時，結論都為1。故結論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），結論C是有效結論。（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.不構成真值表證明：不是、和的有效結論。證明：（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)因此，是題目的有效結論，不是。4.使用推理的方法證明：是和的有效結論。證明：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.不構成真值表證明下列命題公式不能同時全為真。（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），推出結論與前提矛盾，因此命題公式不能同時為真。（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），推出的結

13、論與命題公式矛盾，因此命題公式不能同時為真。6. ，和是前提，根據(jù)推理規(guī)則斷定，在下列情況下是否是有效結論。（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），1，2，4，6（8）T規(guī)則，（1），（7），1，2，4，6（9）F規(guī)則，（1），（8）因此是有效結論。（2）證明：因為，再由前提，得到、的值任意，即、的值任意。因此不是有效結論。7.證明下列結論的有效性。（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一定為真的結論。（題目有問題）8.導出下列結論（如果需要，就是用規(guī)則）（1）證明： （1） P P規(guī)則（假設前提） （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ī)則（假設前提） （2） P規(guī)則 （3） Q T規(guī)則

15、（1）（2） （4） T規(guī)則（1）（3） （5） CP規(guī)則（1）（4）（3）證明： （1） P規(guī)則（假設前提） （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ī)則（假設前提） （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ī)則（假設前提） （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章 謂詞邏輯習題 P391.證明下列各式。（1），證明：（

17、1）P（2）US，（1）（3）P（4）US，（3）（5）T，（2），（4），（6）EG，（5）（2）證明： （1） P（假設前提） （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（假設前提）（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（假設前提） （2） US（1） （3） P （4） US（3） （5） T（2）（4） （6） UG（5） （7） CP（1）（6）（2）證明：由于 因此，原題等價于證明 （1） P（假設前提） （2） US（1） （3） P （4） US（3） （5） T（2）（4） （6） UG（5） （7） CP（1）（6）3.將下列命題符號化并推證其結論。（1）所有的有理數(shù)是實數(shù)，某些有理數(shù)是整數(shù)，因此某些實數(shù)是整數(shù)

19、。解：首先定義如下謂詞：是有理數(shù)是實數(shù)是整數(shù)于是問題符號化為：推理如下： （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）任何人如果他喜歡步行，他就不喜歡乘汽車，每一個人或者喜歡乘汽車或者喜歡騎自行車，有的人不愛騎自行車，因而有的人不愛步行。解：首先定義如下謂詞：是人喜歡步行喜歡乘汽車x喜歡騎自行車于是問題符號化為：推理如下： （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）每個科學工作者都是刻苦鉆研的，每個刻苦鉆研而且聰明的科學工作者在他的事業(yè)中都將獲得成功。華為是科學工作者并且他是聰明的，所以，華為在他的事業(yè)中將獲得成功。解：首先定義如下謂詞：是科學工作者是刻苦鉆研的是聰明的在他的事業(yè)中將獲得成功定義個體a：華為于是命題符號化為：推理如下： （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）每位資深名士或是中科院院士或是國務院參事，所有的資深名士都是政協(xié)委員。張偉是資深名士，但他不是中科院院士。因此，有的政協(xié)委員是國務院參事。解：首先定義如下謂詞：是資深名士是中科院院士是國務院參事是政協(xié)委員定義個體a：張偉于是命題符號化為：推理如下： （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）每一個自然數(shù)不是奇數(shù)就是偶數(shù)，自然數(shù)是偶數(shù)當且僅當它能被2整除。并不是所有的自然數(shù)都能被2所

22、整除。因此，有的自然數(shù)是奇數(shù)。解：首先定義如下謂詞：是自然數(shù)是奇數(shù)是偶數(shù)能被2整除于是命題符號化為：推理如下： （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）如果一個人怕困難，那么他就不會獲得成功。每個人或者獲得成功或者失敗過。有些人未曾失敗過，所以，有些人不怕困難。解：首先定義如下謂詞：是人怕困難曾獲得成功曾獲得失敗于是命題符號化為：推理

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.下列推導步驟中哪個是錯誤的？（1）1）P2）US，1）解：錯誤。1）中改為。（2）1）P2）EG，1）解：錯誤。（3）1）P2）EG，1）解：錯誤。變量x不自由。（4）1）P2）EG，1）解：錯誤。5.試找出下列推導過程中的錯誤，并問結論是否有效？如果有效，寫出正確的推導過程。

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

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

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

27、會上所有人的握手次數(shù)之和為偶數(shù)。與偶數(shù)個人握手的人，這些人的握手次數(shù)之和為（其中，都是偶數(shù)），為偶數(shù)。與奇數(shù)個人握手的人，這些人的握手次數(shù)之和為（其中，為基數(shù)），由于所有人的握手次數(shù)之和偶數(shù)，因此也要為偶數(shù)，即又因為即，因此x為偶數(shù)，即與奇數(shù)個人握手的人是偶數(shù)個，得證。6.證明：圖7-7中的兩個圖同構。證明：首先，給這兩幅圖標上對應的結點編號，如下兩個圖的結點和邊的數(shù)目都相同。假設函數(shù)，左圖中相鄰的結點是1和4，1和5，1和6，2和4，2和5，2和6，3和4，3和5，3和6，對應的像點1和4，1和2，1和6，5和4，5和2，5和6，3和5，3和2，3和6在右圖中也相鄰，因此，兩圖同構。7.證明

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

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

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

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

32、故其邊數(shù)為，由該數(shù)是整數(shù)得：，。故每個自補圖的階能夠被4整除或被4整除余數(shù)為1。6證明：沒有3階完全有向圖的子圖的n階簡單無向圖，最多有條邊。證明：用數(shù)學歸納法：（1） 當n=3時，顯然成立。最多有2條邊。（2） 設當n=k（）時成立，即最多有條邊，當n=k+1時，若k是偶數(shù)，則第k+1個結點最多k/2個邊（否則會構成K3），成立。當k是奇數(shù)時，則第k+1個結點最多有個邊，成立。綜上，原命題成立。習題 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),還有一個自環(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中基本路徑必為簡單路徑。證明：基本路徑要求途經的頂點不重復，簡單路徑要求途經的邊不重復。在圖7-21中，對于所有的基本路徑，邊不重復出現(xiàn)。所以基本路徑必是簡單路徑。3考慮圖7-22（1）對于每個結點，求。解： （2）找出所有強分支、單向分支和弱分支。解：強分支7個，分別是單項分支4個，分別是弱分支3個，分別是4設是任意無向圖（有向圖）G的三個任意結點，以下三個公式是否成立？如果成立，給出證明；如果不成立，舉出反例。（1），并且等號成立，當且僅當。解：成立。當時，距離必定大于1。（2）解：成立。因為無向圖是無方向的。5. 證明：有向圖的每個結點和每條邊恰處于一個弱分支中。反證法：若任意結點V處于兩個或兩個以上的弱分支中，不妨設兩個弱分支為G1, G2, 則G1, G2是G的極大聯(lián)通子圖。設，又,故聯(lián)通。這與G1, G2是極大聯(lián)通子圖矛盾，故命題得證。6. 有向圖的每個結點（每條邊）是否恰處于一個強分支中？是否恰處于一個單向分支中？解：有向圖中的每個結點處于一個強分支中，而邊不一定。有向圖的結點和邊可能出現(xiàn)在兩個單向分支中。圖見書上（P141 圖7-18）7. 證明同階的回路必同構。證明：同階表明兩個圖的頂點個數(shù)相同，設為V; 又聯(lián)通二度正則圖稱為回路。即兩個圖的每個頂點的度數(shù)相同為2. 邊數(shù)為