1、離散數(shù)學(xué)大作業(yè) 班級(jí)：15計(jì)算機(jī)2班 學(xué)號(hào)： 姓名：王鵬 時(shí)間：2017.6.3第一章 命題邏輯1.1命題及其表示法 命題的概念: 數(shù)理邏輯將能夠判斷真假的陳述句稱作命題。1.2命題聯(lián)結(jié)詞1. 否定聯(lián)結(jié)詞P 與原命題相反2. 合取聯(lián)結(jié)詞 同時(shí)為真，才為真3. 析取聯(lián)結(jié)詞 同時(shí)為假，才為假4. 蘊(yùn)涵聯(lián)結(jié)詞 當(dāng)且僅當(dāng)p為真，q為假5. 等價(jià)聯(lián)結(jié)詞 同時(shí)為真，或同時(shí)為假才為真1.3 命題公式、翻譯與解釋1. 命題公式定義 命題公式，簡稱公式，定義為：（1）單個(gè)命題變元是公式；（2）如果P是公式，則P是公式；（3）如果P、Q是公式，則PQ、PQ、PQ、 PQ都是公式；（4）當(dāng)且僅當(dāng)能夠有限次的應(yīng)用(1

2、) 、(2)、(3) 所得到的包括命題變元、聯(lián)結(jié)詞和括號(hào)的符號(hào)串是公式。2. 命題的翻譯 可以把自然語言中的有些語句，轉(zhuǎn)變成數(shù)理邏輯中的符號(hào)形式，稱為命題的翻譯。 命題翻譯時(shí)應(yīng)注意下列事項(xiàng)：（1）確定所給句子是否為命題。（2）句子中聯(lián)結(jié)詞是否為命題聯(lián)結(jié)詞。（3）要正確的選擇原子命題和合適的命題聯(lián)結(jié)詞。1.4 真值表與等價(jià)公式1. 真值表定義 將公式G在其所有解釋下所取得的真值列成一個(gè)表，稱為G的真值表。構(gòu)造真值表的方法如下：（1）找出公式G中的全部命題變元，并按一定的順序排列成P1，P2，Pn。 （2）列出G的2n個(gè)解釋，賦值從000（n個(gè)）開始，按二進(jìn)制遞加順序依次寫出各賦值，直到111為止

3、（或從111開始，按二進(jìn)制遞減順序?qū)懗龈髻x值，直到000為止），然后從低到高的順序列出G的層次。（3）根據(jù)賦值依次計(jì)算各層次的真值并最終計(jì)算出G的真值成真賦值+成假賦值=2n2. 命題公式的分類 定義 設(shè)G為公式：（1）如果G在所有解釋下取值均為真，則稱G是永真式或重言式； （2）如果G在所有解釋下取值均為假，則稱G是永假式或矛盾式； （3）如果至少存在一種解釋使公式G取值為真，則稱G是可滿足式。3. 等價(jià)公式 定義 設(shè)A和B是兩個(gè)命題公式，如果A和B在任意賦值情況下都具有相同的真值，則稱A和B是等價(jià)公式。記為AB。性質(zhì)定理設(shè)A、B、C是公式，則（1）AA（2）若AB則BA（3）若AB且BC則

4、AC定理 設(shè)A、B、C是公式，則下述等價(jià)公式成立：（1）雙重否定律 AA（2）等冪律 AAA ； AAA（3）交換律 ABBA ； ABBA（4）結(jié)合律 （AB）CA（BC）（AB）CA（BC）（5）分配律 （AB）C（AC）（BC）（AB）C（AC）（BC）（6）德摩根律 （AB）AB（AB）AB（7）吸收律 A（AB）A；A（AB）A（8）零一律 A11 ； A00（9）同一律 A0A ； A1A（10）排中律 AA1（11）矛盾律 AA0（12）蘊(yùn)涵等值式 ABAB（13）假言易位 ABBA（14）等價(jià)等值式 AB（AB）（BA）（15）等價(jià)否定等值式 ABABBA（16）歸繆式 （AB

5、）（AB）A4. 置換規(guī)則 定理（置換規(guī)則） 設(shè)（A）是一個(gè)含有子公式A的命題公式，（B）是用公式B置換了（A）中的子公式A后得到的公式，如果AB，那么（A）（B）。1.5 對(duì)偶與范式1. 對(duì)偶定義 在僅含有聯(lián)結(jié)詞、的命題公式A中，將聯(lián)結(jié)詞換成，將換成，如果A中含有特殊變元0或1，就將0換成1，1換成0，所得的命題公式A*稱為A的對(duì)偶式。例：公式（PQ）（PQ） 的對(duì)偶式為：（PQ）（PQ）定理 設(shè)A和A*互為對(duì)偶式，P1，P2，Pn是出現(xiàn)在A和A*中的所有原子變元，若將A和A*寫成n元函數(shù)形式，則（1）A（P1，P2，Pn）A*（P1，P2，Pn）（2）A（P1，P2，Pn）A*（P1，P2

6、，Pn） 定理（對(duì)偶原理）設(shè)A、B是兩個(gè)命題公式，若AB，則A*B*，其中A*、B*分別為A、B的對(duì)偶式。2. 范式定義 僅由有限個(gè)命題變元及其否定構(gòu)成的析取式稱為簡單析取式，僅由有限個(gè)命題變元及其否定構(gòu)成的合取式稱為簡單合取式。定義 僅由有限個(gè)簡單合取式構(gòu)成的析取式稱為析取范式。僅由有限個(gè)簡單析取式構(gòu)成的合取式稱為合取范式。定理（范式存在定理）任何命題公式都存在著與之等價(jià)的析取范式和合取范式。3. 主范式定義 設(shè)G為公式，P1，P2，Pn為G中的所有命題變元，若G的析取范式中每一個(gè)合取項(xiàng)都是P1，P2，Pn的一個(gè)極小項(xiàng)，則稱該析取范式為G的主析取范式。矛盾式的主析取范式為0。定理 任意的命題

7、公式都存在一個(gè)唯一的與之等價(jià)的主析取范式。 定義 設(shè)G為公式，P1，P2，Pn為G中的所有命題變元，若G的合取范式中每一個(gè)析取項(xiàng)都是P1，P2，Pn的一個(gè)極大項(xiàng)，則稱該合取范式為G的主合取范式。通常，主合取范式用表示。重言式的主合取范式中不含任何極大項(xiàng)，用1表示。 定理 任意的命題公式都存在一個(gè)唯一的與之等價(jià)的主合取范式。1.6 公式的蘊(yùn)涵1. 蘊(yùn)涵的概念定義 設(shè)G、H是兩個(gè)公式，若GH是永真式，則稱G蘊(yùn)涵H，記作GH。蘊(yùn)涵關(guān)系有如下性質(zhì)：（1） 對(duì)于任意公式G，有GG；（2）（2）對(duì)任意公式G、H，若GH且HG，則GH；（3） 若GH且HL，則GL。2. 基本蘊(yùn)涵式（1）PQP； （2）PQ

8、Q；（3）PPQ； (4) QPQ；（5）P（PQ）； （6）Q（PQ）；（7）（PQ）P； （8）（PQ）Q；（9）P，PQQ； （10）Q，PQP；（11）P，PQQ； （12）PQ，QRPR；（13）PQ，PR，QRR； （14）PQ，RS（PR）（QS）；（15）P，QPQ。1.7 其它聯(lián)結(jié)詞與最小聯(lián)結(jié)詞組1. 其它聯(lián)結(jié)詞定義 設(shè)P、Q為命題公式，則復(fù)合命題P Q稱為P和Q的不可兼析取，當(dāng)且僅當(dāng)P與Q的真值不相同時(shí)，PQ的真值為1，否則PQ的真值為假。定義 設(shè)P、Q是兩個(gè)命題公式，復(fù)合命題P Q稱為命題P、Q的條件否定，當(dāng)且僅當(dāng)P的真值為1，Q的真值為0時(shí)，P Q的真值為1，否則 PQ

9、的真值為0。2. 最小聯(lián)結(jié)詞組定義 設(shè)S是一些聯(lián)結(jié)詞組成的非空集合，如果任何的命題公式都可以用僅包含S中的聯(lián)結(jié)詞的公式表示，則稱S是聯(lián)結(jié)詞的全功能集。特別的，若S是聯(lián)結(jié)詞的全功能集且S的任何真子集都不是全功能集，則稱S是最小全功能集，又稱最小聯(lián)結(jié)詞組。 定理 ，是聯(lián)結(jié)詞的全功能集。 定理 ，是聯(lián)結(jié)詞的全功能集。定理 ，、，是最小聯(lián)結(jié)詞組。 定理 ，是最小聯(lián)結(jié)詞組。1.8 命題邏輯推理理論1.8.1 命題邏輯推理理論定義 如果G1，G2，Gn蘊(yùn)涵H，則稱H能夠由G1，G2，Gn有效推出，G1，G2，Gn稱為H的前提，H稱為G1，G2，Gn的有效結(jié)論。稱（G1G2Gn）H是由前提G1，G2，Gn推

10、結(jié)論H的推理的形式結(jié)構(gòu)。2. 推理規(guī)則下面給出推理中常用的推理規(guī)則。1 前提引入規(guī)則：可以在證明的任何時(shí)候引入前提；2 結(jié)論引入規(guī)則：在證明的任何時(shí)候，已證明的結(jié)論都可以作為后續(xù)證明的前提；3 置換規(guī)則：在證明的任何時(shí)候，命題公式中的任何子命題公式都可以用與之等價(jià)的命題公式置換。4 假言推理規(guī)則：P，PQQ5 附加規(guī)則：PPQ；6 化簡規(guī)則：P，QP；7 拒取式規(guī)則： Q，PQP；8 假言三段論規(guī)則：PQ，QRPR；9 析取三段論規(guī)則：P，PQQ；10.構(gòu)造性二難規(guī)則：PQ，PR，QRR；11.合取引入規(guī)則：P，QPQ3. 推理常用方法1.直接證法 直接證法就是根據(jù)一組前提，利用前面提供的一些

11、推理規(guī)則，根據(jù)已知的等價(jià)公式和蘊(yùn)涵式，推演得到有效的結(jié)論的方法，即有前提直接推導(dǎo)出結(jié)論。 2間接證法 間接證法主要有如下兩種情況。 （1）附加前提證明法 有時(shí)要證明的結(jié)論以蘊(yùn)涵式的形式出現(xiàn)，即推理的形式結(jié)構(gòu)為：（G1G2Gn）（RC）設(shè)（G1G2Gn）為S，則上述推理可表示為證明S（RC），即證明S（RC）為永真式。 用附加前提證明法證明下面推理。前提：P（QR），SP，Q 結(jié)論：SR證明：（1）SP 前提引入規(guī)則 （2）S 附加前提引入規(guī)則 （3）P （1）（2）析取三段論規(guī)則 （4）P（QR） 前提引入規(guī)則 （5）QR （3）（4）假言推理規(guī)則 （6）Q 前提引入規(guī)則 （7）R （5）（6

12、）假言推理規(guī)則2）歸繆法定義 設(shè)G1，G2，Gn是n個(gè)命題公式，如果G1G2Gn是可滿足式，則稱G1，G2，Gn是相容的。否則（即G1G2Gn是矛盾式）稱G1，G2，Gn是不相容的。例 用歸繆法證明。前提：PQ，PR，QS 結(jié)論：SR證明（1）（SR） 附加前提引入規(guī)則 （2）SR （1）置換規(guī)則 （3）S （2）化簡規(guī)則 （4）R （2）化簡規(guī)則 （5）QS 前提引入規(guī)則 （6）QS （5）置換規(guī)則 （7）Q （3）（6）析取三段論 （8）PQ 前提引入規(guī)則 （9）P （7）（8）析取三段論規(guī)則 （10）PR 前提引入規(guī)則 （11）PR （10）置換規(guī)則 （12）R （9）（11）析取三段論

13、規(guī)則 （13）RR （4）（12）合取引入規(guī)則第二章 謂詞邏輯第三章2.1 謂詞邏輯命題的符號(hào)化 1個(gè)體詞 ：個(gè)體詞是指研究對(duì)象中不依賴于人的主觀而獨(dú)立存在的具體的或抽象的客觀實(shí)體 個(gè)體常項(xiàng)或個(gè)體常元 ： 個(gè)體變項(xiàng)或個(gè)體變元 ： 個(gè)體域或論域 ： 2謂詞：用來刻畫個(gè)體詞的性質(zhì)或個(gè)體詞之間關(guān)系的詞 一般來說，“x是A”類型的命題可以用A（x）表達(dá)。對(duì)于“x大于y”這種兩個(gè)個(gè)體之間關(guān)系的命題，可表達(dá)為B（x，y），這里B表示“大于”謂詞。我們把A（x）稱為一元謂詞,B（x，y）稱為二元謂詞，M（a，b，c）稱為三元謂詞，依次類推，通常把二元以上謂詞稱作多元謂詞。 2.2 謂詞邏輯公式與解釋1. 謂

14、詞邏輯的合式公式 定義2.1 設(shè)P（x1，x2，xn）是n元謂詞公式，其中，x1x2，xn是個(gè)體變項(xiàng)，則稱P（x1，x2，xn）為謂詞演算的原子公式。 定義2.2 謂詞演算的合式公式定義如下：（1）原子公式是合式公式；（2）若A是合式公式，則（A）也是合式公式；（3）若A，B是合式公式，則（AB）、（AB）、（AB）、（AB）是合式公式；（4）若A是合式公式，則x A、x A是合式公式；（5）只有有限次地應(yīng)用（1）（4）構(gòu)成的符號(hào)串才是合式公式。 2. 約束變元與自由變元 1約束變元與自由變元的概念定義 2.3 在公式x F（x）和x F（x）中，稱x為指導(dǎo)變元，F(xiàn)（x ）為相應(yīng)量詞的轄域或作

15、用域。在x和x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)，F(xiàn)（x）中不是約束出現(xiàn)的其他變元均稱為自由出現(xiàn)。 2約束變元的換名與自由變元的代入 自由變元的代入規(guī)則是：（1）對(duì)于謂詞公式中的自由變元，可以代入，此時(shí)需要對(duì)公式中出現(xiàn)該自由變元的每一處進(jìn)行代入。（2）用以代入的變元與原公式中所有變元的名稱都不能相同。2.2.3 謂詞邏輯公式的解釋 定義2.4 謂詞邏輯公式的一個(gè)解釋I，是由非空區(qū)域D和對(duì)G中常項(xiàng)符號(hào)、函數(shù)符號(hào)、謂詞符號(hào)以下列規(guī)則進(jìn)行的一組指定組成：（1）對(duì)每一個(gè)常項(xiàng)符號(hào)指定D中一個(gè)元素。（2）對(duì)每一個(gè)n元函數(shù)符號(hào)，指定一個(gè)函數(shù)。（3）對(duì)每一個(gè)n元謂詞符號(hào)，指定一個(gè)謂詞。顯然，對(duì)任意公式G，如

16、果給定G的一個(gè)解釋I，則G在I的解釋下有一個(gè)真值，記作TI（G）。 定義2.5 若存在解釋I，使得G在解釋I下取值為真，則稱公式G為可滿足的，簡稱I滿足G。定義2.6 若不存在解釋I，使得I滿足G，則稱公式G為永假式（或矛盾式）。若G的所有解釋I都滿足G，則稱公式G為永真式（或重言式）。2.3 謂詞邏輯約束公式的等價(jià)與蘊(yùn)涵3. 謂詞邏輯的等價(jià)公式 定義2.7 設(shè)A、B是命題邏輯中的任意兩個(gè)公式，設(shè)它們有共同的個(gè)體域E，若對(duì)任意的解釋I都有TI（A）= TI（B），則稱公式A、B在E上是等價(jià)的，記作AB。 定理1 設(shè)A（x）是謂詞公式，有關(guān)量詞否定的兩個(gè)等價(jià)公式：（1）x A（x）xA（x）（2

17、）x A（x）xA（x）定理2 設(shè)A（x）是任意的含自由出現(xiàn)個(gè)體變項(xiàng)x的公式，B是不含x出現(xiàn)的公式，則有（1）x（A（x）B）x A（x）B（2）x（A（x）B）x A（x）B（3）x（A（x） B）x A（x） B（4）x（BA（x）B x A（x）（5）x（A（x）B） x A（x）B（6）x（A（x）B）x A（x）B（7）x（A（x） B）x A（x） B（8）x（BA（x）Bx A（x） 定理3 設(shè)A（x）、B（x）是任意包含自由出現(xiàn)個(gè)體變元x的公式,則有：（1）x（A（x）B（x）x A（x）x B（x）（2）x（A（x）B（x）x A（x）x B（x） x（A（x）B（x）x A

18、（x）x B（x） 2.3.2 謂詞邏輯的蘊(yùn)涵公式 定義2.8 設(shè)A、B是命題邏輯中的任意兩個(gè)公式，若AB是永真式，則稱公式A蘊(yùn)涵公式B，記作AB。 定理4 下列蘊(yùn)涵式成立（1）x A（x）x B（x）x（A（x）B（x）（2）x（A（x）B（x）x A（x）x B（x）（3）x（A（x） B（x）x A（x） x B（x）（4）x（A（x） B（x）x A（x） x B（x）（5）x A（x） x B（x）x（A（x） B（x）3. 多個(gè)量詞的使用 定義2.9 設(shè)謂詞公式G，不包含聯(lián)結(jié)詞，。把G中出現(xiàn)的聯(lián)結(jié)詞，互換；命題常量T，F(xiàn)互換；量詞，互換之后得到的公式稱為G的對(duì)偶公式，記作G*。 定

19、理5（對(duì)偶定理） 設(shè)A、B是任意兩個(gè)公式并且不包含聯(lián)結(jié)詞，。若AB，則A*B*。2.4 前束范式 定義2.10 一個(gè)謂詞公式，如果量詞均在全式的開頭，且轄域延伸到公式的末尾，則該公式稱為前束范式。 定理6 對(duì)任意一個(gè)謂詞公式都可以化為與它等價(jià)的前束范式。 定義2.11 若一個(gè)謂詞公式，具有如下形式，則稱該公式為前束析取范式。 定義2.12 若一個(gè)謂詞公式，具有如下形式，則稱該公式為前束合取范式。 定理7 任意謂詞公式都可以化為與其等價(jià)的前束析取范式和前束合取范式。2.5 謂詞演算的推理理論 1全稱指定規(guī)則（簡稱US規(guī)則） 這條規(guī)則有下面兩種形式：(1)x P（x）P（y）(2)x P（x）P（

20、c）其中，P是謂詞，（1）中y為任意不在P（x）中約束出現(xiàn)的個(gè)體變元；（2）中c為個(gè)體域中的任意一個(gè)個(gè)體常元。 2存在指定規(guī)則（簡稱ES規(guī)則） x P（x）P（c）其中，c為個(gè)體域中使P成立的特定個(gè)體常元。必須注意，應(yīng)用存在指定規(guī)則，其指定的個(gè)體c不是任意的。 3全稱推廣規(guī)則（簡稱UG規(guī)則） P（y）x P（x） 4存在推廣規(guī)則（簡稱EG規(guī)則）P（c）x P（x）其中，c為個(gè)體域中的個(gè)體常元，這個(gè)規(guī)則比較明顯，對(duì)于某些個(gè)體c，若P（c）成立，則個(gè)體域中必有x P（x）。第三章 集合論3.1集合的概念與表示 集合的表示 ：1列舉法2描述法 3.文氏圖法 3.2 集合之間的關(guān)系定義3.1 如果集合

21、A中的每一個(gè)元素都是集合B中的元素，則稱A是B的子集，也可以說A包含于B，或者B包含A，這種關(guān)系寫作AB 或 BA,如果A不是B的子集，即在A中至少有一個(gè)元素不屬于B時(shí)，稱B不包含A，記作BA 或 AB定義3.2 如果兩個(gè)集合A和B的元素完全相同，則稱這兩個(gè)集合相等，記作AB。定理3.1 集合A和集合B相等的充分必要條件是AB且BA。 定義3.3 如果集合A是集合B的子集，但A和B不相等，也就是說在B中至少有一個(gè)元素不屬于A，則稱A是B的真子集，記作AB 或 BA 定義3.4 若集合U包含我們所討論的每一個(gè)集合，則稱U是所討論問題的完全集，簡稱全集。 定義3.5 設(shè)A是有限集，由A的所有子集作

22、為元素而構(gòu)成的集合稱為A的冪集，記作(A)，即(A)X|XA。在A的所有子集中，A和這兩個(gè)子集又叫平凡子集。 定理3.2 設(shè)A是有限集，|A|=n，則A的冪集(A)的基為2。3.3 集合的運(yùn)算3.3.1 集合的并運(yùn)算定義3.6 任意兩個(gè)集合A、B的并，記作AB，它也是一個(gè)集合，由所有屬于A或者屬于B的元素合并在一起而構(gòu)成的，即ABx | xA或xB 用文氏圖表示集合之間的并運(yùn)算：用平面上的矩形表示全集U。用矩形內(nèi)的圓表示U中的任一集合。圖中表示了集合A和集合B的并集。陰影部分就是AB。 由集合并運(yùn)算的定義可知，并運(yùn)算具有以下性質(zhì)：（1）冪等律：AAA （2）同一律：AA（3）零律：AUU （4

23、）結(jié)合律：(AB)CA(BC)（5）交換律：ABBA 3.3.2 集合的交運(yùn)算定義3.7 任意兩個(gè)集合A、B的交記作AB，它也是一個(gè)集合，由所有既屬于A又屬于B的元素構(gòu)成，即AB x | xA且xB 集合的交運(yùn)算的文氏圖表示，見圖，其中陰影部分就是AB。 由集合交運(yùn)算的定義可知，交運(yùn)算有以下性質(zhì)：（1）冪等律：AAA（2）同一律：AUA（3）零律：A（4）結(jié)合律：(AB)CA(BC)（5）交換律：ABBA定理3.3 設(shè)A，B，C是三個(gè)集合，則下列分配律成立：A（BC）（AB）（AC）A（BC）（AB）（AC） 定理3.4 設(shè)A，B為兩個(gè)集合，則下列關(guān)系式成立：A（AB）A A（AB）A這個(gè)定理

24、稱為吸收律，可以用文氏圖驗(yàn)證 3.3.3 集合的補(bǔ) 定義3.8 設(shè)A、B是兩個(gè)集合，A-B也是一個(gè)集合。它是由屬于集合A但不屬于集合B的所有元素組成的。A-B稱為集合B關(guān)于A的補(bǔ)集(或相對(duì)補(bǔ))。即-Bx|x且xBA-B也稱為集合A和B的差集。 定義3.9 設(shè)U是全集，A是U的一個(gè)子集，稱U-A為A關(guān)于全集的補(bǔ)集，也叫做A的絕對(duì)補(bǔ)集，簡稱為補(bǔ)集。記作A。即U-x|x且x 集合的補(bǔ)運(yùn)算有以下性質(zhì)（1）雙重否定律：（A）A（2）摩根律：U（3）摩根律：U（4）矛盾律：A（A）（5）排中律：A（A）U為了簡單，約定A（B）表示為AB，A（B）表示為 AB。 定理3.5 設(shè)A、B是兩個(gè)集合，則下列關(guān)系式

25、成立：（AB）AB（AB）AB這個(gè)定理稱為德摩根定律。 定理3.6 設(shè)A、B、C是任意三個(gè)集合，則下列關(guān)系式成立：A-BAB A-BA-（AB） 3.3.4 集合的對(duì)稱差 定義3.10 設(shè)A、B是兩個(gè)集合，集合A和B的對(duì)稱差記作AB，它是一個(gè)集合，其元素或?qū)儆贏，或?qū)儆贐，但不能既屬于A又屬于B。即AB(AB)-(AB) 集合的對(duì)稱差的文氏圖表示 由對(duì)稱差的定義易得下列性質(zhì)：（1）AA（1）（2）AA（3）A（4）ABBA（5）（AB）CA（BC）（6）AB(A-B)(B-A)3.4 包含排斥原理定理3.7 設(shè)A、B為有限集合，|A|、|B|為其基數(shù)，則|AB|A|+|B|-|AB|這個(gè)結(jié)論稱

26、作包含排斥原理。 第七章 圖論7.1 圖的基本概念7.1.1 圖的基本類型 定義7.1 所謂圖G是一個(gè)三元組，G=，其中V(G)是一個(gè)非空的結(jié)點(diǎn)集合，E（G）是邊的集合，G是從邊集合E到結(jié)點(diǎn)無序偶或有序偶集合上的函數(shù)。 定義7.2 如果兩個(gè)結(jié)點(diǎn)之間有多條邊（對(duì)于有向圖，則有多條同方向的邊），則稱這些邊為平行邊，兩相結(jié)點(diǎn)a，b間平行邊的條數(shù)稱為邊的重?cái)?shù)。含有平行邊的圖稱為多重圖，不含平行邊和自回路的圖稱為簡單圖。 7.1.2 圖中結(jié)點(diǎn)的度數(shù) 1無向圖中結(jié)點(diǎn)的度數(shù) 定義7.3 設(shè)圖G是無向圖，v是圖G中的結(jié)點(diǎn)，所有與v關(guān)聯(lián)的邊的條數(shù)，稱為點(diǎn)v的度數(shù)，記作deg(v)。定理7.1 設(shè)圖G是具有n個(gè)點(diǎn)

27、，m條邊的無向圖，其中結(jié)點(diǎn)集合為V=v1，v2，vn，則 2有向圖中結(jié)點(diǎn)的度數(shù) 定義7.4 設(shè)圖G是有向圖，v是圖G中的結(jié)點(diǎn)，以v為始點(diǎn)的有向邊的條數(shù)稱為v的出度，記個(gè)deg+(v)，以v為終點(diǎn)的有向邊的條數(shù)稱為v的入度，記作deg(v)。 定理7.2 設(shè)有向圖G具有n個(gè)結(jié)點(diǎn)，m條邊，其中結(jié)點(diǎn)構(gòu)成的集合V=v1，v2，vn，則有 7.1.3 完全圖 1無向完全圖 定義7.6 在n階無向圖中，如果任意兩個(gè)不同的結(jié)點(diǎn)之間都有一條邊關(guān)聯(lián)，則稱此無向圖為無向完全圖，記作Kn。定理7.3 n個(gè)結(jié)點(diǎn)的無向完全圖Kn的邊數(shù)是。 2有向完全圖 定義7.7 在n階有向圖中，如果任意兩個(gè)結(jié)點(diǎn)都有兩條方向相反的有向

28、邊關(guān)聯(lián)，且每一個(gè)結(jié)點(diǎn)都有自回路，則稱此有向圖為有向完全圖。 定理7.4 n個(gè)結(jié)點(diǎn)的有向完全圖Kn的邊數(shù)是n2。 3競賽圖 定義7.8 設(shè)G為n階有向圖，如果G的底圖為無向完全圖Kn，則稱G為競賽圖。 7.1.4 圖的同構(gòu) 定義7.9 設(shè)圖G的點(diǎn)集為V，邊集為E，圖G的點(diǎn)集為V，邊集為。如果存在著V到V的雙射函數(shù)f，使對(duì)任意的u，vV，(u，v)E（或E），當(dāng)且僅當(dāng)（f（u），f（v）E（或E），則稱圖G和G 同構(gòu)，記作GG。 7.1.5 補(bǔ)圖 定義7.10 設(shè)G=為任意的n階無向簡單圖，則所有使G成為Kn添加的邊和G的n個(gè)結(jié)點(diǎn)構(gòu)成的圖稱為圖G的補(bǔ)圖，記作。 定義7.11 設(shè)G=是任意一個(gè)n階無

29、向圖，V=v1，v2，vn，稱d（v1），d（v2），d（vn）為G的度數(shù)列。對(duì)于結(jié)點(diǎn)標(biāo)定的無向圖，它的度數(shù)列是唯一的。反之，對(duì)于給定的非負(fù)整數(shù)列d=（d1，d2，dn），若存在以V=v1，v2，vn為結(jié)點(diǎn)n階無向圖G，使得d（vi）=di，則稱d是可圖化的。特別地，若得到的圖是簡單圖，則稱d是可簡單圖化的。 定理7.5 設(shè)非負(fù)整數(shù)列d=（d1，d2，dn），當(dāng)且僅當(dāng)為偶數(shù)時(shí)，d是可圖化的。 定理7.6 設(shè)非負(fù)整數(shù)列d=（d1，d2，dn），（n-1）d1d2d n0，則d是可簡單圖化的，當(dāng)且僅當(dāng)對(duì)于每個(gè)整數(shù)r，1r（n-1），r（r-1）+且為偶數(shù)。 定理7.7 設(shè)非負(fù)整數(shù)列d=（d1，d2

30、，dn），（n-1）d1d2d n0，則d是可簡單化的當(dāng)且僅當(dāng)d=（-1，-1，-1，）。 7.1.6 子圖 定義7.12 設(shè)G=和G=是兩個(gè)圖，（1）若VV且EE，則稱G是G的子圖；（2）若G是G的子圖，但VV或EE，則稱G是G的真子圖；（3）若G是G的子圖，且V=V，則稱G是G的生成子圖或支撐子圖。 7.2 路與回路7.2.1 通路與回路 定義7.13 在無向圖（或有向圖）G=中，設(shè)v0，v1，vnV，e0，e1，enE，其中ei是關(guān)聯(lián)于結(jié)點(diǎn)vi-1，vi的邊，交替序列v0e0v1e1en-1 vn稱為聯(lián)結(jié)v0到vn的通路或路。v0和vn分別稱為通路的起點(diǎn)和終點(diǎn)，通路中所含邊的條數(shù)稱為該通

31、路的長度。如果通路中的始點(diǎn)與終點(diǎn)相同，則稱這條路為回路。 定理7.8 在n階無向圖中，如果存在一條從vi到vj的通路，則從vi到vj必有一條長度不大于n-1的基本通路。 定理7.9 在n階無向圖中，如果存在一條通過vi的回路，則必有一條長度不大于n的通過vi 的基本回路。 7.2.2 圖的連通性 1無向圖的連通性 定義7.14 設(shè)圖G是無向圖，u和v是圖G中的兩個(gè)結(jié)點(diǎn)，如果u和v之間有通路，則稱u，v是連通的，并規(guī)定u與自身是連通的。 定義7.15 若圖G是平凡圖或G中任意兩點(diǎn)都是連通的，則稱圖G為連通圖，否則稱G為非連通圖或分離圖。 定義7.16 設(shè)無向圖G=為連通圖，若存在非空點(diǎn)集VV，使

32、圖G刪除了V的所有結(jié)點(diǎn)后，所得到的子圖是不連通圖，而刪除V的任何真子集后，得到的子圖仍然是連通圖，則稱V是G的一個(gè)點(diǎn)割集。若某一個(gè)結(jié)點(diǎn)構(gòu)成一個(gè)點(diǎn)割集，則稱該結(jié)點(diǎn)為割點(diǎn)。 定義7.17 設(shè)無向圖G=為連通圖，若存在非空邊集EE，使圖G刪除了E的所有邊后，所得到的子圖是不連通圖，而刪除E的任何真子集后，得到的子圖仍然是連通圖，則稱E是G的一個(gè)邊割集。若某一個(gè)邊構(gòu)成一個(gè)邊割集，則稱該邊為割邊（或橋）。 定理7.10 對(duì)于任何圖G，都有下面不等式成立：k其中，k、分別為G的點(diǎn)連通度、邊連通度和結(jié)點(diǎn)的最小度。 定理7.11 一個(gè)無向連通圖G中的結(jié)點(diǎn)w是割點(diǎn)的充分必要條件是存在兩個(gè)結(jié)點(diǎn)u和v，使得結(jié)點(diǎn)u和

33、v的每一條路都通過w。 2有向圖的連通性 定義7.18 在有向圖G=中，若從結(jié)點(diǎn)u到v有通路，則稱u可達(dá)v。 定義7.19 有向圖的連通性分為強(qiáng)連通、單向連通和弱連通三種。 定義7.20 設(shè)G是有向圖，G是其子圖，若G是強(qiáng)連通的（單向連通的，弱連通的），且沒包含G的更大的強(qiáng)連通(單向連通，弱連通)子圖，則稱G是G的極大強(qiáng)連通子圖(極大單向連通子圖，極大弱連通子圖)，也稱為強(qiáng)分支（單向分支，弱分支）。 7.2.4 關(guān)鍵路徑 定義7.21 在計(jì)劃評(píng)審圖中，關(guān)鍵路徑是從發(fā)點(diǎn)到收點(diǎn)的通路中權(quán)和最大的路徑。處于關(guān)鍵路徑上的結(jié)點(diǎn)稱為關(guān)鍵狀態(tài)，處于關(guān)鍵路徑上的邊稱為關(guān)鍵活動(dòng)或關(guān)鍵工序。 定義7.22 設(shè)計(jì)劃

34、評(píng)審圖G，任意的viV（G），稱從發(fā)點(diǎn)沿著關(guān)鍵路徑到達(dá)vi所需的時(shí)間，稱為vi的最早完成的時(shí)間，記作TE（vi）。 定理7.13 設(shè)PE=v|TE（v）已經(jīng)算出，TE=V-PE，若TE，則存在vTE，使得PE 定義7.23 在保證收點(diǎn)vn的最早完成時(shí)間TE（vn）不增加的條件下，自發(fā)點(diǎn)v1最遲到達(dá)vi所需要的時(shí)間，稱為vi的最晚完成時(shí)間，記作TL（vi）。7.3 圖的矩陣表示7.3.1 圖的鄰接矩陣表示 定義7.25 設(shè)圖G的結(jié)點(diǎn)集合為V，邊集為E，且V=v1，v2，vn，令則稱矩陣Aaij為圖G的鄰接矩陣。定義7.26 設(shè)n階簡單有向圖G=，V=v1，v2，vn令 則稱矩陣Ppij為圖G的可

35、達(dá)矩陣。記作P（G），簡記為P。 7.3.2 圖的關(guān)聯(lián)矩陣表示 定義7.27 設(shè)無環(huán)無向圖G=，V=v1，v2，vn，E=e1，e2，em，則矩陣M（G）=（mij）nm，其中mij=稱M（G）為完全關(guān)聯(lián)矩陣。 定義7.28 設(shè)簡單有向圖G=，V=v1，v2，vn，E=e1，e2，em，則矩陣M（G）=（mij）nm，其中稱M（G）為G的完全關(guān)聯(lián)矩陣。7.4 歐拉圖7.4.1 歐拉圖的定義 定義7.29 給定無孤立結(jié)點(diǎn)圖G，如果圖中存在一條通過圖中各邊一次且僅一次的回路，則稱此回路為歐拉回路，具有歐拉回路的圖，稱為歐拉圖。如果圖中存在一條通過圖中各邊一次且僅一次的通路，則稱此通路為歐拉通路，具

36、有歐拉通路的圖，稱為半歐拉圖。 7.4.2 歐拉圖的判定1無向圖的歐拉定理 定理7.17 無向連通圖G是歐拉圖的充分必要條件是圖中各點(diǎn)的度數(shù)為偶數(shù)。 定理7.18 無向連通圖是半歐拉圖的充分必要條件是：圖中至多有兩個(gè)奇數(shù)度結(jié)點(diǎn)。 2有向圖的歐拉定理 定理7.19 設(shè)圖G是有向連通圖，圖G是歐拉圖的充分必要條件是：圖中每個(gè)結(jié)點(diǎn)的入度和出度相等。 定理7.20 設(shè)圖G是有向連通圖，圖G是半歐拉圖的充分必要條件是：至多有兩個(gè)結(jié)點(diǎn)，其中一個(gè)結(jié)點(diǎn)的入度比它的出度多1，另一個(gè)結(jié)點(diǎn)的出度比它的入度多1，而其他結(jié)點(diǎn)的入度和出度相等。 7.5 哈密爾頓圖 7.5.2 哈密爾頓圖的判定 定理7.21 設(shè)圖G=是哈

37、密爾頓圖，則對(duì)于結(jié)點(diǎn)集V的每個(gè)非空子集S，都有W（G-S）|S|成立，其中W（G-S）是G-S中的連通分支數(shù)。 定理7.22 設(shè)圖G是具有n個(gè)結(jié)點(diǎn)（v1，v2，vn）的無向簡單圖，如果圖G中任意兩個(gè)不同結(jié)點(diǎn)的度數(shù)之和大于等于n-1，即 deg(vi)+deg(vj)n-1則圖G具有哈密爾頓通路，即G是半哈密爾頓圖。 定理7.23 設(shè)圖G是具有n個(gè)結(jié)點(diǎn)（v1，v2，vn）的無向簡單圖，如果圖G中任意兩個(gè)不同結(jié)點(diǎn)的度數(shù)之和大于等于n，即deg（vi）+deg（vj）n則圖G具有哈密爾頓回路，即G為哈密爾頓圖。 定義7.31 給定圖G=，V中有n個(gè)結(jié)點(diǎn)，若將圖G中度數(shù)之和至少是n的非鄰接結(jié)點(diǎn)連接起來

38、得到圖G，對(duì)圖G重復(fù)上述步驟，直到不再有這樣的結(jié)點(diǎn)存在為止，所得到的圖，稱為圖G的閉包，記作C（G）。 定理7.24 當(dāng)且僅當(dāng)一個(gè)簡單圖G的閉包是哈密爾頓圖時(shí)，則圖G是哈密爾頓圖。 定理7.25 競賽圖必有哈密爾頓通路. 定理7.26 強(qiáng)連通的競賽圖必有哈密爾頓通路. 7.6 樹7.6.1 無向樹 1無向樹的定義與性質(zhì) 定義7.32 設(shè)T是無回路的無向簡單連通圖，則稱T為無向樹，或簡稱為樹。在樹中，度數(shù)為1的點(diǎn)稱為樹葉，度數(shù)大于1的點(diǎn)稱為內(nèi)結(jié)點(diǎn)或分枝點(diǎn)。 定理7.27 設(shè)T是含n個(gè)結(jié)點(diǎn)和m條邊的簡單無向圖，則下列各結(jié)論都是等價(jià)的，都可作為無向樹的定義。（1）T連通且無回路。（2）T中任意兩個(gè)不

39、同的結(jié)點(diǎn)間，有且僅有一條通路相連。（3）T無回路且n=m+1。（4）T連通且n=m+1。（5）T連通，但刪去樹中任意一條邊，則變成不連通圖。（6）T連通且無回路，若在T中任意兩個(gè)不鄰接的結(jié)點(diǎn)中添加一條邊，則構(gòu)成的圖包含唯一的回路。 2生成樹與最小生成樹 定理7.29 一條回路和任何一棵生成樹的補(bǔ)圖至少有一條公共邊。 定理7.30 有一個(gè)邊割集和任何生成樹至少有一條公共邊。 定義7.34 在圖的所有生成樹中，樹權(quán)之和最小的生成樹，稱為最小生成樹。 定理7.31 設(shè)圖有n個(gè)結(jié)點(diǎn)，可用下面的算法產(chǎn)生最小生成樹。（1）選取最小邊e1，設(shè)邊數(shù)k=1；（2）若k=n-1，結(jié)束，否則轉(zhuǎn)（3）；（3）設(shè)已選擇

40、邊為e1，e2，ek，在G中選擇不同于e1，e2，ek的邊ek+1，使ek+1是滿足e1，e2，ek，ek+1中無回路的權(quán)最小的邊。（4）k=k+1，轉(zhuǎn)（2）。 定義7.35 如果一個(gè)有向圖的底圖為無向樹，則該有向圖稱為有向樹。 定義7.36 在有向樹T中，如果有且僅有一個(gè)入度為0的點(diǎn)。其他點(diǎn)的入度均為1，則稱有向樹T為有根樹，簡稱根樹。入度為0的點(diǎn)稱為根，出度為0的點(diǎn)稱為樹葉或葉片，出度不為0的點(diǎn)稱為分枝點(diǎn)或內(nèi)結(jié)點(diǎn)。 定義7.37 根樹包含一個(gè)或多個(gè)結(jié)點(diǎn)，這些結(jié)點(diǎn)中某一個(gè)稱為根，其他所有結(jié)點(diǎn)被分成有限個(gè)子根樹。 定義7.38 在根樹中，如果每一個(gè)結(jié)點(diǎn)的出度小于或等于k，則稱這棵樹為k叉樹。若

41、每一個(gè)結(jié)點(diǎn)的出度恰好等于k或零，則稱這棵樹為完全k叉樹，若所有樹葉的層次相同，稱為正則k叉樹當(dāng)k=2時(shí)，稱為二叉樹。 7.6.3 周游算法 1前序周游算法 設(shè)需要周游的2叉樹為T，其左子樹為T1，右子樹為T2，則前序周游算法的遞歸定義為:（1）訪問T的根；（2）用前序周游算法遍歷左子樹T1；（3）用前序周游算法遍歷右子樹T2。2中序周游算法 其遞歸定義如下：（1）用中序周游算法遍歷T的左子樹；（2）訪問T的根；（3）用中序周游算法遍歷T的右子樹。 7.6.4 前綴碼與最優(yōu)樹 定義7.40 如果在碼中，沒有一個(gè)碼字是另一個(gè)碼字的前綴，則稱這樣的碼為前綴碼。 定理7.32 任意一棵給定的完全2叉樹，可以產(chǎn)生唯一的一個(gè)二元前綴碼。 定理7.33 任何一個(gè)前綴碼都對(duì)應(yīng)一棵完全2叉樹. 定義7.41 設(shè)