第8章 計算機(jī)專業(yè)應(yīng)用數(shù)學(xué)

第8章計算機(jī)專業(yè)應(yīng)用數(shù)學(xué)8.1行列式矩陣及其應(yīng)用(見第3章)8.2命題邏輯介紹8.3圖論及其應(yīng)用返回8.2命題邏輯介紹數(shù)理邏輯是用數(shù)學(xué)方法研究思維規(guī)律的一門學(xué)科.所謂數(shù)學(xué)方法是指用一套數(shù)學(xué)的符號系統(tǒng)來描述和處理思維的形式與規(guī)律.因此，數(shù)理邏輯又稱為符號邏輯.本章介紹數(shù)理邏輯中最基本的內(nèi)容一一命題邏輯.首先引人命題、命題公式等概念.然后，在此基礎(chǔ)上研究命題公式間的等值關(guān)系和蘊(yùn)含關(guān)系.8.2.1命題的概念1.命題人們的思維活動是靠自然語言來表達(dá)的.然而，由于自然語言易產(chǎn)生二義性，用它來表示嚴(yán)格的推理就不合適了.為了解決這個問題，在數(shù)理邏輯中引進(jìn)了一種形式化的語言，這就是一種符號語言.命題邏輯是數(shù)理邏輯中最基本的內(nèi)容，是以命題為基本對象的數(shù)學(xué)化的下一頁返回8.2命題邏輯介紹邏輯系統(tǒng).我們把能夠判斷真假的陳述句稱作命題.這種陳述句的判斷只有兩種可能的結(jié)果“真”或“假”，稱為命題的真值，其中真值為真(用1或T表示)的命題稱為真命題，真值為假(用0或F表示)的命題稱為假命題，因此，命題是具有唯一真值(真或假)的陳述句.例8-1判斷下列語句是不是命題.(1)13是質(zhì)數(shù).(2)3比5大.(3)我是大學(xué)生.(4)昨天是陰天.(5)明年國慶節(jié)是晴天.(6)宇宙中有些星球現(xiàn)在還沒有被發(fā)現(xiàn).上一頁下一頁返回8.2命題邏輯介紹(7)你上網(wǎng)了嗎?(8)請保持安靜!(9)今年春節(jié)真熱鬧啊!(10)x+i=1.(11)他在說謊.(12)他對這句話的判斷是錯誤的.例8-1中(1)～(6)都是命題,(7)～(12)都不是命題.說明:(1)是真命題.(2)是假命題.(3)的真值要看說話者本人是否是大學(xué)生而定.(4)的真值要看當(dāng)時的天氣而定.(6)的真值要到明年國慶節(jié)而定.(6)的真值隨著科學(xué)技術(shù)的發(fā)展總有一天能夠確定.(9}是疑問句.(8)是祈使句.(9)是感嘆句.(10)的真值無法確定.(11)和(12)雖然是陳述句，上一頁下一頁返回8.2命題邏輯介紹但是其表達(dá)的含義和結(jié)論之間有矛盾，這樣的語句稱為悖論.2.命題的表示命題的表示方法一般有如下三種:(1)用大寫字母A,B,C,...,y,Z來表示;(2)大寫字母加下標(biāo)的方式;(3)數(shù)字加中括號的方式.例如，A:他通過了這次考試;P1:他通過了這次考試;「10」:他通過了這次考試.表示命題的符號稱為命題標(biāo)識符，A,P1都是命題標(biāo)識符.表示任意命題的命題標(biāo)識符稱為命題變元.上一頁下一頁返回8.2命題邏輯介紹3.命題的分類命題分為原子命題和復(fù)合命題.我們把不能再分解為其他命題的命題稱為原子命題，由原子命題通過連接詞復(fù)合而成的命題稱為復(fù)合命題.例8-1中的(1)～(6)都是原子命題.而“王琳是學(xué)生黨員”就是復(fù)合命題，因為它是由原子命題“王琳是學(xué)生”和“王琳是黨員”復(fù)合而成.說明:“小李與小王是朋友”是原子命題，因為朋友關(guān)系必須是由兩個人構(gòu)成，單獨(dú)一個人不能構(gòu)成朋友關(guān)系.4.真值表將命題變元的所有取值可能全部列出來，構(gòu)成的一個表，以確定某個命題(或式子)的真值，該表稱為命題的真值表.上一頁下一頁返回8.2命題邏輯介紹8.2.2命題連接詞表示復(fù)合命題內(nèi)部聯(lián)結(jié)關(guān)系的符號，稱為命題連接詞.常見的命題連接詞有五個.1.否定連接詞若P是一個命題，復(fù)合命題“非P”稱為P的否定，記作﹁P.

﹁稱為否定連接詞.P的真值為真當(dāng)且僅當(dāng)﹁P的真值為假.真值表如表8-1所示.上一頁下一頁返回8.2命題邏輯介紹例8-2設(shè)P:承德是旅游城市，則﹁P:承德不是旅游城市.由于P的真值為1,所以﹁P的真值為0.說明:命題的否定對于命題的表示有多種解釋，只要能表達(dá)對原命題的否定含義就可以了，不要求說法完全一致.2.合取聯(lián)結(jié)詞若P,Q是兩個命題，則由合取聯(lián)結(jié)詞八和命題P,Q組成的復(fù)合命題P∧Q稱為PQ的合取式，讀作“P且Q".P∧Q為真當(dāng)且僅當(dāng)P,Q都為真.復(fù)合命題P∧Q的真值表如表8-2所示.合取詞是自然語言中的連接詞“并且”、“和”、“及”等的邏輯抽象.上一頁下一頁返回8.2命題邏輯介紹例8-3將下列命題符號化.(1)王紅既聰明又漂亮.(2)王紅雖聰明但不漂亮.(3)李大強(qiáng)喜歡上網(wǎng)和玩游戲.(4)2+2=4且雪是黑的.上一頁下一頁返回8.2命題邏輯介紹解設(shè)P:王紅聰明，Q:王紅漂亮，R:李大強(qiáng)喜歡上網(wǎng)，S:李大強(qiáng)喜歡玩游戲，M:2+2=4，N:雪是黑的.(1)“王紅既聰明又漂亮”可符號化為P∧Q.(2)“王紅雖聰明但不漂亮”可符號化為P∧﹁Q.(3)“李大強(qiáng)喜歡上網(wǎng)和玩游戲”可符號化為∧S.(4)“2+2=4且雪是黑的”可符號化為M∧V.3.析取連接詞若P,Q是兩個命題，則由析取連接詞∨和命題P,Q組成的復(fù)合命題P∨Q稱為P,Q的析取式，讀作“P或Q”.P∨Q為真當(dāng)且僅當(dāng)P,Q至少有一個為真，因此只有P,Q同時為假時，P∨Q才為假.復(fù)合命題P∨Q的真值表如表8-3所示.析取詞∨是自然語言中的連接詞“或者”、“或”等的邏輯抽象.上一頁下一頁返回8.2命題邏輯介紹例8-4判斷下列命題是否可表示成析取式并符號化.(1)明天下雨或濕度很高.(2)老王在教室里上課或者參加長跑比賽.解(1)設(shè)P:明天下雨，Q:明天濕度很高.則“明天下雨或濕度很高”可符號化為P∨Q.上一頁下一頁返回8.2命題邏輯介紹(2)設(shè)A:老王在教室里上課，B:老王參加長跑比賽.則“老王在教室里上課或者參加長跑比賽”不能表示成A∨B，但可以表示成(A∧﹁B)∨(﹁A∧B).例8-4命題(2)中的“或”為“不可兼或”用

來表示，其真值表見表8-4.上一頁下一頁返回8.2命題邏輯介紹注意:需要特殊說明的是，雖然析取可以理解成漢語中的“或者”、“或”等形式，但是并不是所有的漢語表達(dá)中的“或者”、“或”都可以理解成析取連接詞.如，“這個屋子里大概有30或40個同學(xué)上自習(xí)”，這里的“或”不能表示成析取，只是表示屋子里上自習(xí)的同學(xué)數(shù)不確定，大概有三四十個左右.4.條件聯(lián)結(jié)詞若P,Q是兩個命題，則由條件聯(lián)結(jié)詞~和命題P、Q組成的復(fù)合命題P→Q稱為P、Q的條件式，讀作“如果P，則Q".P→Q為假當(dāng)且僅當(dāng)P為真而Q為假.因此，P為假時，不管Q為真還是為假，P→Q都為真(我們稱其為邏輯學(xué)中善意的推測);而P,Q同時為真時，P→Q也為真.復(fù)合命題P→Q的真值表如表8-5所示.上一頁下一頁返回8.2命題邏輯介紹例8-5將下列命題符號化.(1)如果他努力學(xué)習(xí)，就會門門功課90分以上.(2)若∠1和∠2是對頂角，則∠1=∠2.解(1)設(shè)A:他努力學(xué)習(xí)，B:他門門功課90分以上.則“如果他努力學(xué)上一頁下一頁返回8.2命題邏輯介紹習(xí)，就會門門功課90分以上”可符號化為A→B.

(2)設(shè)A:∠1和∠2是對頂角，B:∠1=∠2.則“若∠1和∠2是對頂角，則∠1=∠2”可符號化為A→B.可見，A是B的充分條件，或B是A的必要條件.例8-6將下列命題符號化.(1)只要不下雨，我就騎自行車上班.(2)只有不下雨，我才騎自行車上班.解設(shè)P:天下雨，Q:我騎自行車上班.上一頁下一頁返回8.2命題邏輯介紹說明:在(1)中，“不下雨”是“我騎自行車上班”的充分條件.在(2)中，“不下雨”是“我騎自行車上班”的必要條件.5.雙條件連接詞若P,Q是兩個命題，則由雙條件連接詞H和命題P、Q組成的復(fù)合命題P?Q稱為P、Q的雙條件式，讀作“P當(dāng)且僅當(dāng)Q".P?Q為真當(dāng)且僅當(dāng)P、Q的真值相同.復(fù)合命題P?Q的真值表如表8-6所示.上一頁下一頁返回8.2命題邏輯介紹上一頁下一頁返回8.2命題邏輯介紹8.2.3命題公式1.命題公式的概念命題符號化的結(jié)果常以命題公式的形式呈現(xiàn)出來.那么，什么是命題公式?下面我們以遞歸的形式給出命題公式的定義.定義8.1(1)單個命題變元是命題公式;(2)若P是命題公式，則，P是命題公式;(3)若P、Q是命題公式，則P∧Q,P∨Q,P→Q,P?Q都是命題公式;(4)當(dāng)且僅當(dāng)有限次地應(yīng)用(1)、(2)、(3)所得到的包括命題變元、連接詞和圓括號的符號串是命題公式.上一頁下一頁返回8.2命題邏輯介紹命題公式簡稱公式.在命題公式的遞歸定義中，(1)是遞歸的基礎(chǔ)，(2)、(3)是歸納，(4)是界限.2.命題公式的賦值一個含有命題變元的命題公式是沒有確定真值的，只有將公式中的每個命題變元用指定的命題替代后，命題公式才有確定的真值.將命題變元指派為真命題相當(dāng)于指定其真值為1，將命題變元指派為假命題相當(dāng)于指定其真值為0.定義8.2設(shè)P1P2,…,Pn，是出現(xiàn)在命題公式中的全部命題變元，對P1,P2,...,Pn指定一組真值，稱這組真值為公式G的一個賦值(解釋)，記作I，公式G在賦值I下的真值記作T1(G).上一頁下一頁返回8.2命題邏輯介紹3.命題公式的真值表定義8.3將命題公式G在其所有賦值下所取真值列成一個表，稱為命題公式G的真值表.上一頁下一頁返回8.2命題邏輯介紹上一頁下一頁返回8.2命題邏輯介紹4.命題公式的分類定義8.4(1)若公式G在所有賦值下的取值都為真，則稱G為永真式(重言式);(2)若公式G在所有賦值下的取值都為假，則稱G為永假式(矛盾式);上一頁下一頁返回8.2命題邏輯介紹(3)若至少有一種賦值使公式G的取值為真，則稱G為可滿足式.由上述定義可知:(1)永真式一定是可滿足式，反之不一定.(2)永假式一定是不可滿足式.在例8-8中，(2)為永真式，(3)為永假式，(1)為可滿足式.8.2.4等價式例如，P→Q與﹁P∨Q形式上看來是兩個不同的命題公式，但在任意賦值下它們都具有相同的真值.定義8.5若命題公式A和B在任意賦值(指派)下都具有相同的真值，則稱A與B等價，記作

稱為命題等價式.上一頁下一頁返回8.2命題邏輯介紹(分配律)上一頁下一頁返回8.2命題邏輯介紹代入規(guī)則對永真式中任意一個命題變元，可用任意一個命題公式代人，所得公式仍為永真式.置換規(guī)則上一頁下一頁返回8.2命題邏輯介紹設(shè)公式Φ(A)是一個含有公式A的命題公式，Φ(B)是用公式B置換了Φ(A)中的A后得到的公式，若上一頁下一頁返回8.2命題邏輯介紹8.2.5蘊(yùn)涵式1.蘊(yùn)涵的概念邏輯的一個重要功能是研究推理.當(dāng)然，利用等價關(guān)系可以進(jìn)行推理，但在邏輯推理時，不一定必須依靠等價關(guān)系，在推理中更多的是用到蘊(yùn)涵關(guān)系.定義8.G設(shè)A、B是公式，若A→B是永真式，則稱A蘊(yùn)涵B，記作

稱為蘊(yùn)涵式.常用的墓本蘊(yùn)涌式:上一頁下一頁返回8.2命題邏輯介紹上一頁下一頁返回8.2命題邏輯介紹2.蘊(yùn)涵的性質(zhì)蘊(yùn)涵具有下列常用性質(zhì):上一頁下一頁返回8.2命題邏輯介紹上一頁下一頁返回8.2命題邏輯介紹8.2.6范式1.析取范式與特異析取范式1)析取范式的特點(diǎn):(1)析取范式是一個析取式.(2)析取范式中的每個析取項是一個合取式.(3)這個析取式只包含命題變元及其否定.2)特異析取范式的特點(diǎn)(1)特異析取范式是一個析取范式.(2)在特異析取范式的每個析取項中，該公式的所有命題變元均出現(xiàn)，它或以命題變元或以命題變元的否定形式出現(xiàn)，且僅出現(xiàn)一次.上一頁下一頁返回8.2命題邏輯介紹(2)利用等價式

將否定符號深入至命題變元，并利用

減少否定符號，使命題變元前的否定符號最多為一個.上一頁下一頁返回8.2命題邏輯介紹(3)利用分配律將公式化歸成析取式.(4)除去析取范式中所有為永假的析取項，即出現(xiàn)有﹁P∧P形式的項.(5)若析取項中同一命題變元出現(xiàn)多次，則利用等價式

將其簡化成只出現(xiàn)一次.(6)若析取項中不是公式中的所有命題變元都出現(xiàn)，利用

在析取項中將變元Q或P補(bǔ)充進(jìn)去，且利用分配律將它展開成幾個析取項，并除去相同之析取項.上一頁下一頁返回8.2命題邏輯介紹2.合取范式與特異合取范式1)合取范式的特點(diǎn)(1)合取范式是一個合取式.(2)合取范式中的每個合取項是一個析取式.上一頁下一頁返回8.2命題邏輯介紹(3)這個合取式只包含命題變元及其否定.2)特異合取范式的特點(diǎn)(1)特異合取范式是一個合取范式.(2)在特異合取范式的每個合取項中，該公式的所有命題變元均出現(xiàn)，它或以命題變元或以命題變元的否定形式出現(xiàn)，且僅出現(xiàn)一次.上一頁下一頁返回8.2命題邏輯介紹將公式中出現(xiàn)的連接詞→及?之處化歸成合取式.(2)利用等價式

將否定符號深入至命題變元，并利用

減少否定符號，使命題變元前的否定符號最多為一個.(3)利用分配律將公式化歸成合取式.(4)除去合取范式中所有為永真的合取項，即出現(xiàn)有

形式的項.(5)若合取項中同一命題變元出現(xiàn)多次，則利用等價式

將其簡化成只出現(xiàn)一次.(6)若合取項中不是公式中的所有命題變元都出現(xiàn)，利用

或

在合取項中將變元Q或P補(bǔ)充上一頁下一頁返回8.2命題邏輯介紹進(jìn)去，且利用分配律將它展開成幾個合取項，并除去相同之合取項.上一頁返回8.3圖論及其應(yīng)用圖論(GraphTheory)是數(shù)學(xué)的一個分支.它以圖為研究對象.圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個事物間具有這種關(guān)系.8.3.1基本概念1.圖的基本概念現(xiàn)實世界中很多狀態(tài)可以用某種圖形來描述，這種圖形是由一些點(diǎn)和一些連接兩點(diǎn)間的連線所組成，對于點(diǎn)的位置及連線的長度無關(guān)緊要.例如，有a,b,c,d四個足球隊進(jìn)行友誼比賽.為了描述4個隊之間比賽的情況，可以用圖8.1來表示.下一頁返回8.3圖論及其應(yīng)用在圖8.1中4個小圓圈分別表示這四個足球隊，稱之為結(jié)點(diǎn).如果兩隊進(jìn)行過比賽，則在表示這兩隊的結(jié)點(diǎn)之間用一條線連接起來，稱之為邊.設(shè)A,B為任意的兩個集合，{(a,b)}|a A∧b B}稱為A上一頁下一頁返回8.3圖論及其應(yīng)用解圖8.2中分別給出了無向圖G和有向圖D的圖形.上一頁下一頁返回8.3圖論及其應(yīng)用定義8.8如果兩個結(jié)點(diǎn)之間有多條邊(對于有向圖，則有多條同方向的邊)，則稱這些邊為平行邊，兩結(jié)點(diǎn)a,h間平行邊的條數(shù)稱為邊的重數(shù).含有平行邊的圖稱為多重圖，不含平行邊和自回路的圖稱為簡單圖.2.圖中結(jié)點(diǎn)的度數(shù)我們常常需要關(guān)心圖中有多少條邊與某一結(jié)點(diǎn)關(guān)聯(lián)，這就引出了圖的一個重要概念一結(jié)點(diǎn)的度.上一頁下一頁返回8.3圖論及其應(yīng)用如圖8.2(a)中，上一頁下一頁返回8.3圖論及其應(yīng)用如圖8.2(b)中，上一頁下一頁返回8.3圖論及其應(yīng)用由此結(jié)點(diǎn)數(shù)|V1|必為偶數(shù).定義8.10在圖中，度數(shù)為0的結(jié)點(diǎn)稱為孤立點(diǎn).如圖8.2(b)中，結(jié)點(diǎn)e為0度，是一個孤立點(diǎn).3.幾種常見的圖定義8.11具有n個結(jié)點(diǎn)和m條邊的圖稱為(n,m)圖.一個(n,0)圖稱為零圖(即該圖只有n個孤立結(jié)點(diǎn)).只有一個結(jié)點(diǎn)的圖，即(1,0)圖稱為平凡圖.定義8.12任意兩個不同的結(jié)點(diǎn)都是鄰接的簡單圖稱為完全圖.n個結(jié)點(diǎn)的無向完全圖記為Kn，其邊的條數(shù)為n(n一1）/2.從圖8.3中的K3和K4看出K3有3條邊，K4有6條邊.容易證明Kn(n-1)/2條邊.上一頁下一頁返回8.3圖論及其應(yīng)用定義8.13設(shè)G=〈V（G）,E（G）〉是一個具有ｎ個結(jié)點(diǎn)的簡單圖.以V為結(jié)點(diǎn)集，以從完全圖Kn，中刪去G的所有邊后得到的圖稱為G的補(bǔ)圖(或稱為G的補(bǔ))，記為 .如圖8.4給出了一個圖G和G的補(bǔ).定義8.14給每條邊賦以一個實數(shù)(稱為該邊的權(quán))的圖叫有權(quán)圖.邊e的權(quán)記為WG(e).有權(quán)圖G=〈V(G),E(G)〉中所有邊的權(quán)之和稱作圖G的權(quán)，記為WG(G).例8-14證明在任何一個有6個人的小組中，存在3個人互相認(rèn)識，或者存在個人互相不認(rèn)識(拉姆齊問題).分析用6個結(jié)點(diǎn)來代表人，并用鄰接性來表示兩人之間認(rèn)識關(guān)系.這樣一來，該例就是要證明:任意一個有6個結(jié)點(diǎn)的圖中G，或者有3個互相鄰接的點(diǎn)，或上一頁下一頁返回8.3圖論及其應(yīng)用上一頁下一頁返回8.3圖論及其應(yīng)用4.子圖在描述和研究圖的性質(zhì)時，還涉及到另一重要概念一子圖.圖8.5給出了圖G以及它的真子圖G1和生成子圖G2.上一頁下一頁返回8.3圖論及其應(yīng)用8.3.2路與回路1.路、回路和連通性上一頁下一頁返回8.3圖論及其應(yīng)用例如在圖8.6中，下面我們利用通路的概念解決一個古老的著名問題.例8-15(渡河問題)一個擺渡人，要把一只狼、一只羊和一捆干草運(yùn)過河去，河上有一只術(shù)船，每次除了人以外，只能帶一樣?xùn)|西.并且，上一頁下一頁返回8.3圖論及其應(yīng)用如果人不在旁時，狼就要吃羊，羊就要吃干草.問這人應(yīng)該怎樣才能把它們運(yùn)過河去?解用F表示擺渡人，W表示狼，S表示羊，H表示干草.如果用FWSH表示人和其他三樣?xùn)|西在河的左岸.這樣，在左岸全部可能出現(xiàn)的狀態(tài)如下表所示16種:這里Φ表示左岸是空集，即人、狼、羊、干草都已運(yùn)到右岸去了.上一頁下一頁返回8.3圖論及其應(yīng)用根據(jù)題意，考查一下這16種情況就可以知道，其中有6種情況不允許出現(xiàn).它們分別是:WSH、FW、FH、WS、SH、F.如FH表示人和干草在左岸，而羊和狼在右岸，狼要吃羊，這當(dāng)然是不行的.因此，允許出現(xiàn)的情況只有10種，如圖8.7所示.定義8.18在圖G中，若結(jié)點(diǎn)vi到vj有路連接(這時稱vi和vj是連通的)，則其中長度最短的路稱為從vi到vj的短程.短程的長度稱為vi到vj的距離，用符d(vi，vj)表示.例如在圖8.6中，d(v1，v3)=2.定理8.3設(shè)G是具有n個結(jié)點(diǎn)的圖，如果從結(jié)點(diǎn)vi到另一結(jié)點(diǎn)vj，存在一條路，則其短程是一條長度不大于n-1的通路.證明設(shè)從結(jié)點(diǎn)vi到結(jié)點(diǎn)vj存在一條路μ，該路上的結(jié)點(diǎn)序列為

可用反證法證明，當(dāng)μ是短程時，μ一定是通路.上一頁下一頁返回8.3圖論及其應(yīng)用推論設(shè)圖G=(V,E)，|V|=n,則G中任一基本回路的長度不大于n.如果一個圖的任何兩個結(jié)點(diǎn)之間都有一條路，那么我們稱這個圖是連通的，否則是不連通的.定義8.19圖G的一個連通的子圖(稱為連通子圖)若不包含在G的任何更大的連通子圖中，它就被稱作G的連通分支，常把圖G的連通分支數(shù)記作W(G).在圖8.8中，G是不連通的，W(G)=2，而G′是連通的，W(G′)=1.任何一個圖都可劃分為若干個連通分支.顯然，僅當(dāng)圖G的連通分支數(shù)W(G)=1時，圖G是連通的.2.有權(quán)圖的最短路徑問題有權(quán)圖經(jīng)常出現(xiàn)在圖的應(yīng)用中.如在交通圖中，權(quán)可以表示兩地的距離;在通訊圖中，權(quán)可以表示各種通訊線路的建造或維修費(fèi)用等等.上一頁下一頁返回8.3圖論及其應(yīng)用上一頁下一頁返回8.3圖論及其應(yīng)用上一頁下一頁返回8.3圖論及其應(yīng)用為清楚起見，將本算法用流程圖表示，見圖8.9所示.例8-16在圖8.10所示的有權(quán)圖中，用迪克斯特拉算法求結(jié)點(diǎn)v0到其余各點(diǎn)的最短路徑.上一頁下一頁返回8.3圖論及其應(yīng)用算法共執(zhí)行6次，求解示意圖見圖8.11所示.上一頁下一頁返回8.3圖論及其應(yīng)用上一頁下一頁返回8.3圖論及其應(yīng)用8.3.3圖的矩陣表示上面介紹了圖的一種表示方法一用圖形表示圖.它的優(yōu)點(diǎn)是形象直觀，但是這種表示在結(jié)點(diǎn)與邊的數(shù)日很多時是不方便的.下面介紹另一種表示方法一用矩陣表示圖.利用這種方法，可以把圖用矩陣存儲在計算機(jī)中，利用矩陣的運(yùn)算還可以了解到它的一些有關(guān)性質(zhì).定義8.21設(shè)G=(V,E)是有n個結(jié)點(diǎn)的圖，則n階方陣A=(aij)稱為G的鄰接矩陣.其中如圖8.12所示的圖G，其鄰接矩陣A為上一頁下一頁返回8.3圖論及其應(yīng)用顯然，無向圖的鄰接矩陣一定是對稱的.在鄰接矩陣A的冪A2，A3，…矩陣中，每個元素有特定的含義，下面定理進(jìn)行了說明.上一頁下一頁返回8.3圖論及其應(yīng)用上一頁下一頁返回8.3圖論及其應(yīng)用例8-17圖G=(V,E)的圖形如圖8.13所示，求鄰接矩陣A和A2,A3,，并分析其元素的圖論意義.解上一頁下一頁返回8.3圖論及其應(yīng)用上一頁下一頁返回8.3圖論及其應(yīng)用上一頁下一頁返回8.3圖論及其應(yīng)用8.3.4樹樹是圖論中的一個重要概念.在1847年克?；舴蚓吞岢鲇脴涞睦碚搧硌芯侩娋W(wǎng)絡(luò)，1857年凱萊在計算有機(jī)化學(xué)中C2H2n+2的同分異構(gòu)物數(shù)日時一也用到了樹的理論.而樹在計算機(jī)科學(xué)中應(yīng)用更加廣泛.本節(jié)介紹樹的基本知識，其中談到的圖都假定為簡單圖.1.樹的概念定義8.22一個連通無回路圖稱為樹.樹中度數(shù)為1的結(jié)點(diǎn)稱為樹葉(或終端結(jié)點(diǎn))，度數(shù)大于1的結(jié)點(diǎn)稱為分枝點(diǎn)(或內(nèi)點(diǎn)，或非終端結(jié)點(diǎn))一個無回路圖稱為森林.顯然，若圖G是森林，則G的每個連通分支是樹.如圖8.14(a)圖所示的是一棵樹;（b）圖所示的是森林.上一頁下一頁返回8.3圖論及其應(yīng)用定理8.5一個(n,m)圖G是樹的充分必要條件是G連通且m=n-1.上一頁下一頁返回8.3圖論及其應(yīng)用定理8.G設(shè)T是一棵(n,m)樹，則T有如下性質(zhì):(1)T中去掉任意一條邊后，所得的圖G是不連通的.(2)T中每一對結(jié)點(diǎn)間有且僅有一條通路相連.(3)在T中不相鄰接的任意兩結(jié)點(diǎn)間添加一條邊后形成的圖有且僅有一個回路.(4)若樹T的結(jié)點(diǎn)數(shù)n≥2，則T至少有兩片樹葉.證明(1)如果G是連通的，那么G仍是樹.由定理8.5知，G有n-1條邊，即與T的邊數(shù)相同，矛盾.(2)因為T連通，由定理8.3知，T的任一對結(jié)點(diǎn)u、v之間有一條通路相連.若u,v間通路不唯一，則T中必有回路，與樹的定義矛盾.所以僅有一條通路連接u與v.上一頁下一頁返回8.3圖論及其應(yīng)用上一頁下一頁返回8.3圖論及其應(yīng)用由定理8.5所描述的樹的特征得出:在結(jié)點(diǎn)數(shù)給定的所有圖中，樹是邊數(shù)最少的連通圖，是邊數(shù)最多的無回路圖.由此可知，在一個(n，m)圖G中，若m<n-1,則G是不連通的;若m>n-1，則G必定有回路.2.生成樹定義8.23若連通圖G的生成子圖是一棵樹，則稱該樹是G的生成樹，記為TG.生成樹TG中的邊稱為樹枝，圖中其他邊稱為TG的弦，所有這些弦的集合稱為TG的補(bǔ).如圖8.15(b)所示的樹T1是圖8.15(a)的生成樹，而8.15(c)(d)所示的樹T2,T3不是8.15(a)圖的生成樹一般的，圖的生成樹不唯一上一頁下一頁返回8.3圖論及其應(yīng)用例8-18某地要興建5個工廠，擬修筑道路連接這5處.經(jīng)勘測其道路可依如圖8.16的無向邊鋪設(shè).為使這5處都有道路相通，問至少要鋪幾條路?解這實際上是求G的生成樹的邊數(shù)問題.

一般情況下，設(shè)連通圖有n個結(jié)點(diǎn)，m條邊.由樹的性質(zhì)知，T有n個結(jié)點(diǎn)，n-1條樹枝，m-n+1條弦.在圖8.16中，n=5，則n-1=5-1=4,所以至少要修4條路才行.3.最小生成樹定義8.24設(shè)G=(V,E)是一連通的有權(quán)圖，則G中具有最小權(quán)的生成樹TG稱為G的最小生成樹.求最小生成樹問題是有實際意義的.上一頁下一頁返回8.3圖論及其應(yīng)用上一頁下一頁返回8.3圖論及其應(yīng)用例8-19求圖8.17中有權(quán)圖的最小生成樹.解因為圖中n=8，所以按算法要執(zhí)行n-1=7次，其過程見圖8.17中(a)～(g)8.3.5根樹及其應(yīng)用1.根樹、有序樹、M叉樹定義8.25一個有向圖，若不考慮邊的方向，它是一棵樹，則這個有向圖稱為有向樹一棵有向樹，如果僅有一個結(jié)點(diǎn)的人度為0，其余所有結(jié)點(diǎn)的人度都為1,則稱為根樹，其中人度為0的結(jié)點(diǎn)稱為根，出度為0的結(jié)點(diǎn)稱為葉，出度不為0的結(jié)點(diǎn)稱為分枝點(diǎn)或內(nèi)點(diǎn).如圖8.18(a)表示一棵根樹，其中v1為根，v2，v3為分枝點(diǎn)，其余結(jié)點(diǎn)為葉，一般情況下，習(xí)慣把根樹的根畫在上方，葉畫在下方.這樣就可以省去根樹的箭頭，如上一頁下一頁返回8.3圖論及其應(yīng)用圖8.18(b).在根樹中，稱從樹根到結(jié)點(diǎn)v的距離為該點(diǎn)的層次.這樣對圖8.17中的根樹，v1的層次為0，v2、v3的層次為1，其余結(jié)點(diǎn)的層次均為2.我們用家族關(guān)系表示根樹中各結(jié)點(diǎn)的關(guān)系.上一頁下一頁返回8.3圖論及其應(yīng)用定義8.28如果在根樹中規(guī)定了每一層次上結(jié)點(diǎn)的次序，這樣的根樹稱為有序樹.在有序樹中規(guī)定同一層次結(jié)點(diǎn)的次序是從左至右.在樹的實際應(yīng)用中，經(jīng)常研究完全刀m叉樹.定義8.29在根樹中，若每個結(jié)點(diǎn)的出度小于或等于m，則稱這棵樹為m叉樹.如果每個結(jié)點(diǎn)的出度恰好等于0或m，則稱這棵樹為完全m叉樹.二又樹的每個結(jié)點(diǎn)v至多有兩棵子樹，分別稱為v的左子樹和右子樹.例8-20甲、乙兩人進(jìn)行象棋比賽，規(guī)定三局兩勝，表示出比賽可能出現(xiàn)的各種情況.解圖8.19表示了比賽可能出現(xiàn)的所有情況，圖中結(jié)點(diǎn)標(biāo)甲者表示甲勝，標(biāo)乙者表示乙勝.由定義可知，這是一顆完全二又樹.上一頁下一頁返回8.3圖論及其應(yīng)用2.二叉樹m叉樹中，二叉樹應(yīng)用得最為廣泛.由于在計算機(jī)中最易處理的是二叉樹，所以常常要把一棵有序樹轉(zhuǎn)換為二叉樹.轉(zhuǎn)換的一般步驟為:(1)從根開始，保留每個父親與其最左邊孩子的連線，撤銷與別的孩子的連線;(2)兄弟間用從左向右的有向邊連接;(3)用如下方法選定二叉樹的左孩子和右孩子:直接處于給定結(jié)點(diǎn)下面的結(jié)點(diǎn)作為左孩子;對于同一水平線上與給定結(jié)點(diǎn)右鄰的結(jié)點(diǎn)作為右孩子，依次類推.例8-21將圖8.20(a)所示的三叉樹轉(zhuǎn)換為一棵二叉樹.解對圖8.20(a)進(jìn)行步驟(1),（2)得8.20（b)，再按步驟(3)得8.20(c).圖8.20(c)即為所求的二叉樹.上一頁下一頁返回8.3圖論及其應(yīng)用反過來，我們一也可將8.20(c)還原為8.20(a).一個森林一也可轉(zhuǎn)換為二叉樹.其步驟為:(1)先把森林中的每一棵樹表示成一棵二叉樹;(2)除第一棵二叉樹外，依次將每棵二叉樹作為左邊二叉樹的根的右子樹，直到所有的二叉樹都連成一棵二叉樹為止.例8-22將圖8.21(a)所示的森林轉(zhuǎn)換為一棵二叉樹.解如圖8.21(b)的二叉樹即為所求.

反過來，我們一也可將二叉樹轉(zhuǎn)換成森林.研究二叉樹有一個十分重要的問題，就是要找到一些方法能系統(tǒng)地訪問樹的結(jié)點(diǎn)，使得每個結(jié)點(diǎn)恰好被訪問一次，這就是二叉樹的遍歷問題.上一頁下一頁返回8.3圖論及其應(yīng)用下面介紹二又樹的三種常用的遍歷方法.1)先根次序遍歷法，分三步.(1)訪問根;(2)按先根次序遍歷根的左子樹;(3)按先根次序遍歷根的右子樹.2)中根次序遍歷法，分3步.(1)按中根次序遍歷根的左子樹;(2)訪問根;(3)按中根次序遍歷根的右子樹.3)后根次序遍歷法，分3步.(1)按后根次序遍歷根的左子樹;(2)按后根次序遍歷根的右子樹;上一頁下一頁返回8.3圖論及其應(yīng)用

(3)訪問根.

對一棵樹的遍歷有兩種方法，即先根次序遍歷和后根次序遍歷.以圖8.21(a)和相應(yīng)的二又樹圖8.21(c)為例討論如下:圖8.21(a)的先根次序遍歷的結(jié)果為圖8.21(c)的先根次序遍歷的結(jié)果一也為圖8.21(a)的后根次序遍歷的結(jié)果為圖8.21(c)的中根次序遍歷的結(jié)果一也為分析以上結(jié)果可以看出如下結(jié)論:(1)樹的先根次序正是相應(yīng)二叉樹的先根次序;(2)樹的后根次序正是相應(yīng)二叉樹的中根次序.該結(jié)果具有普遍的意義.上一頁下一頁返回8.3圖論及其應(yīng)用定義8.30在根樹中，一個結(jié)點(diǎn)的通路長度，就是從樹根到此結(jié)點(diǎn)通路的邊數(shù).把