圖論圖的基本概念

圖論圖的基本概念第1頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念教學要求理解圖的概念：結點、邊、有向圖，無向圖、圖的同構、簡單圖、完全圖、結點的度數(shù)、子圖、邊的重數(shù)和平行邊等理解握手定理了解通路與回路概念：通路(簡單通路、初級通路和復雜通路)，回路(簡單回路、初級回路和復雜回路)，會求通路和回路的長度了解無向圖的連通性，會求無向圖的連通分支。了解點割集、割點、邊割集、割邊、點連通度、邊連通度等概念了解有向圖的強連通強性；會判別其類型了解(有向圖、無向圖)關聯(lián)矩陣、(無向圖)相鄰矩陣和(有向圖)鄰接矩陣的概念，掌握構造方法及其應用。知道帶權圖、最短通路概念，知道關鍵路徑概念

計算機數(shù)學基礎－孫繼榮第2頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念學習內(nèi)容：

圖的概念

（圖的表示，有向圖、無向圖、度、同構）

圖的矩陣表示

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

計算機數(shù)學基礎－孫繼榮第3頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念本章重點圖的概念握手定理通路回路圖的矩陣表示.

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

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

簡單圖，不含平行邊和自回路的圖.計算機數(shù)學基礎－孫繼榮第6頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念圖的基本概念在無向圖G＝<V,E>中，與結點v(V)關聯(lián)的邊數(shù)，即為結點度數(shù)deg(v)或d(v).；有向圖G＝<V,E>中，，以結點v為始點的變的條數(shù)為該點的出度，記作deg+(v);以結點v為終點的邊為該點的入度，記作deg－(v)；結點v的出度和入度之和為度數(shù).最大度數(shù)，(G)＝max{d(v)vV}；

最小度數(shù)，(G)=min{d(v)vV}計算機數(shù)學基礎－孫繼榮第7頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念1圖的基本概念有n個結點的且每對結點都有邊相連無向簡單圖，無向完全圖Kn.此時有；有n個結點的且每對結點之間都有兩條方向相反的邊相關連的有向簡單圖為有向完全圖，.此時有設G＝<V,E>,V，E的子集V,E構成的圖G=<V,E>是圖G的子圖；若GG且GG，(VV或EE)，G是G的真子圖.生成子圖，設圖G＝<V,E>,若EE,則圖<V,E>是<V,E>的生成子圖.即結點與原圖G相同的子圖，為生成子圖.

計算機數(shù)學基礎－孫繼榮第8頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念圖的基本概念補圖G=<V,E>，設G＝<V,E>,以V為結點集，以使G成為完全圖所添加的邊為邊集E的圖，就是圖G的補圖G

，即<V,EE>是完全圖,其中EE＝.圖的同構，設G1=<V1,E1>和G2=<V2,E2>,存在雙射f：V1V2，(vi,vj)E1,當且僅當

(f(vi),f(vj))E2，且(vi,vj)與

(f(vi),f(vj))的重數(shù)相同.則G1≌G2.同構充分條件：建立兩個圖的對應關系，這個關系是雙射函數(shù).同構必要條件：①結點數(shù)相同；②邊數(shù)相同；③度數(shù)相同的結點個數(shù)相同.

計算機數(shù)學基礎－孫繼榮第9頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念圖的基本概念握手定理:結點度數(shù)之和為邊數(shù)的兩倍設G=<V，E>，有在有向圖圖D＝<V,E>中，奇數(shù)度結點的個數(shù)為偶數(shù)個.如果一個圖中只有兩個奇數(shù)度節(jié)點，則這兩個節(jié)點相連通。計算機數(shù)學基礎－孫繼榮第10頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念通路、回路、圖的連通性通路與通路的長度，設圖G＝<V，E>，V＝{v0,v1,…,vn},E={e1,e2,…,em},結點與邊的交替序列v0e1v1e2…vi-1eivi,成為結點v0到結點vi的通路.v0,vi是通路的起點和終點.通路中邊的數(shù)目就是通路的長度.回路，起點和終點重合的通路.簡單通路(回路)：邊不重復的通路(回路).初級通路(回路)：結點不重復的通路(回路).復雜通路(回路)：邊有重復的通路(回路).計算機數(shù)學基礎－孫繼榮第11頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念通路、回路、圖的連通性定理：若圖中具有n各結點，從結點vi多幅奧結點vj存在一條通路，則從vi到vj存在一條不多于n－1條邊的通路推論：在一個具有n個結點的圖中，如果存在結點vi到vj的一條通路，則必存在一條從vi到vj的不多于n－1條邊的初級通路定理：在一個具有n個結點的圖中，如果存在結點vi到自身的回路，則從vi到自身存在不多于n條邊的回路。推論：在一個具有n個結點的圖中，如果存在結點vi到自身的簡單回路，則從vi到自身存在不多于n條邊的初級回路。計算機數(shù)學基礎－孫繼榮第12頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念通路、回路、圖的連通性連通與連通圖，無向圖G中，結點u,v存在通路，那么u,v是連通的，G中任意結點u,v都是連通的，G是連通圖.連通分支，設G＝<V,E>，V的連通等價類V1，V2，…,Vm,子圖G(V1),G(V2),…,G(Vm)成為連通分支，P(G)表示圖G連通分支的個數(shù).計算機數(shù)學基礎－孫繼榮第13頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念通路、回路、圖的連通性點割集與割點，設無向圖G＝<V，E>，存在結點集VV，使得P(G－V)>P(G)，而對任意VV，都有P（G－V）＝P(G)，V稱為圖G的點割集.若V是單元集，V＝{v}，v叫做割點.邊割集與割邊，設無向圖G＝<V，E>，存在邊集EE，使得P(G－V)>P(G)，而對任意EE，都有P（G－E）＝P(G)，E稱為圖G的邊割集.若E是單元集，E＝{e}，e叫做割邊(橋).

計算機數(shù)學基礎－孫繼榮第14頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念通路、回路、圖的連通性點連通度：最小的點割集的點數(shù)目邊連通度：最小的邊割集的邊數(shù)目定理5：計算機數(shù)學基礎－孫繼榮第15頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念通路、回路、圖的連通性單側(cè)通路，有向圖中，任意一對結點之間至少有一個結點可達另一結點.強連通，在有向圖中任何一對結點都相互可達.弱連通，略去有向圖D各邊的方向成為無向連通圖，稱D是弱連通圖.由定義可知：強連通單側(cè)連通弱連通.計算機數(shù)學基礎－孫繼榮第16頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念通路、回路、圖的連通性定理：一個有向圖是強連通的充分必要條件是G中有一個回路，它至少經(jīng)過每個結點一次的。強分圖：既有強連通性的最大子圖單側(cè)分圖：既有單側(cè)連通性的最大子圖弱分圖：既有弱連通性的最大子圖定理：在有向圖D＝<V，E>中，它的每個結點位于且僅位于一個強分圖中計算機數(shù)學基礎－孫繼榮第17頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念圖的矩陣表示

(無向圖)關聯(lián)矩陣設G=<V,E>,關聯(lián)矩陣M(G)=,其中mij=vi與ej的關聯(lián)次數(shù)(行為結點，列為邊)性質(zhì)：列元素和為2行元素和為結點的度數(shù)若行元素和為0，則對應的結點為孤立點全部元素之和為G的總度數(shù)平行邊對應的兩列完全相同計算機數(shù)學基礎－孫繼榮第18頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念圖的矩陣表示(無向圖)相鄰矩陣:設G＝<V,E>,，相鄰矩陣A(G)=，其中aij=vi與vj相關聯(lián)的邊的條數(shù)(行、列均為結點)性質(zhì)：A(G)是對稱矩陣對角線上的元素表示該結點處環(huán)的個數(shù)，若vi是孤立結點，則計算機數(shù)學基礎－孫繼榮第19頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念圖的矩陣表示（無環(huán)有向圖）關聯(lián)矩陣：設D=<V,E>,關聯(lián)矩陣M(D)=,(行為結點，列為邊)，

其中計算機數(shù)學基礎－孫繼榮第20頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念圖的矩陣表示（無環(huán)有向圖）關聯(lián)矩陣：

，列元素和為0每行元素絕對值之和等于對應點的度數(shù)，其中1的個數(shù)為對應點的出度，－1的個數(shù)為對應電的入度所有元素的和為0，1的個數(shù)等于－1的個數(shù)，都等于邊數(shù)m計算機數(shù)學基礎－孫繼榮第21頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念圖的矩陣表示（有向圖）鄰接矩陣：設D＝<V,E>，相鄰矩陣A(D)=，其中aij=vi鄰接到vj的邊的條數(shù)(行、列均為結點)所有元素之和為D中長度為1的通路

有向圖的鄰接矩陣不一定對稱計算機數(shù)學基礎－孫繼榮第22頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念圖的矩陣表示由有向圖D的鄰接矩陣推斷從ai到aj

的長度為l的通路的數(shù)目：Al(D)由有向圖D的鄰接矩陣推斷D的可達矩陣P(D)P(D)=，其中

P(D)＝A1(D)＋A2(D)＋…＋An(D)將其中大于0的元素都改為1，再將主對角線上的元素改為1。計算機數(shù)學基礎－孫繼榮第23頁，共25頁，2023年，2月20日，星期六圖論－圖的基本概念最短路徑和關鍵路徑帶權圖：G<V,