圖論圖的基本概念

圖論圖的基本概念第一頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念教學(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)用。知道帶權(quán)圖、最短通路概念，知道關(guān)鍵路徑概念

計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)－孫繼榮第二頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念學(xué)習(xí)內(nèi)容：

圖的概念

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

圖的矩陣表示

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

計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)－孫繼榮第三頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念本章重點(diǎn)圖的概念握手定理通路回路圖的矩陣表示.

計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)－孫繼榮第四頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念圖的基本概念圖是指某些具體的事物以及這些事物之間的聯(lián)系圖是一個(gè)有序?qū)?lt;V，E>，V是結(jié)點(diǎn)集，E是邊集，當(dāng)V,E有限時(shí)，<V,E>稱為有限圖；否則稱無(wú)限圖.無(wú)向邊,與無(wú)序結(jié)點(diǎn)(v,u)相關(guān)聯(lián)的邊有向邊，與有序結(jié)點(diǎn)<v,u>相關(guān)聯(lián)的邊.無(wú)向圖，每條邊都是無(wú)向邊的圖，記作G＝<V,E>;每條邊都是有向邊的圖，記作D＝<V,E>.混合圖，既有有向邊，也有無(wú)向邊的圖.計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)－孫繼榮第五頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念圖的基本概念平凡圖，僅有一個(gè)結(jié)點(diǎn)的圖；零圖（空?qǐng)D）：邊集為空集的圖<V,>，即僅有結(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ǔ)－孫繼榮第六頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念圖的基本概念在無(wú)向圖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ǔ)－孫繼榮第七頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念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的子集V,E構(gòu)成的圖G=<V,E>是圖G的子圖；若GG且GG，(VV或EE)，G是G的真子圖.生成子圖，設(shè)圖G＝<V,E>,若EE,則圖<V,E>是<V,E>的生成子圖.即結(jié)點(diǎn)與原圖G相同的子圖，為生成子圖.

計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)－孫繼榮第八頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念圖的基本概念補(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è)圖的對(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ǔ)－孫繼榮第九頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念圖的基本概念握手定理:結(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ǔ)－孫繼榮第十頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念通路、回路、圖的連通性通路與通路的長(zhǎng)度，設(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ù)目就是通路的長(zhǎng)度.回路，起點(diǎn)和終點(diǎn)重合的通路.簡(jiǎn)單通路(回路)：邊不重復(fù)的通路(回路).初級(jí)通路(回路)：結(jié)點(diǎn)不重復(fù)的通路(回路).復(fù)雜通路(回路)：邊有重復(fù)的通路(回路).計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)－孫繼榮第十一頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念通路、回路、圖的連通性定理：若圖中具有n各結(jié)點(diǎn)，從結(jié)點(diǎn)vi多幅奧結(jié)點(diǎn)vj存在一條通路，則從vi到vj存在一條不多于n－1條邊的通路推論：在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，如果存在結(jié)點(diǎn)vi到vj的一條通路，則必存在一條從vi到vj的不多于n－1條邊的初級(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ǔ)－孫繼榮第十二頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念通路、回路、圖的連通性連通與連通圖，無(wú)向圖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ǔ)－孫繼榮第十三頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念通路、回路、圖的連通性點(diǎn)割集與割點(diǎn)，設(shè)無(wú)向圖G＝<V，E>，存在結(jié)點(diǎn)集VV，使得P(G－V)>P(G)，而對(duì)任意VV，都有P（G－V）＝P(G)，V稱為圖G的點(diǎn)割集.若V是單元集，V＝{v}，v叫做割點(diǎn).邊割集與割邊，設(shè)無(wú)向圖G＝<V，E>，存在邊集EE，使得P(G－V)>P(G)，而對(duì)任意EE，都有P（G－E）＝P(G)，E稱為圖G的邊割集.若E是單元集，E＝{e}，e叫做割邊(橋).

計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)－孫繼榮第十四頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念通路、回路、圖的連通性點(diǎn)連通度：最小的點(diǎn)割集的點(diǎn)數(shù)目邊連通度：最小的邊割集的邊數(shù)目定理5：計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)－孫繼榮第十五頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念通路、回路、圖的連通性單側(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ǔ)－孫繼榮第十六頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念通路、回路、圖的連通性定理：一個(gè)有向圖是強(qiáng)連通的充分必要條件是G中有一個(gè)回路，它至少經(jīng)過(guò)每個(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ǔ)－孫繼榮第十七頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念圖的矩陣表示

(無(wú)向圖)關(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，則對(duì)應(yīng)的結(jié)點(diǎn)為孤立點(diǎn)全部元素之和為G的總度數(shù)平行邊對(duì)應(yīng)的兩列完全相同計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)－孫繼榮第十八頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念圖的矩陣表示(無(wú)向圖)相鄰矩陣:設(shè)G＝<V,E>,，相鄰矩陣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ǔ)－孫繼榮第十九頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念圖的矩陣表示（無(wú)環(huán)有向圖）關(guān)聯(lián)矩陣：設(shè)D=<V,E>,關(guān)聯(lián)矩陣M(D)=,(行為結(jié)點(diǎn)，列為邊)，

其中計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)－孫繼榮第二十頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念圖的矩陣表示（無(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ǔ)－孫繼榮第二十一頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念圖的矩陣表示（有向圖）鄰接矩陣：設(shè)D＝<V,E>，相鄰矩陣A(D)=，其中aij=vi鄰接到vj的邊的條數(shù)(行、列均為結(jié)點(diǎn))所有元素之和為D中長(zhǎng)度為1的通路

有向圖的鄰接矩陣不一定對(duì)稱計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)－孫繼榮第二十二頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念圖的矩陣表示由有向圖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ǔ)－孫繼榮第二十三頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖論－圖的基本概念最短路徑和關(guān)鍵路徑帶權(quán)圖：G<V,