圖論-圖的基本概念.ppt

1、圖論圖的基本概念,教師：孫繼榮 電話：87768609 Email:,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,教學(xué)要求 理解圖的概念：結(jié)點(diǎn)、邊、有向圖，無(wú)向圖、圖的同構(gòu)、簡(jiǎn)單圖、完全圖、結(jié)點(diǎn)的度數(shù)、子圖、邊的重?cái)?shù)和平行邊等 理解握手定理 了解通路與回路概念：通路(簡(jiǎn)單通路、初級(jí)通路和復(fù)雜通路)，回路(簡(jiǎn)單回路、初級(jí)回路和復(fù)雜回路) ，會(huì)求通路和回路的長(zhǎng)度 了解無(wú)向圖的連通性，會(huì)求無(wú)向圖的連通分支。了解點(diǎn)割集、割點(diǎn)、邊割集、割邊、點(diǎn)連通度、邊連通度等概念 了解有向圖的強(qiáng)連通強(qiáng)性；會(huì)判別其類型 了解(有向圖、無(wú)向圖)關(guān)聯(lián)矩陣、(無(wú)向圖)相鄰矩陣和(有向圖)鄰接矩陣的概念，掌握構(gòu)造方法及其應(yīng)用。 知

2、道帶權(quán)圖、最短通路概念，知道關(guān)鍵路徑概念,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,學(xué)習(xí)內(nèi)容： 圖的概念 （圖的表示，有向圖、無(wú)向圖、度、同構(gòu)） 圖的矩陣表示 （鄰接矩陣，關(guān)聯(lián)矩陣）,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,本章重點(diǎn) 圖的概念 握手定理 通路 回路 圖的矩陣表示.,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,圖的基本概念 圖是指某些具體的事物以及這些事物之間的聯(lián)系 圖是一個(gè)有序?qū)Γ琕是結(jié)點(diǎn)集，E是邊集，當(dāng)V,E有限時(shí)，稱為有限圖；否則稱無(wú)限圖. 無(wú)向邊, 與無(wú)序結(jié)點(diǎn)(v,u)相關(guān)聯(lián)的邊 有向邊，與有序結(jié)點(diǎn)相關(guān)聯(lián)的邊. 無(wú)向圖，每條邊都是無(wú)向邊的圖，記作G; 每條邊都是有向邊的圖，記作

3、D. 混合圖，既有有向邊，也有無(wú)向邊的圖.,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,圖的基本概念 平凡圖，僅有一個(gè)結(jié)點(diǎn)的圖； 零圖（空?qǐng)D）：邊集為空集的圖，即僅有結(jié)點(diǎn)的圖. 自回路(環(huán))，關(guān)聯(lián)于同一個(gè)結(jié)點(diǎn)的邊. 無(wú)向平行邊，聯(lián)結(jié)相同兩個(gè)結(jié)點(diǎn)的多于1條的無(wú)向邊；有向平行邊，聯(lián)結(jié)兩個(gè)結(jié)點(diǎn)之間的多于1條且方向相同的有向邊. 簡(jiǎn)單圖，不含平行邊和自回路的圖.,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,圖的基本概念 在無(wú)向圖G中，與結(jié)點(diǎn)v(V)關(guān)聯(lián)的邊數(shù)，即為結(jié)點(diǎn)度數(shù)deg(v)或d(v).； 有向圖G中，以結(jié)點(diǎn)v為始點(diǎn)的變的條數(shù)為該點(diǎn)的出度，記作deg+(v);以結(jié)點(diǎn)v為終點(diǎn)的邊為該點(diǎn)的入度，記作deg

4、(v)；結(jié)點(diǎn)v的出度和入度之和為度數(shù). 最大度數(shù)，(G)maxd(v)vV； 最小度數(shù)，(G)=mind(v)vV,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念1,圖的基本概念 有n個(gè)結(jié)點(diǎn)的且每對(duì)結(jié)點(diǎn)都有邊相連無(wú)向簡(jiǎn)單圖，無(wú)向完全圖Kn. 此時(shí)有 ；有n個(gè)結(jié)點(diǎn)的且每對(duì)結(jié)點(diǎn)之間都有兩條方向相反的邊相關(guān)連的有向簡(jiǎn)單圖為有向完全圖，.此時(shí)有 設(shè)G, V，E的子集V,E構(gòu)成的圖G=是圖G的子圖；若GG且GG，(VV或EE)，G是G的真子圖. 生成子圖，設(shè)圖G, 若EE, 則圖是的生成子圖. 即結(jié)點(diǎn)與原圖G相同的子圖，為生成子圖.,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,圖的基本概念 補(bǔ)圖 G=，設(shè)G, 以V

5、為結(jié)點(diǎn)集，以使G成為完全圖所添加的邊為邊集E的圖，就是圖G的補(bǔ)圖G ，即是完全圖, 其中EE. 圖的同構(gòu)，設(shè)G1=和G2=, 存在雙射f：V1V2，(vi,vj)E1, 當(dāng)且僅當(dāng) (f(vi),f(vj)E2，且(vi,vj)與 (f(vi),f(vj)的重?cái)?shù)相同. 則G1G2. 同構(gòu)充分條件：建立兩個(gè)圖的對(duì)應(yīng)關(guān)系，這個(gè)關(guān)系是雙射函數(shù). 同構(gòu)必要條件：結(jié)點(diǎn)數(shù)相同；邊數(shù)相同；度數(shù)相同的結(jié)點(diǎn)個(gè)數(shù)相同.,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,圖的基本概念 握手定理:結(jié)點(diǎn)度數(shù)之和為邊數(shù)的兩倍 設(shè)G=，有 在有向圖圖D中， 奇數(shù)度結(jié)點(diǎn)的個(gè)數(shù)為偶數(shù)個(gè). 如果一個(gè)圖中只有兩個(gè)奇數(shù)度節(jié)點(diǎn)，則這兩個(gè)節(jié)點(diǎn)相連通

6、。,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,通路、回路、圖的連通性 通路與通路的長(zhǎng)度，設(shè)圖G，Vv0,v1,vn,E=e1,e2,em,結(jié)點(diǎn)與邊的交替序列v0e1v1e2vi-1eivi,成為結(jié)點(diǎn)v0到結(jié)點(diǎn)vi的通路. v0,vi是通路的起點(diǎn)和終點(diǎn). 通路中邊的數(shù)目就是通路的長(zhǎng)度. 回路，起點(diǎn)和終點(diǎn)重合的通路. 簡(jiǎn)單通路(回路)：邊不重復(fù)的通路(回路). 初級(jí)通路(回路)：結(jié)點(diǎn)不重復(fù)的通路(回路). 復(fù)雜通路(回路)：邊有重復(fù)的通路(回路).,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,通路、回路、圖的連通性 定理：若圖中具有n各結(jié)點(diǎn)，從結(jié)點(diǎn)vi多幅奧結(jié)點(diǎn)vj存在一條通路，則從vi到vj存在一條不

7、多于n1條邊的通路 推論：在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，如果存在結(jié)點(diǎn)vi到vj的一條通路，則必存在一條從vi到vj的不多于n1條邊的初級(jí)通路 定理：在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，如果存在結(jié)點(diǎn)vi到自身的回路，則從vi到自身存在不多于n條邊的回路。 推論：在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，如果存在結(jié)點(diǎn)vi到自身的簡(jiǎn)單回路，則從vi到自身存在不多于n條邊的初級(jí)回路。,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,通路、回路、圖的連通性 連通與連通圖，無(wú)向圖G中，結(jié)點(diǎn)u,v存在通路，那么u,v是連通的，G中任意結(jié)點(diǎn)u,v都是連通的，G是連通圖. 連通分支，設(shè)G，V的連通等價(jià)類V1，V2，,Vm,子圖G(V1),G(V2)

8、,G(Vm)成為連通分支，P(G)表示圖G連通分支的個(gè)數(shù).,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,通路、回路、圖的連通性 點(diǎn)割集與割點(diǎn)，設(shè)無(wú)向圖G，存在結(jié)點(diǎn)集VV，使得P(GV)P(G)，而對(duì)任意VV，都有P（GV）P(G)，V稱為圖G的點(diǎn)割集. 若V是單元集，Vv，v叫做割點(diǎn). 邊割集與割邊，設(shè)無(wú)向圖G，存在邊集EE，使得P(GV)P(G)，而對(duì)任意EE，都有P（GE）P(G)，E稱為圖G的邊割集. 若E是單元集，Ee，e叫做割邊(橋).,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,通路、回路、圖的連通性 點(diǎn)連通度：最小的點(diǎn)割集的點(diǎn)數(shù)目 邊連通度：最小的邊割集的邊數(shù)目 定理5：,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)

9、孫繼榮,圖論圖的基本概念,通路、回路、圖的連通性 單側(cè)通路，有向圖中，任意一對(duì)結(jié)點(diǎn)之間至少有一個(gè)結(jié)點(diǎn)可達(dá)另一結(jié)點(diǎn). 強(qiáng)連通，在有向圖中任何一對(duì)結(jié)點(diǎn)都相互可達(dá). 弱連通，略去有向圖D各邊的方向成為無(wú)向連通圖，稱D是弱連通圖. 由定義可知：強(qiáng)連通 單側(cè)連通 弱連通.,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,通路、回路、圖的連通性 定理：一個(gè)有向圖是強(qiáng)連通的充分必要條件是G中有一個(gè)回路，它至少經(jīng)過(guò)每個(gè)結(jié)點(diǎn)一次的。 強(qiáng)分圖：既有強(qiáng)連通性的最大子圖 單側(cè)分圖：既有單側(cè)連通性的最大子圖 弱分圖：既有弱連通性的最大子圖 定理：在有向圖D中，它的每個(gè)結(jié)點(diǎn)位于且僅位于一個(gè)強(qiáng)分圖中,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的

10、基本概念,圖的矩陣表示 (無(wú)向圖)關(guān)聯(lián)矩陣設(shè)G=, 關(guān)聯(lián)矩陣M(G)= ,其中mij=vi與ej的關(guān)聯(lián)次數(shù)(行為結(jié)點(diǎn)，列為邊) 性質(zhì)： 列元素和為2 行元素和為結(jié)點(diǎn)的度數(shù) 若行元素和為0，則對(duì)應(yīng)的結(jié)點(diǎn)為孤立點(diǎn) 全部元素之和為G的總度數(shù) 平行邊對(duì)應(yīng)的兩列完全相同,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,圖的矩陣表示 (無(wú)向圖)相鄰矩陣:設(shè)G, ，相鄰矩陣 A(G)= ，其中aij =vi與vj相關(guān)聯(lián)的邊的條數(shù)(行、列均為結(jié)點(diǎn)) 性質(zhì)： A(G)是對(duì)稱矩陣 對(duì)角線上的元素表示該結(jié)點(diǎn)處環(huán)的個(gè)數(shù) ，若vi是孤立結(jié)點(diǎn)，則,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,圖的矩陣表示 （無(wú)環(huán)有向圖）關(guān)聯(lián)矩陣：設(shè)D

11、=, 關(guān)聯(lián)矩陣M(D)= , (行為結(jié)點(diǎn)，列為邊)， 其中,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,圖的矩陣表示 （無(wú)環(huán)有向圖）關(guān)聯(lián)矩陣： ，列元素和為0 每行元素絕對(duì)值之和等于對(duì)應(yīng)點(diǎn)的度數(shù)，其中1的個(gè)數(shù)為對(duì)應(yīng)點(diǎn)的出度，1的個(gè)數(shù)為對(duì)應(yīng)電的入度 所有元素的和為0，1的個(gè)數(shù)等于1的個(gè)數(shù)，都等于邊數(shù)m,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,圖的矩陣表示 （有向圖）鄰接矩陣：設(shè)D，相鄰矩陣 A(D)= ，其中aij =vi鄰接到vj的邊的條數(shù)(行、列均為結(jié)點(diǎn)) 所有元素之和為D中長(zhǎng)度為1的通路 有向圖的鄰接矩陣不一定對(duì)稱,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,圖的矩陣表示 由有向圖D的鄰接矩陣推斷從ai到aj 的長(zhǎng)度為l的通路的數(shù)目：Al(D) 由有向圖D的鄰接矩陣推斷D的可達(dá)矩陣P(D) P(D)= ，其中 P(D) A1(D) A2(D) An(D)將其中大于0的元素都改為1，再將主對(duì)角線上的元素改為1。,計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)孫繼榮,圖論圖的基本概念,最短路徑和關(guān)鍵路徑 帶權(quán)圖：G，其中W為