圖論基本概念課件

1、第五部分 圖論本部分主要內(nèi)容 圖的基本概念 歐拉圖、哈密頓圖 樹1圖論基本概念緒論圖論的歷史： 圖論的第一篇論文是瑞士數(shù)學(xué)家歐拉（Euler）發(fā)表于1736年出版的圣彼得堡科學(xué)院刊物中。討論一個所謂Konigsberg Seven Bridges Problem。2圖論基本概念緒論圖論的作用：圖與計算機(jī)：計算機(jī)中數(shù)據(jù)結(jié)構(gòu)，離不開數(shù)組、串、各種鏈接表、樹和圖，因此圖是計算機(jī)中數(shù)據(jù)表示、存儲和運(yùn)算的基礎(chǔ) 圖與網(wǎng)絡(luò)： 最大流問題：假設(shè)從城市P到城市Q的一個公路網(wǎng)， 公路網(wǎng)中每段公路上每天可以通過的汽車的數(shù)量有上限，那么經(jīng)過該公路網(wǎng)，每天最多可以有多少輛汽車從城市P開到城市Q？ 最優(yōu)支撐樹問題：某一地

2、區(qū)有若干個主要城市，擬修建高速公路把這些城市連接起來，使得從其中任何一個城市都可以經(jīng)高速公路直接或間接到達(dá)另一個城市。假設(shè)已經(jīng)知道了任意兩個城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最?。?圖論基本概念第十四章 圖的基本概念主要內(nèi)容圖通路與回路圖的連通性圖的矩陣表示圖的運(yùn)算預(yù)備知識多重集合元素可以重復(fù)出現(xiàn)的集合無序集AB=(x,y) | xAyB4圖論基本概念14.1 圖 無向圖G = , 其中(1) V 為頂點集，元素稱為頂點 Vertex(2) E為VV 的多重集，其元素稱為無向邊，簡稱邊 Edge實例 設(shè) V = v1, v2, ,v5, E = (v

3、1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 則 G = 為一無向圖5圖論基本概念有向圖 有向圖D=, 只需注意E是VV 的多重子集圖2表示的是一個有向圖，試寫出它的V 和 E 注意：圖的數(shù)學(xué)定義與圖形表示，在同構(gòu)（待敘）的意義下是一一對應(yīng)的6圖論基本概念相關(guān)概念1. 圖 可用G泛指圖（無向的或有向的） V(G), E(G), |V(G)|, |E(G)| n階圖：n 個頂點的圖2. 有限圖3. n 階零圖（0條邊）與平凡圖（1個頂點）4. 空圖（運(yùn)算中出現(xiàn)）5. 用 ek 表示無向邊或有向邊7圖論基本概念相關(guān)概念6.

4、頂點與邊的關(guān)聯(lián)關(guān)系 關(guān)聯(lián)、關(guān)聯(lián)次數(shù) 環(huán) 孤立點7. 頂點之間的相鄰與鄰接關(guān)系8圖論基本概念8. 鄰域與關(guān)聯(lián)集 vV(G) (G為無向圖) v 的關(guān)聯(lián)集 vV(D) (D為有向圖)9. 標(biāo)定圖與非標(biāo)定圖(頂點和邊指定編號的）10. 基圖（有向圖的有向邊改為無向邊）相關(guān)概念9圖論基本概念多重圖與簡單圖定義14.3 (1) 無向圖中的平行邊及重數(shù) 關(guān)聯(lián)一對頂點的邊多于一條，條數(shù)稱為重數(shù) (2) 有向圖中的平行邊及重數(shù)（注意方向性） (3) 多重圖 (4) 簡單圖（無平行邊和環(huán)）簡單圖是極其重要的概念 10圖論基本概念頂點的度數(shù) (1) 設(shè)G=為無向圖, vV, d(v)v的度數(shù), 簡稱度 (2) 設(shè)

5、D=為有向圖, vV, d+(v)v的出度 d(v)v的入度 d(v)v的度或度數(shù) (3) (G)（最大度）, (G)（最小度） 無向圖中 (4) +(D), +(D), (D), (D), (D), (D) (5) 度數(shù)為1的點稱為懸掛點，關(guān)聯(lián)的邊為懸掛邊； 奇頂點度與偶度頂點11圖論基本概念定理 設(shè)G=為任意無向圖，V=v1,v2,vn, |E|=m, 則證 G中每條邊 (包括環(huán)) 均有兩個端點，所以在計算G中各頂點度數(shù)之和時，每條邊均提供2度，m 條邊共提供 2m 度.此二定理是歐拉1736年給出，是圖論的基本定理握手定理 設(shè)D=為任意有向圖，V=v1,v2,vn, |E|=m, 則12

6、圖論基本概念握手定理推論推論 任何圖 (無向或有向) 中，奇度頂點的個數(shù)是偶數(shù).證 設(shè)G=為任意圖，令 V1=v | vV d(v)為奇數(shù) V2=v | vV d(v)為偶數(shù) 則V1V2=V, V1V2=，由握手定理可知由于2m, 均為偶數(shù)，所以 為偶數(shù)，但因為V1中頂點度數(shù)為奇數(shù)，所以|V1|必為偶數(shù). 13圖論基本概念圖的度數(shù)列1 . V=v1, v2, , vn為無向圖G的頂點集，稱d(v1), d(v2), , d(vn)為G的度數(shù)列 2. V=v1, v2, , vn為有向圖D的頂點集， D的度數(shù)列：d(v1), d(v2), , d(vn) D的出度列：d+(v1), d+(v2)

7、, , d+(vn) D的入度列：d(v1), d(v2), , d(vn) 3. 非負(fù)整數(shù)列d=(d1, d2, , dn)是可圖化的，是可簡單圖化的.易知：(2, 4, 6, 8, 10)，(1, 3, 3, 3, 4) 是可圖化的，后者又是可簡單圖化的，而(2, 2, 3, 4, 5)，(3, 3, 3, 4) 都不是可簡單圖化的，特別是后者也不是可圖化的14圖論基本概念圖的同構(gòu) 設(shè)G1=, G2=為兩個無向圖(兩個有向圖)，若存在雙射函數(shù)f:V1V2, 對于vi,vjV1, (vi,vj)E1 當(dāng)且僅當(dāng) (f(vi),f(vj)E2 （E1 當(dāng)且僅當(dāng) E2 )并且, (vi,vj)（）

8、與 (f(vi),f(vj)（）的重數(shù)相同，則稱G1與G2是同構(gòu)的，記作G1G2. 圖之間的同構(gòu)關(guān)系具有自反性、對稱性和傳遞性.能找到多條同構(gòu)的必要條件，但它們?nèi)皇浅浞謼l件： 邊數(shù)相同，頂點數(shù)相同; 度數(shù)列相同; 對應(yīng)頂點的關(guān)聯(lián)集及鄰域的元素個數(shù)相同，等等 若破壞必要條件，則兩圖不同構(gòu)判斷兩個圖同構(gòu)是個難題15圖論基本概念圖同構(gòu)的實例圖中(1)與(2)的度數(shù)列相同，它們同構(gòu)嗎？為什么？ (1) (2) (3) (4) 圖中，(1)與(2)不同構(gòu)（度數(shù)列不同），(3)與(4)也不同構(gòu). (1) (2) 16圖論基本概念n 階完全圖與競賽圖定義14.6 (1) n (n1) 階無向完全圖每個頂點

9、與其余頂點均相鄰的無向簡單圖，記作 Kn.簡單性質(zhì)：邊數(shù)(2) n (n1)階有向完全圖每對頂點之間均有兩條方向相反的有向邊的有向簡單圖.簡單性質(zhì)： (3) n (n1) 階競賽圖基圖為Kn的有向簡單圖.簡單性質(zhì)：邊數(shù) 17圖論基本概念n 階 k 正則圖(1)為K5，(2)為3階有向完全圖，(3)為4階競賽圖. (1) (2) (3) n 階k正則圖=k 的無向簡單圖簡單性質(zhì)：邊數(shù)（由握手定理得）Kn是 n1正則圖，彼得松圖（見書上圖14.3(1) 所示，記住它）18圖論基本概念子圖 G=, G=(1) GG G為G的子圖，G為G的母圖(2) 若GG且V=V，則稱G為G的生成子圖(3) 若VV

10、或EE，稱G為G的真子圖(4) V（VV且V）的導(dǎo)出子圖，記作GV(5) E（EE且E）的導(dǎo)出子圖，記作GE19圖論基本概念例2 畫出K4的所有非同構(gòu)的生成子圖實例20圖論基本概念補(bǔ)圖 設(shè)G=為n階無向簡單圖，以V為頂點集，以所有使G成為完全圖Kn的添加邊組成的集合為邊集的圖，稱為G的補(bǔ)圖，記作 .若G , 則稱G是自補(bǔ)圖. 相對于K4, 求上面圖中所有圖的補(bǔ)圖，并指出哪些是自補(bǔ)圖. 問：互為自補(bǔ)圖的兩個圖的邊數(shù)有何關(guān)系？21圖論基本概念14.2 通路與回路 給定圖G=（無向或有向的），G中頂點與邊的交替序列 = v0e1v1e2elvl，vi1, vi 是 ei 的端點.(1) 通路與回路：

11、 為通路；若 v0=vl， 為回路，l 為回路長 度.(2) 簡單通路與回路：所有邊各異， 為簡單通路，又若v0=vl， 為簡單回路(3) 初級通路(路徑)與初級回路(圈)： 中所有頂點各異，則稱 為初級通路(路徑)，又若除v0=vl，所有的頂點各不相同且所有的邊各異，則稱 為初級回路(圈)(4) 復(fù)雜通路與回路：有邊重復(fù)出現(xiàn)22圖論基本概念幾點說明表示法 定義表示法 只用邊表示法 只用頂點表示法（在簡單圖中） 混合表示法環(huán)（長為1的圈）的長度為1，兩條平行邊構(gòu)成的圈長度為 2，無向簡單圖中，圈長3，有向簡單圖中圈的長度2. 不同的圈（以長度3的為例） 定義意義下 無向圖：圖中長度為l（l3）

12、的圈，定義意義下為2l個 有向圖：圖中長度為l（l3）的圈，定義意義下為l個 同構(gòu)意義下：長度相同的圈均為1個試討論l=3和l=4的情況23圖論基本概念通路與回路的長度 在n 階圖G中，若從頂點vi 到vj（vivj）存在通路，則從vi 到 vj 存在長度小于或等于n1 的通路.推論 在 n 階圖G中，若從頂點vi 到 vj（vivj）存在通路，則從vi 到vj 存在長度小于或等于n1的初級通路（路徑）. 在一個n 階圖G中，若存在 vi 到自身的回路，則一定存在vi 到自身長度小于或等于 n 的回路.推論 在一個n 階圖G中，若存在 vi 到自身的簡單回路，則一定存在長度小于或等于n 的初級

13、回路.24圖論基本概念 圖的連通性無向圖的連通性(1) 頂點之間的連通關(guān)系：G=為無向圖 若 vi 與 vj 之間有通路，則 vivj 是V上的等價關(guān)系 R=| u,v V且uv (2) G的連通性與連通分支 若u,vV，uv，則稱G連通 V/R=V1,V2,Vk，稱GV1, GV2, ,GVk為連通分 支，其個數(shù) p(G)=k (k1)； k=1，G連通25圖論基本概念短程線與距離(3) 短程線與距離 u與v之間的短程線：uv，u與v之間長度最短的通路 u與v之間的距離：d(u,v)短程線的長度 d(u,v)的性質(zhì)： d(u,v)0, uv時d(u,v)= d(u,v)=d(v,u) d(u

14、,v)+d(v,w)d(u,w)26圖論基本概念無向圖的連通度1. 刪除頂點及刪除邊 Gv 從G中將v及關(guān)聯(lián)的邊去掉 GV從G中刪除V中所有的頂點 Ge 將e從G中去掉 GE刪除E中所有邊 2. 點割集與邊割集 點割集與割點 G=, VV V為點割集p(GV)p(G)且有極小性 v為割點v為點割集 G=, EE E是邊割集p(GE)p(G)且有極小性 e是割邊（橋）e為邊割集27圖論基本概念點割集與割點例3 v1,v4，v6是點割集，v6是割點. v2,v5是點割集嗎？e1,e2，e1,e3,e5,e6，e8等是邊割集，e8是橋，e7,e9,e5,e6 是邊割集嗎？幾點說明：Kn中無點割集，N

15、n中既無點割集，也無邊割集，其中Nn為 n 階零圖. 若G 連通，E為邊割集，則 p(GE)=2，V為點割集，則 p(GV)2 28圖論基本概念點連通度與邊連通度 G為連通非完全圖 點連通度 (G) = min |V |V 為點割集 規(guī)定 (Kn) = n1 若G非連通，(G) = 0 若 (G)k，則稱G為 k-連通圖 設(shè)G為連通圖 邊連通度(G) = min|E|E為邊割集 若G非連通，則(G) = 0 若(G)r，則稱G是 r 邊-連通圖圖中， =1，它是 1-連通圖 和 1邊-連通圖29圖論基本概念幾點說明(Kn)=(Kn)=n1G非連通，則 =0若G中有割點，則=1，若有橋，則=1若

16、(G)=k, 則G是1-連通圖，2-連通圖，k-連通圖，但不是(k+s)-連通圖，s1若(G)=r, 則G是1-邊連通圖，2-邊連通圖，r-邊連通圖，但不是(r+s)-邊連通圖，s1, , 之間的關(guān)系.定理 (G)(G)(G)請畫出一個的無向簡單圖30圖論基本概念有向圖的連通性 D=為有向圖 vi vj（vi 可達(dá) vj）vi 到vj 有通路 vi vj（vi 與vj 相互可達(dá)）性質(zhì) 具有自反性(vi vi)、傳遞性 具有自反性、對稱性、傳遞性 vi 到vj 的短程線與距離類似于無向圖中，只需注意距離表示法的不同(無向圖中d(vi,vj)，有向圖中d) 及 d無對稱性31圖論基本概念有向圖的連

17、通性及分類 D=為有向圖 D弱連通(連通)基圖為無向連通圖 D單向連通vi,vjV，vivj 或 vjvi D強(qiáng)連通vi,vjV，vivj易知，強(qiáng)連通單向連通弱連通判別法 D強(qiáng)連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個頂點至少一次的回路 D單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個頂點至少一次的通路32圖論基本概念擴(kuò)大路徑法無向圖中設(shè)G=為 n 階無向圖，E. 設(shè) l 為G中一條路徑，若此路徑的始點或終點與通路外的頂點相鄰，就將它們擴(kuò)到通路中來，繼續(xù)這一過程，直到最后得到的通路的兩個端點不與通路外的頂點相鄰為止. 設(shè)最后得到的路徑為l+k（長度為 l 的路徑擴(kuò)大成了長度為 l+k 的路徑），稱l+k為“極大路徑”，稱

18、使用此種方法證明問題的方法為“擴(kuò)大路徑法”.有向圖中類似討論，只需注意，在每步擴(kuò)大中保證有向邊方向的一致性.33圖論基本概念實例由某條路徑擴(kuò)大出的極大路徑不惟一，極大路徑不一定是圖中最長的路徑上圖中，(1)中實線邊所示的長為2的初始路徑，(2),(3),(4)中實線邊所示的都是它擴(kuò)展成的極大路徑. 還能找到另外的極大路徑嗎？ (1) (2) (4) (3)34圖論基本概念擴(kuò)大路徑法的應(yīng)用例4 設(shè) G 為 n（n3）階無向簡單圖， 2，證明G 中存在長度 +1 的圈.證 設(shè) = v0v1vl 是由初始路徑 0 用擴(kuò)大路徑法的得到的極大路徑，則 l （為什么？）. 因為v0 不與 外頂點相鄰，又

19、d(v0) ，因而在 上除 v1外，至少還存在 1個頂點與 v0 相鄰. 設(shè) vx 是離 v0 最遠(yuǎn)的頂點，于是 v0v1vxv0 為 G 中長度 +1 的圈. 35圖論基本概念二部圖 設(shè) G=為一個無向圖，若能將 V分成 V1和V2(V1V2=V，V1V2=)，使得 G 中的每條邊的兩個端點都是一個屬于V1，另一個屬于V2，則稱 G 為二部圖 ( 或稱二分圖、偶圖等 )，稱V1和V2為互補(bǔ)頂點子集，常將二部圖G記為. 又若G是簡單二部圖，V1中每個頂點均與V2中所有的頂點相鄰，則稱G為完全二部圖，記為 Kr,s，其中r=|V1|，s=|V2|. 注意，n 階零圖為二部圖. 36圖論基本概念二

20、部圖的判別法 無向圖G=是二部圖當(dāng)且僅當(dāng)G中無奇圈 由定理14.10可知圖9中各圖都是二部圖，哪些是完全二部圖？哪些圖是同構(gòu)的？37圖論基本概念14.4 圖的矩陣表示無向圖的關(guān)聯(lián)矩陣（對圖無限制） 無向圖G=，|V|=n，|E|=m，令 mij為 vi 與 ej的關(guān)聯(lián)次數(shù)，稱(mij)nm為G 的關(guān)聯(lián)矩陣，記為M(G). 性質(zhì)38圖論基本概念有向圖的關(guān)聯(lián)矩陣（無環(huán)有向圖） 定義 有向圖D=，令則稱 (mij)nm為D的關(guān)聯(lián)矩陣，記為M(D). (4) 平行邊對應(yīng)的列相同性質(zhì)有向圖的關(guān)聯(lián)矩陣39圖論基本概念有向圖的鄰接矩陣（無限制） 設(shè)有向圖D=, V=v1, v2, , vn, E=e1, e

21、2, , em, 令為頂點 vi 鄰接到頂點 vj 邊的條數(shù)，稱為D的鄰接矩陣，記作A(D)，或簡記為A. 性質(zhì) 40圖論基本概念推論 設(shè)Bl=A+A2+Al（l1），則 Bl中元素為D中長度為 l 的通路總數(shù)， 設(shè) A為有向圖 D 的鄰接矩陣，V=v1, v2, , vn為頂點集，則 A 的 l 次冪 Al（l1）中元素為D中vi 到vj長度為 l 的通路數(shù)，其中為vi到自身長度為 l 的回路數(shù)，而為D中長度小于或等于 l 的回路數(shù)為D中長度小于或等于 l 的通路數(shù). 鄰接矩陣的應(yīng)用為D 中長度為 l 的回路總數(shù). 41圖論基本概念例5 有向圖D如圖所示，求 A, A2, A3, A4，并回

22、答諸問題：(1) D 中長度為1, 2, 3, 4的通路各有多少條？其中回路分別為多少條？(2) D 中長度小于或等于4的通路為多少條？其中有多少條回路？實例42圖論基本概念(1) D中長度為1的通路為8條，其中有1條是回路. D中長度為2的通路為11條，其中有3條是回路. D中長度為3和4的通路分別為14和17條，回路分別 為1與3條.(2) D中長度小于等于4的通路為50條，其中有8條是回路.實例求解43圖論基本概念 設(shè)D=為有向圖. V=v1, v2, , vn, 令 有向圖的可達(dá)矩陣（無限制）稱 (pij)nn 為D的可達(dá)矩陣，記作P(D)，簡記為P. 由于viV，vivi，所以P(D

23、)主對角線上的元素全為1. 由定義不難看出, D 強(qiáng)連通當(dāng)且僅當(dāng) P(D)為全1矩陣. 下圖所示有向圖 D 的可達(dá)矩陣為44圖論基本概念第十四章 習(xí)題課主要內(nèi)容無向圖、有向圖、關(guān)聯(lián)與相鄰、簡單圖、完全圖、正則圖、子圖、補(bǔ)圖；握手定理與推論；圖的同構(gòu)通路與回路及其分類無向圖的連通性與連通度有向圖的連通性及其分類圖的矩陣表示45圖論基本概念基本要求深刻理解握手定理及推論的內(nèi)容并能靈活地應(yīng)用它們深刻理解圖同構(gòu)、簡單圖、完全圖、正則圖、子圖、補(bǔ)圖、二部圖的概念以及它們的性質(zhì)及相互之間的關(guān)系記住通路與回路的定義、分類及表示法深刻理解與無向圖連通性、連通度有關(guān)的諸多概念會判別有向圖連通性的類型熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會求可達(dá)矩陣 46圖論基本概念19階無向圖G中，每個頂點的度數(shù)不是5就是6. 證明G中至少有5個6度頂點或至少有6個5度頂點. 練習(xí)1證 關(guān)鍵是利用握手定理的推論. 方法一：窮舉法設(shè)G中有x個5度頂點，則必有(9x)個6度頂點，由握手定理推論可知，(x,9x)只有5種可能：(0,9), (2,7), (4,5), (6,3), (8,1）它們都滿足要求. 方法二：反證法否則，由握手定理推論可知，“G