圖論GraphTheory教學(xué).ppt

1,第五章 圖 論 (Graph Theory),2,Konigsberg(柯尼斯堡)七橋問(wèn)題,能否從河岸或小島出發(fā)，恰好通過(guò)每一座橋一次再回到出發(fā)地?,圖論的起源,3,瑞士數(shù)學(xué)家Euler(歐拉)于1736年從理論上圓滿解決這個(gè)問(wèn)題。,歐拉引進(jìn)了圖論,A,D,B,C,抽象,4,1736年 歐拉解決柯尼斯堡七橋問(wèn)題圖論產(chǎn)生 1936 年圖論第一部專著出現(xiàn)有界圖和無(wú)界圖的理論 經(jīng)過(guò)近六十多年的發(fā)展，逐漸成為一門(mén)相對(duì)獨(dú)立的學(xué)科。,圖論發(fā)展過(guò)程,5,圖論的應(yīng)用,網(wǎng)絡(luò)技術(shù)的理論基礎(chǔ)和重要的研究工具 生物和化學(xué)：區(qū)別分子式相同但結(jié)構(gòu)不同的兩種化合物。 計(jì)算機(jī)和通信：用于通信網(wǎng)絡(luò)和計(jì)算機(jī)網(wǎng)絡(luò)的設(shè)計(jì)，交通網(wǎng)絡(luò)的合理分布 大型工程項(xiàng)目的計(jì)劃管理。,6,圖的基本概念 1,圖（graph）：由結(jié)點(diǎn)（頂點(diǎn)）(vertex)和連接結(jié)點(diǎn)的邊所構(gòu)成的圖形. V(G)表示圖G的結(jié)點(diǎn)集 E(G)表示圖G的邊集。 圖G可記為或 有n個(gè)頂點(diǎn)和m條邊的圖記為(n,m)圖或稱為n階圖。,7,注意：圖論中研究的圖只關(guān)心圖的結(jié)點(diǎn)之間是否有邊相連，不關(guān)心結(jié)點(diǎn)的位置和邊的長(zhǎng)短,8,圖的基本概念 2(1),邊(edge) 有向邊(directed edge) 無(wú)向邊(indirected edge) 平行邊(parallel edge ) 自回路（環(huán)）(Self-loop / Ring),9,圖的基本概念 2(2),邊(edge) 有向邊(directed edge) 端點(diǎn)有始點(diǎn)和終點(diǎn)之分的邊。 用有序二元組表示 無(wú)向邊(indirected edge) 邊的兩個(gè)端點(diǎn)都可以作始點(diǎn)和終點(diǎn)的邊 端點(diǎn)為v1和v2的無(wú)向邊表示為 (v1, v2) 或v1v2,10,圖的基本概念 2(2),邊(edge) 平行邊(parallel edge ) 兩結(jié)點(diǎn)之間的多條無(wú)向邊或 多條方向相同的有向邊稱為平行邊。 兩個(gè)端點(diǎn)a和b之間平行邊的條數(shù) 稱為邊(a,b)（或）的重?cái)?shù) 自回路（環(huán)）(Self-loop / Ring) 兩個(gè)端點(diǎn)重合的無(wú)向（有向）邊。,v1,a,b,11,圖的基本概念 3,邊與結(jié)點(diǎn)的關(guān)系 設(shè)邊e的端點(diǎn)為a和b 邊e關(guān)聯(lián)(incident)于頂點(diǎn)a和b（或a和b關(guān)聯(lián)邊e） a、b是鄰接（相鄰）的(adjacent),12,根據(jù)圖中邊的類型可將圖分為： 無(wú)向圖(undirected graph) 有向圖(directed graph) 混合圖(mixed graph) 多重圖(multiple graph) 簡(jiǎn)單圖(simple graph),圖的基本類型（1）,13,圖的基本類型（2）,無(wú)向圖(undirected graph)：所有邊都是無(wú)向邊的圖。 有向圖(directed graph)：所有邊都是有向邊的圖。 混合圖：既有有向邊又有無(wú)向邊的圖。,(c),14,圖的基本分類（2）,多重圖(multiple graph)：含平行邊的圖 簡(jiǎn)單圖(simple graph)：無(wú)環(huán)和平行邊的圖,a,b,c,15,圖的基本分類（3）,有限圖(finite graph)：頂點(diǎn)個(gè)數(shù)有限的圖 無(wú)限圖(infinite graph)：頂點(diǎn)個(gè)數(shù)無(wú)限的圖,根據(jù)圖中結(jié)點(diǎn)的數(shù)目可分為：,16,回顧,所有邊都有方向,所有邊都無(wú)方向,既有有向邊又有無(wú)向邊,有平行邊,無(wú)平行邊和環(huán),結(jié)點(diǎn)數(shù)有限,結(jié)點(diǎn)數(shù)無(wú)限,17,練習(xí)題,判斷下面給出的兩個(gè)圖的類型。,無(wú)向圖,有向圖 簡(jiǎn)單圖,有向圖 無(wú)向圖 混合圖 多重圖 簡(jiǎn)單圖,18,底圖 定向圖 逆圖,圖的基本分類（4）,19,圖的基本類型（5）,底圖：將有向圖G的所有有向邊換成無(wú)向邊，得到的無(wú)向圖稱為G的底圖。,20,圖的基本類型（6）,定向圖：將無(wú)向圖G中每條無(wú)向邊指定一個(gè)方向所得到的圖稱為G的定向圖。,21,圖的基本分類（7）,逆圖 將有向圖G的每一條邊的方向顛倒所得到的圖稱為G的逆圖，記為 。,a,b,c,a,b,c,逆圖,22,結(jié)點(diǎn)的度（1）,結(jié)點(diǎn)v的度: 指結(jié)點(diǎn)v關(guān)聯(lián)的邊數(shù)， 記為deg(v)或d(v)。 注意：每個(gè)環(huán)看作兩條邊,d(b)=2,d(a)=4,d(c)=4,d(d)=2,23,結(jié)點(diǎn)的度（2）,有向圖中，度可分為：出度(out-degree)和入度 (in-degree) 結(jié)點(diǎn)v的出度: 以v為起點(diǎn)的有向邊的數(shù)目 記為deg+(v) 或d+(v) 結(jié)點(diǎn)v的入度: 以v為終點(diǎn)的有向邊的數(shù)目， 記為deg-(v)或d-(v) 有向圖中結(jié)點(diǎn)v的度d(v)：d(v)=d+(v)+d-(v),a,b,c,deg+(c) = 2 deg-(c) = 3 deg(c) = deg+(c) + deg-(c) = 5,24,定理 1,設(shè)圖G是具有n個(gè)頂點(diǎn)、m條邊的有向圖，V(G)=v1,v2,vn，則,25,定理 2 （Hankshaking）,設(shè)圖G是具有n個(gè)頂點(diǎn)、m條邊，V(G)=v1,v2,vn，則,推論：度數(shù)為奇數(shù)的頂點(diǎn)個(gè)數(shù)必為偶數(shù)。,26,常用的簡(jiǎn)單圖,賦權(quán)圖 無(wú)向完全圖 有向完全圖 競(jìng)賽圖 正則圖,27,賦權(quán)圖,賦權(quán)圖是頂點(diǎn)或邊附加了信息的圖。 頂點(diǎn)或邊中附加的信息稱為權(quán)。,28,賦權(quán)圖例,A,F,B,C,D,E,29,普通圖和賦權(quán)圖,比較 對(duì)普通圖，主要研究結(jié)點(diǎn)和邊之間的拓?fù)潢P(guān)系 度，連通，通路等性質(zhì) 賦權(quán)圖給普通圖附加了數(shù)量關(guān)系 距離，成本，代價(jià)，規(guī)模等性質(zhì),30,無(wú)向完全圖,任意兩個(gè)不同的頂點(diǎn)間都有一條邊關(guān)聯(lián)的無(wú)向簡(jiǎn)單圖稱為無(wú)向完全圖 n階無(wú)向完全圖記為：Kn,K1,K2,K3,K4,K5,31,有向完全圖,任意兩個(gè)不同的頂點(diǎn)之間都有兩條方向相反的有向邊相連并且每一個(gè)頂點(diǎn)都有一條自回路的有向圖 稱為有向完全圖,32,完全圖邊數(shù),n階無(wú)向完全圖的邊數(shù)是多少？ n(n-1)/2 n階有向完全圖的邊數(shù)是多少？ n2,33,競(jìng)賽圖（tournament）,若有向圖的底圖是無(wú)向完全圖，稱此有向圖為競(jìng)賽圖。,34,競(jìng)賽圖名稱的由來(lái),由于循環(huán)賽中任意兩名選手都要進(jìn)行比賽，而且任何一場(chǎng)比賽都分勝負(fù)。 用每個(gè)頂點(diǎn)代表一名選手，如果選手a戰(zhàn)勝了b，那么連一條從a 指向b 的有向邊，這樣得到的圖稱之為競(jìng)賽圖,35,競(jìng)賽圖的性質(zhì),設(shè)圖G是n階競(jìng)賽圖，V(G)=v1,v2,vn，則,由G是競(jìng)賽圖可知：,證明：等價(jià)于證明,而由有向圖頂點(diǎn)度數(shù)和定理可知：,36,競(jìng)賽圖的性質(zhì)證明（續(xù)）,37,正則圖(regular graph),所有頂點(diǎn)的度均相同的簡(jiǎn)單圖稱為正則圖。若頂點(diǎn)的度數(shù)k，則稱作k-正則圖,2-正則圖,3-正則圖,38,圖的操作,刪邊 刪去圖G中的若干條邊，但仍保留被刪除邊的端點(diǎn) 刪點(diǎn) 刪去圖G中的若干個(gè)頂點(diǎn)以及與被刪點(diǎn)所關(guān)聯(lián)的所有邊,39,圖的操作-刪邊,刪e1,40,圖的操作-刪點(diǎn),刪v1,41,子圖,從圖G中刪除若干條邊或頂點(diǎn)所得到的圖稱為G的子圖。,G,G1,G2,42,主子圖 生成子圖 邊集的導(dǎo)出子圖 點(diǎn)集的導(dǎo)出子圖,子圖的類型,43,主子圖,在圖G中刪去一個(gè)頂點(diǎn)后所得的子圖稱為圖G的主子圖,44,生成子圖,若G 是G的子圖，且G含有G的所有頂點(diǎn)，則稱G是G的生成子圖,45,邊集的導(dǎo)出子圖,設(shè)E是E(G)的非空子集，則以E為邊集，以E中邊的端點(diǎn)全體為頂點(diǎn)集所構(gòu)成的圖稱為G的由邊集E導(dǎo)出的子圖。 記為GE。,46,邊集的導(dǎo)出子圖示例,邊集 E=(a,b),(b,e),(a,e),(a,c) 的導(dǎo)出子圖,G,GE,47,點(diǎn)集的導(dǎo)出子圖,設(shè)V是V(G)的非空子集，則以V為頂點(diǎn)集，以G中兩端點(diǎn)均在V中的邊的全體為邊集，所構(gòu)成的子圖稱為G的由V導(dǎo)出的子圖。 記為GV,48,點(diǎn)集的導(dǎo)出的子圖示例,點(diǎn)集V=a,b,c,e導(dǎo)出的子圖,G,GV,49,回顧,原圖刪除一個(gè)頂點(diǎn),包含原圖所有頂點(diǎn),由邊集E及E關(guān)聯(lián)的頂點(diǎn)構(gòu)成,由頂點(diǎn)集V以及端點(diǎn)都在V中的邊構(gòu)成,50,練習(xí)(1),請(qǐng)判斷下列哪些圖是圖G的生成子圖：,A,B,C,D,G,回答：C和D,51,練習(xí)(2),請(qǐng)判斷下列哪個(gè)圖是圖G的由邊集Ee1,e2,e6,e7的導(dǎo)出子圖：,A,B,C,D,G,回答：C,e1,e2,e3,e4,e5,e6,e7,e8,52,補(bǔ)圖,設(shè)G是n階無(wú)向簡(jiǎn)單圖 在G中添加一些邊后，可使G成為n階無(wú)向完全圖 由這些添加邊和G的所有頂點(diǎn)構(gòu)成的圖稱為G的補(bǔ)圖 記作 G G=G,53,補(bǔ)圖示例,v5,v1,v2,v3,v4,G,54,圖的同構(gòu)（isomorphism）,設(shè)圖G=(V,E)和圖G=(V,E) ， 如果存在著從V到V的雙射映射f，使對(duì)任意的u,vV， (u,v)E（或E） ，當(dāng)且僅當(dāng) (f(u),f(v)E（或E ）， 則稱圖G和G同構(gòu) 記為GG f稱為G和G的同構(gòu)映射 實(shí)質(zhì)：如果兩個(gè)圖的點(diǎn)能建立一一對(duì)應(yīng)關(guān)系，并且點(diǎn)和點(diǎn)的鄰接也能保持一一對(duì)應(yīng)關(guān)系，則這兩個(gè)圖是同構(gòu)的。 同構(gòu)的圖被看作同一個(gè)圖.,55,圖同構(gòu)示例 1,b,a,c,d,G,G,G,56,圖同構(gòu)舉示例2,57,圖同構(gòu)示例3,G1,G1G2,G1G3？,58,自補(bǔ)圖,如果G和它的補(bǔ)圖 同構(gòu)，稱G為自補(bǔ)圖,G,a,b,c,d,e,a,b,c,d,e,59,5.1.2 圖的表示,1、鄰接矩陣 (adjacent matrix) 2、關(guān)聯(lián)矩陣（incident matrix）,60,1、鄰接矩陣,設(shè)G(V,E)是n階圖，設(shè)Vv1，vn。G的鄰接矩陣A(G)bij是nn階的矩陣，其中，,v1 v2 vj vn,bij=邊(vi,vj)（或邊）的重?cái)?shù),61,無(wú)向圖鄰接矩陣舉例和性質(zhì),關(guān)于主對(duì)角線對(duì)稱:aij=aji 無(wú)向簡(jiǎn)單圖的鄰接矩陣每行(列)和為行(列)表頭頂點(diǎn)的度數(shù),G,62,有向圖鄰接矩陣舉例與性質(zhì),每行和為出度: nj=1aij=d+(vi) 每列和為入度: ni=1aij=d-(vj),G,63,2.1 無(wú)向圖的關(guān)聯(lián)矩陣,設(shè)G(V,E)是有n個(gè)結(jié)點(diǎn)和m條邊的無(wú)向圖， V(G)v1，vn，E(G)e1，em。 G的關(guān)聯(lián)矩陣M(G)aij是nm階矩陣，其中,e1 e2 ej em,64,無(wú)向圖的關(guān)聯(lián)矩陣舉例,G,65,無(wú)向圖的關(guān)聯(lián)矩陣性質(zhì),每列和為2 每行和為d(vi),66,2.2 有向圖的關(guān)聯(lián)矩陣,設(shè)G(V,E)是有n個(gè)結(jié)點(diǎn)和m條邊的有向無(wú)環(huán)圖，V(G)v1，vn，E(G)e1，em。 G的關(guān)聯(lián)矩陣M(G)aij是nm階矩陣，其中,67,有向圖關(guān)聯(lián)矩陣舉例和性質(zhì),每列和為零 每行各元素絕對(duì)值的和為該行表頭頂點(diǎn)的度數(shù),G,68,同構(gòu)判定算法,同構(gòu)判定算法（用鄰接矩陣） 1、確定兩個(gè)圖的鄰接矩陣I和II 2、計(jì)算行度（對(duì)應(yīng)于出度）和列度（對(duì)應(yīng)于入度） ： 行度/列度：矩陣每行/列中的個(gè)數(shù)， 3、若兩個(gè)矩陣的行度集合與列度集合不同，則必不同構(gòu)，否則繼續(xù)。 4、同時(shí)交換其中一個(gè)矩陣的第行和第行，第列和第列。若此矩陣能變成與另一矩陣相同，則同構(gòu)。 5、對(duì)所有的行列變換都試驗(yàn)完畢，仍不相同，則不同構(gòu)。,69,同構(gòu)判定算法舉例,例：A(G1)的行度集合 ， 列度集合 ， A(G2)的行度集合 1， 列度集合 ，,A(G1),A(G2),70,同構(gòu)判定算法舉例(續(xù)1),將矩陣A(G1)的第行與第行交換、第列與第列交換，得:,A(G1),A(G2),71,同構(gòu)判定算法舉例(續(xù)2),再把矩陣A(G1)的第行與第行交換，第列與第列交換，得 :,=,A(G1),A(G2),72,同