圖論-圖的基本概念

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

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

圖的概念

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

圖的矩陣表示

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

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

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

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

最小度數(shù)，(G)=min{d(v)vV}計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念圖的基本概念補(bǔ)圖G=<V,E>，設(shè)G＝<V,E>,以V為結(jié)點(diǎn)集，以使G成為完全圖所添加的邊為邊集E的圖，就是圖G的補(bǔ)圖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))的重?cái)?shù)相同.則G1≌G2.同構(gòu)充分條件：建立兩個(gè)圖的對應(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=<V，E>，有在有向圖圖D＝<V,E>中，奇數(shù)度結(jié)點(diǎn)的個(gè)數(shù)為偶數(shù)個(gè).如果一個(gè)圖中只有兩個(gè)奇數(shù)度節(jié)點(diǎn)，則這兩個(gè)節(jié)點(diǎn)相連通。計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念通路、回路、圖的連通性通路與通路的長度，設(shè)圖G＝<V，E>，V＝{v0,v1,…,vn},E={e1,e2,…,em},結(jié)點(diǎn)與邊的交替序列v0e1v1e2…vi-1eivi,成為結(jié)點(diǎn)v0到結(jié)點(diǎn)vi的通路.v0,vi是通路的起點(diǎn)和終點(diǎn).通路中邊的數(shù)目就是通路的長度.回路，起點(diǎn)和終點(diǎn)重合的通路.簡單通路(回路)：邊不重復(fù)的通路(回路).初級通路(回路)：結(jié)點(diǎn)不重復(fù)的通路(回路).復(fù)雜通路(回路)：邊有重復(fù)的通路(回路).計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念通路、回路、圖的連通性連通與連通圖，無向圖G中，結(jié)點(diǎn)u,v存在通路，那么u,v是連通的，G中任意結(jié)點(diǎn)u,v都是連通的，G是連通圖.連通分支，設(shè)G＝<V,E>，V的連通等價(jià)類V1，V2，…,Vm,子圖G(V1),G(V2),…,G(Vm)成為連通分支，P(G)表示圖G連通分支的個(gè)數(shù).計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)－孫繼榮圖論－圖的基本概念通路、回路、圖的連通性點(diǎn)割集與割點(diǎn)，設(shè)無向圖G＝<V，E>，存在結(jié)點(diǎn)集VV，使得P(G－V)>P(G)，而對任意VV，都有P（G－V）＝P(G)，V稱為圖G的點(diǎn)割集.若V是單元集，V＝{v}，v叫做割點(diǎn).邊割集與割邊，設(shè)無向圖G＝<V，E>，存在邊集EE，使得P(G－V)>P(G)，而對任意EE，都有P（G－E）＝P(G)，E稱為圖G的邊割集.若E是單元集，E＝{e}，e叫做割邊(橋).

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

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

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