離散數(shù)學(xué)PPT教學(xué)圖論.ppt

《離散數(shù)學(xué)PPT教學(xué)圖論.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、歡迎進(jìn)入第11章圖論本章重難點(diǎn):重點(diǎn)了解圖的各種概念，理解并掌握握手定理的應(yīng)用以及各種矩陣的表示。難點(diǎn)是圖的最短路徑和關(guān)鍵路徑的求法。第11章圖論第一節(jié)圖的基本概念第二節(jié)圖的矩陣表示第三節(jié)生成樹(shù)、最短路徑和關(guān)鍵路徑第四節(jié)特殊圖（歐拉圖和哈密頓圖等）第五節(jié)樹(shù)、二叉樹(shù)和哈夫曼樹(shù)一、圖的基本概念圖的定義：圖（graph）G由三個(gè)部分所組成：（1）非空集合V(G)稱(chēng)為圖G的結(jié)點(diǎn)集，其成員稱(chēng)為節(jié)點(diǎn)或頂點(diǎn)（nodesorvertices）（2）集合E(G)，稱(chēng)為圖G的邊集，其成員稱(chēng)為邊(edges)。（3）函數(shù)ΨG：E(G)→(V(G)，V(G))，

2、稱(chēng)為邊與頂點(diǎn)的關(guān)聯(lián)映射。度的相關(guān)定義：在任何圖中，結(jié)點(diǎn)v的度（degree）d(v)是v所關(guān)聯(lián)邊的數(shù)目。而在有向圖中，結(jié)點(diǎn)v的出度（out-degree）d+(v)是v作為有向邊起點(diǎn)的數(shù)目，v的入度（in-degree）d-(v)是v作為有向邊終點(diǎn)的數(shù)目，這時(shí)結(jié)點(diǎn)v的度是它的出度與入度的和；結(jié)點(diǎn)v的環(huán)使其度增加2。一、圖的基本概念連通圖、強(qiáng)連通圖、弱連通圖若無(wú)向圖中的任意兩個(gè)頂點(diǎn)都相互可達(dá)，則稱(chēng)無(wú)向圖G是連通的（connected）；若有向圖G的任何兩個(gè)頂點(diǎn)都是相互可達(dá)的，則稱(chēng)有向圖G是強(qiáng)連通的；如果G的任何兩個(gè)頂點(diǎn)都是相互可達(dá)的，稱(chēng)有向

3、圖G是單向連通的；如果G的任何兩個(gè)頂點(diǎn)中，至少?gòu)囊粋€(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)是可達(dá)的，稱(chēng)有向圖G是弱連通的。一、圖的基本概念鄰接和關(guān)聯(lián)無(wú)向圖和有向圖零圖和平凡圖簡(jiǎn)單圖完全圖（無(wú)向完全圖和有向完全圖）有環(huán)圖一、圖的基本概念有限圖和無(wú)限圖設(shè)圖G為（l）當(dāng)V和E為有限集時(shí)，稱(chēng)G為有限圖，否則稱(chēng)G為無(wú)限圖。（2）當(dāng)ΨG為單射時(shí)，稱(chēng)G為單圖；當(dāng)ΨG為非單射時(shí)，稱(chēng)G為重圖，又稱(chēng)滿(mǎn)足Ψ(e1)=Ψ(e2)的不同邊e1，e2，為重邊,或平行邊。正則圖各頂點(diǎn)的度均相同的圖稱(chēng)為正則圖（regulargraph）。各頂點(diǎn)度均為k的正則圖稱(chēng)為k-正則圖。同

4、構(gòu)圖一、圖的基本概念子圖、真子圖、生成子圖設(shè)圖G1＝，G2＝，稱(chēng)G1為G2的子圖（subgraph）；如果V1?V2，E1?E2，Ψ1?Ψ2，稱(chēng)G1為G2的真子圖；如果G1是G2的子圖，且G1?G2，稱(chēng)G1為G2的生成子圖（spanningsubgraph）；如果G1是G2的子圖，且V1=V2。握手定理的證明每個(gè)圖中，節(jié)點(diǎn)度數(shù)的總和等于邊的2倍。證明：因?yàn)槊織l邊必關(guān)聯(lián)兩個(gè)節(jié)點(diǎn)，而一條邊給予關(guān)聯(lián)的每個(gè)節(jié)點(diǎn)的度數(shù)為1，因此在一個(gè)圖中，節(jié)點(diǎn)度數(shù)的總和等于邊數(shù)的2倍。握手定理的運(yùn)用定理1：在任何圖中，度數(shù)為

5、奇數(shù)的節(jié)點(diǎn)個(gè)數(shù)必定是偶數(shù)個(gè)。證明：（自己思考！）定理2：在任何有向圖中，所有節(jié)點(diǎn)入度之和等于所有節(jié)點(diǎn)的出度之和。證明：因?yàn)槊恳粭l有向邊必對(duì)應(yīng)一個(gè)入度及一個(gè)出度，所以有向圖中各節(jié)點(diǎn)入度之和等于邊數(shù)，各節(jié)點(diǎn)的出度之和也等于邊數(shù)。例：設(shè)圖G為下列情況：(1)16條邊，每個(gè)頂點(diǎn)都是2度；(2)21條邊，3個(gè)4度頂點(diǎn)，其余均為３度頂點(diǎn)；(3)24條邊，各節(jié)點(diǎn)的度數(shù)均相同；試求每個(gè)圖有幾個(gè)節(jié)點(diǎn)？握手定理的應(yīng)用解答：利用握手定理，設(shè)圖Ｇ有x個(gè)節(jié)點(diǎn)，則２x=16*2x=1621*2=12+3*xx=10故圖中有１３個(gè)節(jié)點(diǎn)．(3)x*m=24*2二、圖的矩

6、陣表示關(guān)聯(lián)矩陣2.鄰接矩陣3.可達(dá)矩陣4.布爾矩陣5.代價(jià)矩陣二、圖的矩陣表示關(guān)聯(lián)矩陣無(wú)向圖的關(guān)聯(lián)矩陣-----以節(jié)點(diǎn)數(shù)為行,邊數(shù)為列.若有環(huán),則關(guān)聯(lián)數(shù)為2,無(wú)關(guān)聯(lián)則為0.每行之和為該頂點(diǎn)的度,列之和一定為2.有向圖的關(guān)聯(lián)矩陣-----以節(jié)點(diǎn)數(shù)為行,邊數(shù)為列.節(jié)點(diǎn)與邊無(wú)關(guān)系,為0,有關(guān)系,則起點(diǎn)為1,終點(diǎn)為-1;列之和一定為0,每行絕對(duì)值之和等于該節(jié)點(diǎn)的度數(shù);其中1的個(gè)數(shù)為該節(jié)點(diǎn)的出度,-1的個(gè)數(shù)為對(duì)應(yīng)節(jié)點(diǎn)的入度;所有元素的和為0,1的個(gè)數(shù)等于-1的個(gè)數(shù),都等于邊數(shù)m.二、圖的矩陣表示2.鄰接矩陣無(wú)向圖的鄰接矩陣-----行和列均為節(jié)點(diǎn)的

7、數(shù)目;是個(gè)對(duì)稱(chēng)距陣,行之和等于列之和,均等于該頂點(diǎn)的度;主對(duì)角線都為0,除非有環(huán)才為1;邊的數(shù)目m為1的數(shù)目總和的一半.有向圖的鄰接矩陣-----行和列均為節(jié)點(diǎn)的數(shù)目;不是對(duì)稱(chēng)距陣,行之和等于該頂點(diǎn)的出度,列之和等于該頂點(diǎn)的入度;主對(duì)角線都為0,除非有環(huán)才為1;邊的數(shù)目m為非0的數(shù)目的總和.二、圖的矩陣表示可達(dá)矩陣---行和列均為節(jié)點(diǎn)的數(shù)目;節(jié)點(diǎn)和節(jié)點(diǎn)之間若至少存在一條路則為1,不存在路則為0.4.布爾矩陣---由可達(dá)距陣轉(zhuǎn)變,把非0的數(shù)值均改為1即可.代價(jià)矩陣---若鄰接距陣元素為1的以權(quán)值表示,距陣元素為0的則以∞表示.三、生成樹(shù)、最

8、短路徑和關(guān)鍵路徑生成樹(shù)定義1、深度優(yōu)先遍歷2、廣度優(yōu)先遍歷最小生成樹(shù)構(gòu)造最小生成樹(shù)的三種方法：1、Kruskal算法2、管梅谷算法3、Prim算法第四節(jié)歐拉圖和哈密頓圖歐拉圖的由來(lái)：哥尼斯堡七