資源描述：
《離散數(shù)學PPT教學圖論》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、歡迎進入第11章圖論本章重難點:重點了解圖的各種概念，理解并掌握握手定理的應用以及各種矩陣的表示。難點是圖的最短路徑和關鍵路徑的求法。第11章圖論第一節(jié)圖的基本概念第二節(jié)圖的矩陣表示第三節(jié)生成樹、最短路徑和關鍵路徑第四節(jié)特殊圖（歐拉圖和哈密頓圖等）第五節(jié)樹、二叉樹和哈夫曼樹一、圖的基本概念圖的定義：圖（graph）G由三個部分所組成：（1）非空集合V(G)稱為圖G的結(jié)點集，其成員稱為節(jié)點或頂點（nodesorvertices）（2）集合E(G)，稱為圖G的邊集，其成員稱為邊(edges)。（3）函數(shù)ΨG：E(G)→(V(G)，V(G))，稱為邊與
2、頂點的關聯(lián)映射。度的相關定義：在任何圖中，結(jié)點v的度（degree）d(v)是v所關聯(lián)邊的數(shù)目。而在有向圖中，結(jié)點v的出度（out-degree）d+(v)是v作為有向邊起點的數(shù)目，v的入度（in-degree）d-(v)是v作為有向邊終點的數(shù)目，這時結(jié)點v的度是它的出度與入度的和；結(jié)點v的環(huán)使其度增加2。一、圖的基本概念連通圖、強連通圖、弱連通圖若無向圖中的任意兩個頂點都相互可達，則稱無向圖G是連通的（connected）；若有向圖G的任何兩個頂點都是相互可達的，則稱有向圖G是強連通的；如果G的任何兩個頂點都是相互可達的，稱有向圖G是單向連通的
3、；如果G的任何兩個頂點中，至少從一個頂點到另一個頂點是可達的，稱有向圖G是弱連通的。一、圖的基本概念鄰接和關聯(lián)無向圖和有向圖零圖和平凡圖簡單圖完全圖（無向完全圖和有向完全圖）有環(huán)圖一、圖的基本概念有限圖和無限圖設圖G為（l）當V和E為有限集時，稱G為有限圖，否則稱G為無限圖。（2）當ΨG為單射時，稱G為單圖；當ΨG為非單射時，稱G為重圖，又稱滿足Ψ(e1)=Ψ(e2)的不同邊e1，e2，為重邊,或平行邊。正則圖各頂點的度均相同的圖稱為正則圖（regulargraph）。各頂點度均為k的正則圖稱為k-正則圖。同構(gòu)圖一、圖的基本概念子圖
4、、真子圖、生成子圖設圖G1＝，G2＝，稱G1為G2的子圖（subgraph）；如果V1?V2，E1?E2，Ψ1?Ψ2，稱G1為G2的真子圖；如果G1是G2的子圖，且G1?G2，稱G1為G2的生成子圖（spanningsubgraph）；如果G1是G2的子圖，且V1=V2。握手定理的證明每個圖中，節(jié)點度數(shù)的總和等于邊的2倍。證明：因為每條邊必關聯(lián)兩個節(jié)點，而一條邊給予關聯(lián)的每個節(jié)點的度數(shù)為1，因此在一個圖中，節(jié)點度數(shù)的總和等于邊數(shù)的2倍。握手定理的運用定理1：在任何圖中，度數(shù)為奇數(shù)的節(jié)點個數(shù)必定是偶數(shù)個。證明
5、：（自己思考！）定理2：在任何有向圖中，所有節(jié)點入度之和等于所有節(jié)點的出度之和。證明：因為每一條有向邊必對應一個入度及一個出度，所以有向圖中各節(jié)點入度之和等于邊數(shù)，各節(jié)點的出度之和也等于邊數(shù)。例：設圖G為下列情況：(1)16條邊，每個頂點都是2度；(2)21條邊，3個4度頂點，其余均為３度頂點；(3)24條邊，各節(jié)點的度數(shù)均相同；試求每個圖有幾個節(jié)點？握手定理的應用解答：利用握手定理，設圖Ｇ有x個節(jié)點，則２x=16*2x=1621*2=12+3*xx=10故圖中有１３個節(jié)點．(3)x*m=24*2二、圖的矩陣表示關聯(lián)矩陣2.鄰接矩陣3.可達矩陣4
6、.布爾矩陣5.代價矩陣二、圖的矩陣表示關聯(lián)矩陣無向圖的關聯(lián)矩陣-----以節(jié)點數(shù)為行,邊數(shù)為列.若有環(huán),則關聯(lián)數(shù)為2,無關聯(lián)則為0.每行之和為該頂點的度,列之和一定為2.有向圖的關聯(lián)矩陣-----以節(jié)點數(shù)為行,邊數(shù)為列.節(jié)點與邊無關系,為0,有關系,則起點為1,終點為-1;列之和一定為0,每行絕對值之和等于該節(jié)點的度數(shù);其中1的個數(shù)為該節(jié)點的出度,-1的個數(shù)為對應節(jié)點的入度;所有元素的和為0,1的個數(shù)等于-1的個數(shù),都等于邊數(shù)m.二、圖的矩陣表示2.鄰接矩陣無向圖的鄰接矩陣-----行和列均為節(jié)點的數(shù)目;是個對稱距陣,行之和等于列之和,均等于該頂
7、點的度;主對角線都為0,除非有環(huán)才為1;邊的數(shù)目m為1的數(shù)目總和的一半.有向圖的鄰接矩陣-----行和列均為節(jié)點的數(shù)目;不是對稱距陣,行之和等于該頂點的出度,列之和等于該頂點的入度;主對角線都為0,除非有環(huán)才為1;邊的數(shù)目m為非0的數(shù)目的總和.二、圖的矩陣表示可達矩陣---行和列均為節(jié)點的數(shù)目;節(jié)點和節(jié)點之間若至少存在一條路則為1,不存在路則為0.4.布爾矩陣---由可達距陣轉(zhuǎn)變,把非0的數(shù)值均改為1即可.代價矩陣---若鄰接距陣元素為1的以權(quán)值表示,距陣元素為0的則以∞表示.三、生成樹、最短路徑和關鍵路徑生成樹定義1、深度優(yōu)先遍歷2、廣度優(yōu)先遍
8、歷最小生成樹構(gòu)造最小生成樹的三種方法：1、Kruskal算法2、管梅谷算法3、Prim算法第四節(jié)歐拉圖和哈密頓圖歐拉圖的由來：哥尼斯堡七
