離散數(shù)學(xué)6-8章課件

1、圖論簡(jiǎn)介圖論是一個(gè)古老的數(shù)學(xué)分支，它起源于游戲難題的研究。圖論的內(nèi)容十分豐富，應(yīng)用得相當(dāng)廣泛，許多學(xué)科，諸如運(yùn)籌學(xué)、信息論、控制論、網(wǎng)絡(luò)理論、博弈論、化學(xué)、生物學(xué)、物理學(xué)、社會(huì)科學(xué)、語(yǔ)言學(xué)、計(jì)算機(jī)科學(xué)等，都以圖作為工具來(lái)解決實(shí)際問題和理論問題。隨著計(jì)算機(jī)科學(xué)的發(fā)展，圖論在以上各學(xué)科中的作用越來(lái)越大，同時(shí)圖論本身也得到了充分的發(fā)展。第八章 圖論 第一節(jié) 圖的基本概念 內(nèi)容：有向圖，無(wú)向圖的基本概念。重點(diǎn)：1、有向圖，無(wú)向圖的定義， 2、圖中頂點(diǎn)，邊，關(guān)聯(lián)與相鄰，頂點(diǎn)度數(shù)等基本概念，3、各頂點(diǎn)度數(shù)與邊數(shù)的關(guān)系及推論，內(nèi)容：有向圖，無(wú)向圖的基本概念。5、圖的同構(gòu)的定義。重點(diǎn)：4、簡(jiǎn)單圖，完全圖，子圖

2、，補(bǔ)圖的概念，一、圖的概念。1、定義。無(wú)序積2、圖的表示法。有向圖，無(wú)向圖的頂點(diǎn)都用小圓圈表示。無(wú)向邊連接頂點(diǎn)的線段。有向邊以為始點(diǎn)，以為終點(diǎn)的有向線段。圖形表示如右：例1、(2) 有向圖，3、相關(guān)概念。(1) 有限圖都是有限集的圖。階圖的圖。零圖的圖。特別，若又有，稱平凡圖。(2) 關(guān)聯(lián) (邊與點(diǎn)關(guān)系)設(shè)邊(或)，則稱與(或)關(guān)聯(lián)。3、相關(guān)概念。(2)3、相關(guān)概念。(2) 懸掛點(diǎn)只有一條邊與其關(guān)聯(lián)的點(diǎn)，所對(duì)應(yīng)的邊叫懸掛邊。(3) 平行邊關(guān)聯(lián)于同一對(duì)頂點(diǎn)的若干條邊稱為平行邊。平行邊的條數(shù)稱為重?cái)?shù)。多重圖含有平行邊的圖。簡(jiǎn)單圖不含平行邊和環(huán)的圖。如例1的(1)中，與關(guān)聯(lián)的次數(shù)均為1，與關(guān)聯(lián)的次數(shù)

3、為2，邊都是相鄰的，為孤立點(diǎn)，為懸掛點(diǎn)，為懸掛邊，為環(huán)，為平行邊，重?cái)?shù)2， 為多重圖。例如：二、頂點(diǎn)的度數(shù)，握手定理。1、頂點(diǎn)的度數(shù) (簡(jiǎn)稱度)。無(wú)向圖的度數(shù)記，指與，相關(guān)聯(lián)的邊的條數(shù)。有向圖的度數(shù)，二、頂點(diǎn)的度數(shù)，握手定理。1、頂點(diǎn)的度數(shù) (簡(jiǎn)稱度)。最大度 最小度對(duì)有向圖相應(yīng)地還有，。如例1的(2)中，。設(shè)為圖的頂點(diǎn)集，稱 為的度數(shù)序列。2、握手定理。定理1：設(shè)圖為無(wú)向圖或有向圖，為邊數(shù))，(則定理2：設(shè)為有向圖，則，。2、握手定理推論：任何圖中，度為奇數(shù)的頂點(diǎn)個(gè)數(shù)為偶數(shù)。 三、子圖，補(bǔ)圖。導(dǎo)出子圖非空，以為頂點(diǎn)集，以兩端均在中的邊的全體為邊集的的子圖，稱的導(dǎo)出子圖。非空，以為邊集，以中邊

4、關(guān)聯(lián)的頂點(diǎn)的全體為頂點(diǎn)集的的子圖，稱的導(dǎo)出子圖。例3、上圖中，(1)(6)都是(1)的子圖，其中(2)(6)為真子圖，(1)(5)為生成子圖。如例3中，四、圖的同構(gòu)。定義：設(shè)兩個(gè)無(wú)向圖，若存在雙射函數(shù)，使得對(duì)于任意的，當(dāng)且僅當(dāng)并且與重?cái)?shù)相同，則稱與同構(gòu)，記作。例4、例5、(1) 畫出4個(gè)頂點(diǎn)，3條邊的所有非同構(gòu)的無(wú)向簡(jiǎn)單圖。解：只有如下3個(gè)圖：例5、(2) 畫出3個(gè)頂點(diǎn)，2條邊的所有非同構(gòu)的有向簡(jiǎn)單圖。解：只有如下4個(gè)圖：第二節(jié) 路徑和回路（1） 內(nèi)容：圖的通路，回路，連通性。重點(diǎn)：1、通路，回路，簡(jiǎn)單通路，回路，初級(jí)通路，回路的定義，2、圖的連通性的概念，3、短程線，距離的概念。一、路徑，回

5、路。1、路徑 (回路)中頂點(diǎn)和邊的交替序列，其中(無(wú)向圖)，或(有向圖)，始點(diǎn)，終點(diǎn)，稱為到的通路。當(dāng)時(shí)，為回路。一、路徑，回路。2、簡(jiǎn)單路徑，簡(jiǎn)單回路。簡(jiǎn)單路徑 (跡)：同一條邊不出現(xiàn)兩次基本路徑（鏈）：同一頂點(diǎn)不出現(xiàn)兩次簡(jiǎn)單回路 (閉跡)：沒有相同邊的回路基本回路：通過(guò)各頂點(diǎn)不超過(guò)一次的回路一、路徑，回路?；韭窂?(回路)簡(jiǎn)單路徑 (回路)，但反之不真。3、路徑，回路的長(zhǎng)度中邊的數(shù)目。例1、(1)圖(1)中，從的路徑有：到長(zhǎng)度3長(zhǎng)度6長(zhǎng)度6例1、(1)圖(1)中，從的路徑有：到基本路徑簡(jiǎn)單路徑復(fù)雜通路例1、(2)長(zhǎng)度3長(zhǎng)度4長(zhǎng)度7圖(2)中過(guò))有：的回路 (從到例1、(2)基本回路(圈)

6、基本回路(圈)復(fù)雜回路圖(2)中過(guò))有：的回路 (從到4、性質(zhì)。定理1：階圖中，若從頂點(diǎn)到存在路徑，則從到存在長(zhǎng)度小于等于在一個(gè)的基本路徑。（定理8.2-1）4、性質(zhì)。定理2：階圖中，若到自身存在一個(gè)簡(jiǎn)單回路，則從到自身存在長(zhǎng)度小于等于的基本回路。（定理8.2-2）在一個(gè)二、圖的連通度。1、連通，可達(dá)。無(wú)向圖中，從到存在通路，稱到是連通的(雙向)。有向圖中，從到存在通路，稱可達(dá)(注意方向)。2、短程線，距離。短程線連通或可達(dá)的兩點(diǎn)間長(zhǎng)度最短的通路。距離短程線的長(zhǎng)度，記無(wú)向圖有向圖3、無(wú)向圖的連通。為連通圖是平凡圖，或都是連通的。中任兩點(diǎn)為非連通圖中至少有兩點(diǎn)不連通。3、無(wú)向圖的連通。設(shè)是一個(gè)無(wú)

7、向圖，是中頂點(diǎn)之間的連通關(guān)系，則是等價(jià)關(guān)系。設(shè)將劃分成個(gè)等價(jià)類：，由它們導(dǎo)出的子圖稱為的連通分支，其個(gè)數(shù)記為4、有向圖的連通。中任一對(duì)頂點(diǎn)都互相可達(dá)(雙向)中任一對(duì)頂點(diǎn)至少一向可達(dá)略去中有向邊的方向后得到的無(wú)向圖連通連通強(qiáng)連通單向連通弱連通強(qiáng)連通單向連通弱連通例2、強(qiáng)連通單向連通例2、單向連通弱連通非連通圖8.2 路徑與回路（2）內(nèi)容：歐拉、哈密爾頓路徑、賦權(quán)圖中的最短路徑。重點(diǎn)：1、歐拉圖的定義，無(wú)向圖是否具有 歐拉回路的判定2、迪克斯特拉算法計(jì)算賦權(quán)圖的最短路徑了解：無(wú)向圖是否具有哈密爾頓回路的判定。一、歐拉回路問題的提出。1736年，瑞士數(shù)學(xué)家歐拉，哥尼斯堡七橋問題二、定義。歐拉通路 (

8、歐拉跡)通過(guò)圖中每條邊一次且僅一次，并且過(guò)每一頂點(diǎn)的通路。歐拉回路 (歐拉閉跡)通過(guò)圖中每條邊一次且僅一次，并且過(guò)每一頂點(diǎn)的回路。歐拉圖存在歐拉回路的圖。注意：(1) 歐拉通路與歐拉回路不同。(2) 歐拉圖指具有歐拉回路(并非通路)的圖。(3) 歐拉通路(回路)必是簡(jiǎn)單通路(回路)。(4) 連通是具有歐拉通路(回路)的必要條件。(5) 歐拉通路(回路)是經(jīng)過(guò)圖中所有邊的通路(回路)中最短的通路(回路)。三、無(wú)向圖是否具有歐拉通路或回路的判定。有歐拉通路連通，中只有兩個(gè)奇度頂點(diǎn)(它們分別是歐拉通路的兩個(gè)端點(diǎn))。有歐拉回路(為歐拉圖)連通，中均為偶度頂點(diǎn)。例1、以下圖形能否一筆畫成？例1、以下圖形

9、能否一筆畫成？例2、兩只螞蟻比賽問題。兩只螞蟻甲、乙分別處在圖中的頂點(diǎn)處，并設(shè)圖中各邊長(zhǎng)度相等。甲提出同乙比賽：從它們所在頂點(diǎn)出發(fā)，走過(guò)圖中所有邊最后到達(dá)頂點(diǎn)處。如果它們速度相同，問誰(shuí)最先到達(dá)目的地？四、有向圖是否具有歐拉通路或回路的判定。有歐拉通路連通，除兩個(gè)頂點(diǎn)外，其余頂點(diǎn)的入度均等于出度，這兩個(gè)特殊的頂點(diǎn)中，一個(gè)頂點(diǎn)的入度比出度大1，另一個(gè)頂點(diǎn)的入度比出度小1。有歐拉回路(為歐拉圖)連通，中所有頂點(diǎn)的入度等于出度。例3、判斷以下有向圖是否歐拉圖。二、哈密爾頓圖一、問題的提出。1859年，英國(guó)數(shù)學(xué)家哈密爾頓，周游世界游戲。二、哈密爾頓圖。哈密爾頓通路通過(guò)圖中每個(gè)頂點(diǎn)一次且僅一次的通路。哈密

10、爾頓回路通過(guò)圖中每個(gè)頂點(diǎn)一次且僅一次的回路。哈密爾頓圖存在哈密爾頓回路的圖。注意：(1) 哈密爾頓通路與哈密爾頓回路不同。(2) 哈密爾頓圖是指具有哈密爾頓回路(并非通路)的圖。(3) 哈密爾頓通路(回路)必是初級(jí)通路(回路)。 (4) 連通是具有哈密爾頓通路(回路)的必要條件。注意：(5) 若圖通路。具有哈密爾頓回路，則必有哈密爾頓(6) 階圖的哈密爾頓通路長(zhǎng)為，回路長(zhǎng)為。三、判定。采用嘗試的辦法。例1、判斷下圖是否具有哈密爾頓回路，通路。解：存在哈密爾頓通路，但不存在哈密爾頓回路。例1、判斷下圖是否具有哈密爾頓回路，通路。解：是哈密爾頓圖，存在哈密爾頓回路和通路。例1、判斷下圖是否具有哈密

11、爾頓回路，通路。解：不存在哈密爾頓回路，也不存在哈密爾頓通路。 哈密爾頓回路存在的兩件個(gè)充分條件定理8.2-13 設(shè) 是具有 個(gè)頂點(diǎn)的簡(jiǎn)單無(wú)向圖，若在G中每一對(duì)頂點(diǎn)的次數(shù)之和大于n,則在G中存在一條哈密爾頓回路。 推論8.2-13 在簡(jiǎn)單無(wú)向圖中，若每一頂點(diǎn)的次數(shù)則在G中存在一條哈密爾頓回路。70三、最短路徑定義 設(shè)G=(V，E)是無(wú)向簡(jiǎn)單圖，如果對(duì)E中每條邊e都有一個(gè)實(shí)數(shù)w(e)附著其上，則稱G為權(quán)圖，稱w(e)為邊e的權(quán)。設(shè)P是G的一條路，P上所帶權(quán)的總和稱為路P的權(quán)。有時(shí)記為G=(V，E，W) 71設(shè)權(quán)圖G中每條邊的權(quán)均大于等于0，u,v為G中任意的兩個(gè)頂點(diǎn)，從u到v的所有路中權(quán)最小的路

12、稱為u到v的最短路徑，求給定的兩頂點(diǎn)之間的最短路徑問題稱為最短路徑問題。 最短路徑算法：由E.W.Dijkstra（迪克斯特拉）于1959年給出的標(biāo)號(hào)法（Dijkstra算法）。 三、最短路徑72問題：圖G=(V,E,W),1V,求1到V其它點(diǎn)的最短距離。設(shè)S為最短距離已經(jīng)確定的集合，T為最短距離未確定的集合。算法描述如下：(1) 初始話：S=1，T=V-S。(2) 求1經(jīng)過(guò)S中的點(diǎn)。到T中點(diǎn)的最短距離。記為D(i)。 D(i)=w(1,i)(3) 選T中D(i)值最小的點(diǎn)i，記為k。把k加入S，T=V-S。(4) 對(duì)T中的點(diǎn)i更新D(i)： 若D(k)+W(i,k)D(i)，D(i)= D(

13、k)+W(i,k) (5) T為空集，算法結(jié)束。三、最短路徑73例 用Dijkstra求下圖中a到d的最短路徑。abcdefa62 2f37 93b595ce9d677674四、最短路徑例 求下圖中a到f的最短路徑。A,b,d,c,e,f 68.3 圖的矩陣表示內(nèi)容：鄰接矩陣，關(guān)聯(lián)矩陣，可達(dá)矩陣。重點(diǎn)：1、有向圖的鄰接矩陣。2、有向圖，無(wú)向圖的關(guān)聯(lián)矩陣。了解：有向圖的可達(dá)矩陣。一、有向圖的鄰接矩陣。1、設(shè)有向圖，的鄰接矩陣，其中指鄰接到的邊的條數(shù) (非負(fù)整數(shù))。例1、有向圖(下圖所示)，求。解：2、性質(zhì)。(1)(2)(3)(4)為中環(huán)的個(gè)數(shù)。3. 的元素的意義設(shè) ，則 。 表示：從結(jié)點(diǎn) 和 兩

14、者引出的邊，如果能共同終止于一些結(jié)點(diǎn)，則 就是這些終止結(jié)點(diǎn)的數(shù)目。特別地： 時(shí)，對(duì)角線上的元素 就是結(jié)點(diǎn) 的引出次數(shù)。4. 的元素的意義設(shè) ，則 。 表示：從一些結(jié)點(diǎn)引出的邊，如果能同時(shí)終止于 和 ，則 就是這樣的結(jié)點(diǎn)數(shù)目。特別地： 時(shí)，對(duì)角線上的元素 就是結(jié)點(diǎn) 的引出次數(shù)。5、求中長(zhǎng)度為的通路數(shù)和回路數(shù)。(1) 令矩陣乘法其中表示從到長(zhǎng)度為2的通路數(shù)或回路數(shù)。5、求中長(zhǎng)度為的通路數(shù)和回路數(shù)?？紤]，簡(jiǎn)記為。其中表示從到長(zhǎng)度為或回路數(shù)。的通路數(shù)中長(zhǎng)度為為的通路總數(shù)，其中為中長(zhǎng)度為的回路總數(shù)。5、求中長(zhǎng)度為的通路數(shù)和回路數(shù)。(2) 設(shè)則中元素為中到長(zhǎng)度小于等于的通路總數(shù)，為中長(zhǎng)度小于等于的通路總數(shù)

15、，其中為中長(zhǎng)度小于等于的回路總數(shù)。例4、在例1的有向圖中求，。解：，二、無(wú)向圖的關(guān)聯(lián)矩陣。1、設(shè)無(wú)向圖，的關(guān)聯(lián)矩陣，例2、無(wú)向圖(下圖所示)，求。解：2、性質(zhì)。(1)(2)(3)握手定理（m為邊數(shù)）（每列之和為2表示每條邊只有兩個(gè)頂點(diǎn)）（每行之和表示對(duì)應(yīng)點(diǎn)的度數(shù)）(4)，當(dāng)且僅當(dāng)為孤立點(diǎn)。2、性質(zhì)。(5) 若第列與第列相同，則說(shuō)明與為平行邊。三、有向簡(jiǎn)單圖（無(wú)環(huán)）的關(guān)聯(lián)矩陣。1、設(shè)無(wú)環(huán)有向圖，的關(guān)聯(lián)矩陣，其中例2、有向圖(下圖所示)，求。解：2、性質(zhì)。(1)(2)(3)四、有向圖的可達(dá)性矩陣。(了解)設(shè)為有向圖，令，四、有向圖的可達(dá)性矩陣。(了解)可達(dá)性矩陣其中元素可由求得：8.7 樹一 .

16、無(wú)向樹及生成樹 內(nèi)容：無(wú)向樹，生成樹。重點(diǎn)：1、無(wú)向樹的定義 (包括等價(jià)定義)，2、無(wú)向樹的性質(zhì)，3、生成樹的定義，由連通圖構(gòu)造最小生成樹的方法。本章中所談回路均指簡(jiǎn)單回路或基本回路。一、無(wú)向樹。1、無(wú)向樹連通且不含回路的無(wú)向圖。無(wú)向樹簡(jiǎn)稱樹，常用表示。平凡樹平凡圖（僅有一個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖）。森林 連通分支數(shù)大于等于2，且每個(gè)連通分支都是樹的無(wú)向圖。例1、例1、2、樹的六個(gè)等價(jià)定義。(1)連通且不含回路。(2)的每對(duì)頂點(diǎn)間具有唯一的路徑。(3)連通且。(4)無(wú)回路且。定理：設(shè)，則以下命題等價(jià)。2、樹的六個(gè)等價(jià)定義。(5)無(wú)回路，但在中任兩個(gè)不相鄰的頂點(diǎn)之間增加一條邊，就形成唯一的一條初級(jí)回路。(

17、6)是連通的，但刪除任何一條邊后，就不連通了。3、性質(zhì)。(1) 樹中頂點(diǎn)數(shù)與邊數(shù)的關(guān)系：。(2) 定理：非平凡樹至少2片樹葉。證明：設(shè)為階非平凡樹，設(shè)有片樹葉，則有個(gè)頂點(diǎn)度數(shù)大于等于2，由握手定理，又由(1)，代入上式，解得，即至少2片葉。例2、畫出所有的6個(gè)頂點(diǎn)的非同構(gòu)的樹。解：所要畫的樹有6個(gè)頂點(diǎn)，則邊數(shù)為5，因此6個(gè)頂點(diǎn)的度數(shù)之和為10，可以產(chǎn)生以下五種度數(shù)序列：(1)例2、畫出所有的6個(gè)頂點(diǎn)的非同構(gòu)的樹。解：所要畫的樹有6個(gè)頂點(diǎn)，則邊數(shù)為5，因此6個(gè)頂點(diǎn)的度數(shù)之和為10，可以產(chǎn)生以下五種度數(shù)序列：(2)例2、畫出所有的6個(gè)頂點(diǎn)的非同構(gòu)的樹。解：所要畫的樹有6個(gè)頂點(diǎn)，則邊數(shù)為5，因此6個(gè)

18、頂點(diǎn)的度數(shù)之和為10，可以產(chǎn)生以下五種度數(shù)序列：(3)例2、畫出所有的6個(gè)頂點(diǎn)的非同構(gòu)的樹。解：所要畫的樹有6個(gè)頂點(diǎn)，則邊數(shù)為5，因此6個(gè)頂點(diǎn)的度數(shù)之和為10，可以產(chǎn)生以下五種度數(shù)序列：(4)例2、畫出所有的6個(gè)頂點(diǎn)的非同構(gòu)的樹。解：所要畫的樹有6個(gè)頂點(diǎn)，則邊數(shù)為5，因此6個(gè)頂點(diǎn)的度數(shù)之和為10，可以產(chǎn)生以下五種度數(shù)序列：(5)二、生成樹。1、定義：設(shè)是無(wú)向連通圖，是的生成子圖，若是樹，稱是的生成樹。樹枝弦余樹在中的邊，不在中的邊，的所有的弦的集合的導(dǎo)出子圖。例4、上圖中，(2)是(1)的生成樹，(3)是(2)的余樹。注意：(1) 生成樹不唯一，(2) 余樹不一定是樹。2、連通圖的性質(zhì)。設(shè)為連

19、通圖，(1)至少有一棵生成樹，(2)，(3) 設(shè)是的生成樹，是的余樹，則中有條邊。已知連通圖，求其生成樹步驟。3、最小生成樹。對(duì)于有向圖或無(wú)向圖的每條邊附加一個(gè)實(shí)數(shù)，則稱為邊上的權(quán)，連同附加在各邊上的實(shí)數(shù)稱為帶權(quán)圖，記為。最小生成樹各邊權(quán)和最小的生成樹。定義：設(shè)無(wú)向連通帶權(quán)圖，是的一棵生成樹，各邊帶權(quán)之和稱為的權(quán)，記作。求最小生成樹的方法（克魯斯克爾)避圈法。設(shè)階無(wú)向連通帶權(quán)圖中有條邊，它們帶的權(quán)分別為，不妨設(shè)，(1) 取在中 (非環(huán)，若為環(huán)，則棄)。(2) 若不與構(gòu)成回路，取在中，否則棄，再查，繼續(xù)這一過(guò)程，直到形成樹為止。解：例5、求以下連通圖的最小生成樹及。解：例5、求以下連通圖的最小生

20、成樹及。解：例6、求以下連通圖的最小生成樹及。解：例6、求以下連通圖的最小生成樹及。注意：的最小生成樹可能不唯一，但的不同最小生成樹權(quán)的值一樣。第八章 小結(jié)與例題一、無(wú)向圖與有向圖。1、基本概念。有向圖與無(wú)向圖的定義；關(guān)聯(lián)與鄰接(相鄰)；頂點(diǎn)的度數(shù)；零圖與平凡圖；簡(jiǎn)單圖與多重圖；完全圖；子圖，補(bǔ)圖；圖的同構(gòu)。一、無(wú)向圖與有向圖。2、運(yùn)用。(1) 靈活運(yùn)用握手定理及其推論，(2) 判斷兩個(gè)圖是否同構(gòu)，(3) 畫出滿足某些條件的子圖，補(bǔ)圖等。二、通路，回路，圖的連通性。1、基本概念。通路和回路；無(wú)向圖和有向圖中頂點(diǎn)之間的可達(dá)關(guān)系；短程線，距離；有向圖連通的分類。二、通路，回路，圖的連通性。2、運(yùn)用

21、。(1) 判斷有向圖或無(wú)向圖中通路(回路)的類型。(2) 求短程線和距離。(3) 判斷有向圖連通的類型。三、歐拉圖。1、基本概念。歐拉通路，歐拉回路，歐拉圖。2、運(yùn)用。判定無(wú)向圖是否具有歐拉通路或回路。四、哈密爾頓圖。1、基本概念。哈密爾頓通路，哈密爾頓回路，哈密爾頓圖。2、運(yùn)用。判斷無(wú)向圖是否具有哈密爾頓通路或回路。五、圖的矩陣表示。1、基本概念。無(wú)向圖的關(guān)聯(lián)矩陣，有向圖的關(guān)聯(lián)矩陣和鄰接矩陣。2、運(yùn)用。(1) 關(guān)聯(lián)矩陣的行和、頂點(diǎn)度數(shù)間的關(guān)系。(2) 由有向圖的鄰接矩陣的次冪求從一頂點(diǎn)到另一頂點(diǎn)的長(zhǎng)度為的通路數(shù)。六、無(wú)向樹及生成樹。1、基本概念。無(wú)向樹；樹葉，分支點(diǎn)；森林；平凡樹；生成樹，最

22、小生成樹。2、運(yùn)用。(3) 根據(jù)握手定理及樹的某些性質(zhì)，求頂點(diǎn)數(shù)或某些頂點(diǎn)的度數(shù)。(4) 求生成樹，最小生成樹。七、應(yīng)用1、賦權(quán)圖的最短路徑迪克斯特拉算法2、最小生成樹克魯斯克爾算法例1、設(shè)圖，其中，分別由下面給出。判斷哪些是簡(jiǎn)單圖，哪些是多重圖？(1)(2)(3)簡(jiǎn)單圖多重圖不是例1、設(shè)圖，其中，分別由下面給出。判斷哪些是簡(jiǎn)單圖，哪些是多重圖？(4)(5)(6)簡(jiǎn)單圖多重圖不是例2、下列各序列中，可以構(gòu)成無(wú)向簡(jiǎn)單圖的度數(shù)序列的有哪些？(1)可以(2)不可以(3)可以(4)不可以(5)不可以例3、右圖所示的無(wú)向圖中，分別求：不同的基本通路(路徑)。(1)之間所有解：有7條，分別為，和，。(2)之間的短程線。(3)。解：。解：。例4、下圖所示的六個(gè)圖中，強(qiáng)連通，單向連通，弱連通的分別有哪些？強(qiáng)連通單向連通弱連通例4、下圖所示的六個(gè)圖中