圖論-圖的基本概念

圖論－圖的基本概念教師：孫繼榮電話：87768609Email:圖論－圖的基本概念教學(xué)要求理解圖的概念：結(jié)點、邊、有向圖，無向圖、圖的同構(gòu)、簡單圖、完全圖、結(jié)點的度數(shù)、子圖、邊的重數(shù)和平行邊等理解握手定理了解通路與回路概念：通路(簡單通路、初級通路和復(fù)雜通路)，回路(簡單回路、初級回路和復(fù)雜回路)，會求通路和回路的長度了解無向圖的連通性，會求無向圖的連通分支。了解點割集、割點、邊割集、割邊、點連通度、邊連通度等概念了解有向圖的強連通強性；會判別其類型了解(有向圖、無向圖)關(guān)聯(lián)矩陣、(無向圖)相鄰矩陣和(有向圖)鄰接矩陣的概念，掌握構(gòu)造方法及其應(yīng)用。知道帶權(quán)圖、最短通路概念，知道關(guān)鍵路徑概念

計算機數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念學(xué)習(xí)內(nèi)容：

圖的概念

（圖的表示，有向圖、無向圖、度、同構(gòu)）

圖的矩陣表示

（鄰接矩陣，關(guān)聯(lián)矩陣）

計算機數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念圖的基本概念圖是指某些具體的事物以及這些事物之間的聯(lián)系圖是一個有序?qū)?lt;V，E>，V是結(jié)點集，E是邊集，當(dāng)V,E有限時，<V,E>稱為有限圖；否則稱無限圖.無向邊,與無序結(jié)點(v,u)相關(guān)聯(lián)的邊有向邊，與有序結(jié)點<v,u>相關(guān)聯(lián)的邊.無向圖，每條邊都是無向邊的圖，記作G＝<V,E>;每條邊都是有向邊的圖，記作D＝<V,E>.混合圖，既有有向邊，也有無向邊的圖.計算機數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念圖的基本概念平凡圖，僅有一個結(jié)點的圖；零圖（空圖）：邊集為空集的圖<V,>，即僅有結(jié)點的圖.自回路(環(huán))，關(guān)聯(lián)于同一個結(jié)點的邊.

無向平行邊，聯(lián)結(jié)相同兩個結(jié)點的多于1條的無向邊；有向平行邊，聯(lián)結(jié)兩個結(jié)點之間的多于1條且方向相同的有向邊.

簡單圖，不含平行邊和自回路的圖.計算機數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念圖的基本概念在無向圖G＝<V,E>中，與結(jié)點v(V)關(guān)聯(lián)的邊數(shù)，即為結(jié)點度數(shù)deg(v)或d(v).；有向圖G＝<V,E>中，，以結(jié)點v為始點的變的條數(shù)為該點的出度，記作deg+(v);以結(jié)點v為終點的邊為該點的入度，記作deg－(v)；結(jié)點v的出度和入度之和為度數(shù).最大度數(shù)，(G)＝max{d(v)vV}；

最小度數(shù)，(G)=min{d(v)vV}計算機數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念圖的基本概念補圖G=<V,E>，設(shè)G＝<V,E>,以V為結(jié)點集，以使G成為完全圖所添加的邊為邊集E的圖，就是圖G的補圖G

，即<V,EE>是完全圖,其中EE＝.圖的同構(gòu)，設(shè)G1=<V1,E1>和G2=<V2,E2>,存在雙射f：V1V2，(vi,vj)E1,當(dāng)且僅當(dāng)(f(vi),f(vj))E2，且(vi,vj)與(f(vi),f(vj))的重數(shù)相同.則G1≌G2.同構(gòu)充分條件：建立兩個圖的對應(yīng)關(guān)系，這個關(guān)系是雙射函數(shù).同構(gòu)必要條件：①結(jié)點數(shù)相同；②邊數(shù)相同；③度數(shù)相同的結(jié)點個數(shù)相同.

計算機數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念圖的基本概念握手定理:結(jié)點度數(shù)之和為邊數(shù)的兩倍設(shè)G=<V，E>，有在有向圖圖D＝<V,E>中，奇數(shù)度結(jié)點的個數(shù)為偶數(shù)個.如果一個圖中只有兩個奇數(shù)度節(jié)點，則這兩個節(jié)點相連通。計算機數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念通路、回路、圖的連通性通路與通路的長度，設(shè)圖G＝<V，E>，V＝{v0,v1,…,vn},E={e1,e2,…,em},結(jié)點與邊的交替序列v0e1v1e2…vi-1eivi,成為結(jié)點v0到結(jié)點vi的通路.v0,vi是通路的起點和終點.通路中邊的數(shù)目就是通路的長度.回路，起點和終點重合的通路.簡單通路(回路)：邊不重復(fù)的通路(回路).初級通路(回路)：結(jié)點不重復(fù)的通路(回路).復(fù)雜通路(回路)：邊有重復(fù)的通路(回路).計算機數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念通路、回路、圖的連通性連通與連通圖，無向圖G中，結(jié)點u,v存在通路，那么u,v是連通的，G中任意結(jié)點u,v都是連通的，G是連通圖.連通分支，設(shè)G＝<V,E>，V的連通等價類V1，V2，…,Vm,子圖G(V1),G(V2),…,G(Vm)成為連通分支，P(G)表示圖G連通分支的個數(shù).計算機數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念通路、回路、圖的連通性點割集與割點，設(shè)無向圖G＝<V，E>，存在結(jié)點集VV，使得P(G－V)>P(G)，而對任意VV，都有P（G－V）＝P(G)，V稱為圖G的點割集.若V是單元集，V＝{v}，v叫做割點.邊割集與割邊，設(shè)無向圖G＝<V，E>，存在邊集EE，使得P(G－V)>P(G)，而對任意EE，都有P（G－E）＝P(G)，E稱為圖G的邊割集.若E是單元集，E＝{e}，e叫做割邊(橋).

計算機數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念通路、回路、圖的連通性點連通度：最小的點割集的點數(shù)目邊連通度：最小的邊割集的邊數(shù)目定理5：計算機數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念通路、回路、圖的連通性定理：一個有向圖是強連通的充分必要條件是G中有一個回路，它至少經(jīng)過每個結(jié)點一次的。強分圖：既有強連通性的最大子圖單側(cè)分圖：既有單側(cè)連通性的最大子圖弱分圖：既有弱連通性的最大子圖定理：在有向圖D＝<V，E>中，它的每個結(jié)點位于且僅位于一個強分圖中計算機數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念圖的矩陣表示(無向圖)關(guān)聯(lián)矩陣設(shè)G=<V,E>,關(guān)聯(lián)矩陣M(G)=,其中mij=vi與ej的關(guān)聯(lián)次數(shù)(行為結(jié)點，列為邊)性質(zhì)：列元素和為2行元素和為結(jié)點的度數(shù)若行元素和為0，則對應(yīng)的結(jié)點為孤立點全部元素之和為G的總度數(shù)平行邊對應(yīng)的兩列完全相同計算機數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念圖的矩陣表示(無向圖)相鄰矩陣:設(shè)G＝<V,E>,，相鄰矩陣A(G)=，其中aij=vi與vj相關(guān)聯(lián)的邊的條數(shù)(行、列均為結(jié)點)性質(zhì)：A(G)是對稱矩陣對角線上的元素表示該結(jié)點處環(huán)的個數(shù)，若vi是孤立結(jié)點，則計算機數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念圖的矩陣表示（無環(huán)有向圖）關(guān)聯(lián)矩陣：

，列元素和為0每行元素絕對值之和等于對應(yīng)點的度數(shù)，其中1的個數(shù)為對應(yīng)點的出度，－1的個數(shù)為對應(yīng)電的入度所有元素的和為0，1的個數(shù)等于－1的個數(shù)，都等于邊數(shù)m計算機數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念圖的矩陣表示（有向圖）鄰接矩陣：設(shè)D＝<V,E>，相鄰矩陣A(D)=，其中aij=vi鄰接到vj的邊的條數(shù)(行、列均為結(jié)點)所有元素之和為D中長度為1的通路

有向圖的鄰接矩陣不一定對稱計算機數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念圖的矩陣表示由有向圖D的鄰接矩陣推斷從ai到aj的長度為l的通路的數(shù)目：Al(D)由有向圖D的鄰接矩陣推斷