圖論圖的基本概念PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1圖論圖的基本概念圖論圖的基本概念第1頁/共115頁第2頁/共115頁。例如 在多重集合a,a,b,b,b,c,d中，a,b,c,d的重復(fù)度分別為2,3,1,1。第3頁/共115頁第4頁/共115頁頂點(diǎn)或結(jié)點(diǎn)。（2）E為邊集，它是笛卡兒積VV的多重子集，其元素稱為有向邊，簡稱邊。q可以用圖形表示圖，即用小圓圈（或?qū)嵭狞c(diǎn)）表示頂點(diǎn)，用頂點(diǎn)之間的連線表示無向邊，用有方向的連線表示有向邊。 第5頁/共115頁 (1) 給定無向圖G，其中 Vv1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5). (2)

2、給定有向圖D=，其中 Va,b,c,d，E,。 畫出G與D的圖形。第6頁/共115頁此時(shí)，又若G為n階圖，則稱G為n階零圖，記作Nn，特別地，稱N1為平凡圖。n在圖的定義中規(guī)定頂點(diǎn)集V為非空集，但在圖的運(yùn)算中可能產(chǎn)生頂點(diǎn)集為空集的運(yùn)算結(jié)果，為此規(guī)定頂點(diǎn)集為空集的圖為空圖，并將空圖記為。第7頁/共115頁基圖的有向圖。第8頁/共115頁n設(shè)D為有向圖，ekE，稱vi,vj為ek的端點(diǎn)。若vivj，則稱ek為D中的環(huán)。n無論在無向圖中還是在有向圖中，無邊關(guān)聯(lián)的頂點(diǎn)均稱為孤立點(diǎn)。第9頁/共115頁接于vi。若ek的終點(diǎn)為el的始點(diǎn)，則稱ek與el相鄰。第10頁/共115頁稱u|uVEuv為v的先驅(qū)元

3、集，記做-D(v)。稱+D(v) 為v的出鄰域, -D(v)為v 的入鄰域. +D(v)-D(v)為v的鄰域，記做ND(v)。稱ND(v)v為v的閉鄰域，記做ND(v)。第11頁/共115頁+D(d ) v2，v5NG(v1) v1，v2，v5IG(v1) e1，e2，e3 c-D(d ) a，cND(d ) a，cND(d ) a，c，d第12頁/共115頁例如：在圖1.1中，(a)中e5與e6是平行邊，(b)中e2與e3是平行邊，但e6與e7不是平行邊。(a)和(b)兩個(gè)圖都不是簡單圖。第13頁/共115頁D，。稱d+(v)+d-(v)為v的度數(shù)，記做d(v)。注:某個(gè)點(diǎn)上的有向環(huán)要對這個(gè)

4、點(diǎn)計(jì)算一次入度計(jì)算一次出度.第14頁/共115頁maxd+(v)|vV(D)最小出度+(D)mind+(v)|vV(D)最大入度-(D)maxd-(v)|vV(D)最小入度-(D)mind-(v)|vV(D)第15頁/共115頁d+(a)4，d-(a)1(環(huán)e1提供出度1，提供入度1)，d(a)4+15。5，3，+4 (在a點(diǎn)達(dá)到)+0(在b點(diǎn)達(dá)到)-3(在b點(diǎn)達(dá)到)-1(在a和c點(diǎn)達(dá)到) 第16頁/共115頁n n12)(iimvd說明任何無向圖中，各頂點(diǎn)度數(shù)之和等于邊數(shù)的兩倍。證明G中每條邊(包括環(huán))均有兩個(gè)端點(diǎn)，所以在計(jì)算G中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供2度，當(dāng)然，m條邊，共提供2m度

5、。 第17頁/共115頁否則當(dāng) , 0),(),( , 1),(GEvvvvjiji第18頁/共115頁n兩邊消去2t,得到結(jié)論。第19頁/共115頁定理1.2 設(shè)D為任意有向圖，Vv1,v2,vn，|E|m，則 n nn nn n111)()(,2)(iiiiiimvdvdmvd且第20頁/共115頁Vvvdm)(221)()(VvVvvdvd由于2m和2)(Vvvd，所以1)(Vvvd為偶數(shù)，但因V1中頂點(diǎn)度數(shù)為奇數(shù)， 所以|V1|必為偶數(shù)。第21頁/共115頁解。(2)為了建立一個(gè)圖模型，需要決定頂點(diǎn)和邊分別代表什么。(3)在一個(gè)圖模型中，邊經(jīng)常代表兩個(gè)頂點(diǎn)之間的關(guān)系。第22頁/共115

6、頁G,兩個(gè)面有公共邊界線時(shí)在相應(yīng)的兩頂間連一條邊， 于是|V(G)|是奇數(shù)，而且對每個(gè)頂點(diǎn)v,d(v)是奇數(shù),則所有的頂點(diǎn)的度數(shù)之和為奇數(shù)， 與握手定理矛盾。第23頁/共115頁特別地，若所得圖是簡單圖，則稱d是可簡單圖化的。類似地，設(shè)D為一個(gè)n階有向圖，Vv1,v2,vn，稱d(v1)，d(v2)，d(vn)為D的度數(shù)列，另外稱d+(v1)，d+(v2)，d+(vn)與d-(v1)，d-(v2)，d-(vn)分別為D的出度列和入度列。第24頁/共115頁按字母順序，度數(shù)列，出度列，入度列分別為5,3,3,34,0,2,11,3,1,2第25頁/共115頁n n1)2(mod0iid證明必要性

7、。由握手定理顯然得證。充分性。由已知條件可知，d中有偶數(shù)個(gè)奇數(shù)度點(diǎn)。奇數(shù)度點(diǎn)兩兩之間連一邊，剩余度用環(huán)來實(shí)現(xiàn)。5331第26頁/共115頁第27頁/共115頁第28頁/共115頁第29頁/共115頁(2) (5,4,3,2,2)可圖化，不可簡單圖化。若它可簡單圖化，設(shè)所得圖為G，則(G)max5,4,3,2,25，這與定理1.4矛盾。第30頁/共115頁因而(3)中序列也不可簡單圖化。(4) (d1,d2,dn)，d1d2dn1 且 為偶數(shù)。 n n1iid可圖化，不可簡單圖化。原因?第31頁/共115頁第32頁/共115頁 設(shè)G1，G2為兩個(gè)無向圖，若存在雙射函數(shù)f：V1V2，對于vi,vj

8、V1，(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)的，記做G1G2。說明(1) 類似地，可以定義兩個(gè)有向圖的同構(gòu)。(2) 圖的同構(gòu)關(guān)系看成全體圖集合上的二元關(guān)系。(3) 圖的同構(gòu)關(guān)系是等價(jià)關(guān)系。(4) 在圖同構(gòu)的意義下，圖的數(shù)學(xué)定義與圖形表示 是一一對應(yīng)的。 第33頁/共115頁彼得森(Petersen)圖第34頁/共115頁第35頁/共115頁n2)第36頁/共115頁。第37頁/共115頁1)/2K53階有向完全圖4階競賽圖第38頁/共115頁第39頁/共115頁第40頁/共115頁第41頁/共115

9、頁1第42頁/共115頁(1)為自補(bǔ)圖(2)和(3)互為補(bǔ)圖第43頁/共115頁,刪除e后，將e的兩個(gè)端點(diǎn)u,v用一個(gè)新的頂點(diǎn)w(或用u或v充當(dāng)w)代替，使w關(guān)聯(lián)除e外u,v關(guān)聯(lián)的所有邊，稱為邊e的收縮。(4)設(shè)u,vV(u,v可能相鄰，也可能不相鄰)，用G(u,v)(或G+(u,v)表示在u,v之間加一條邊(u,v)，稱為加新邊。說明 在收縮邊和加新邊過程中可能產(chǎn)生環(huán)和平行邊。第44頁/共115頁GGe5Ge1, e4Gv5Gv4, v5Ge5第45頁/共115頁若的所有頂點(diǎn)(除vi0與vij可能相同外)各異，所有邊也各異，則稱為初級(jí)通路或路徑，又若vi0vil，則稱為初級(jí)回路或圈。將長度為

10、奇數(shù)的圈稱為奇圈，長度為偶數(shù)的圈稱為偶圈。第46頁/共115頁n情況，即回路也是通路，又初級(jí)通路(回路)是簡單通路(回路)，但反之不真。第47頁/共115頁()表示法為混合表示法。第48頁/共115頁即在上存在vs到自身的回路Csk,在上刪除Csk上的一切邊及除vs外的一切頂點(diǎn)，得v0e1v1e2vkes+1elvl ,仍為vi到vj的通路，且長度至少比減少1。若還不滿足要求，則重復(fù)上述過程，由于G是有限圖，經(jīng)過有限步后，必得到vi到vj長度小于或等于n-1的通路。第49頁/共115頁第50頁/共115頁第51頁/共115頁如果只考慮起點(diǎn)(終點(diǎn))的差異，而不考慮順時(shí)針逆時(shí)針的差異，應(yīng)有3種不同

11、的圈，當(dāng)然它們都是同構(gòu)的，畫出圖來只有一個(gè)。第52頁/共115頁第53頁/共115頁第54頁/共115頁p( )。說明 若G為連通圖，則p(G)1。若G為非連通圖，則p(G)2。在所有的n階無向圖中，n階零圖是連通分支最多的， p(Nn)n。第55頁/共115頁nG連通分支， 則存在一個(gè)連通分支， 其頂點(diǎn)數(shù)小于等于k, 則在這個(gè)連通分支上最大度數(shù)不超過k-1, 矛盾第56頁/共115頁第57頁/共115頁d(u,v)+d(v,w)d(u,w)說明：在完全圖Kn(n2)中，任何兩個(gè)頂點(diǎn)之間的距離都是1。在n階零圖Nn(n2)中，任何兩個(gè)頂點(diǎn)之間的距離都為。第58頁/共115頁第59頁/共115頁

12、v2,v4,v3,v5都是點(diǎn)割集v3,v5都是割點(diǎn)v1與v6不在任何割集中。 實(shí)際上，點(diǎn)割集是若刪去它們就會(huì)使圖不連通的頂點(diǎn)的集合，而割點(diǎn)是若刪去此一頂點(diǎn)就會(huì)使圖不連通的頂點(diǎn)。第60頁/共115頁e6,e5,e2,e3,e1,e2,e3,e4,e1,e4,e1,e3,e2,e4都是割集，e6,e5是橋。 實(shí)際上，邊割集是若刪去它們就會(huì)使圖不連通的邊的集合，而割邊是若刪去此一邊就會(huì)使圖不連通的邊。第61頁/共115頁若 (G)k，則稱G是k-連通圖，k為非負(fù)整數(shù)。說明 (G)有時(shí)簡記為。上例中圖的點(diǎn)連通度為1，此圖為1-連通圖。K5的點(diǎn)連通度K4，所以K5是1-連通圖，2-連通圖，3-連通圖，4

13、-連通圖。若G是k-連通圖（k1）則在G中刪除任何k-1個(gè)頂點(diǎn)后，所得圖一定還是連通的。第62頁/共115頁Knn-1，Kn是r邊-連通圖，0rn-1。平凡圖G 由于E 則01，它只能是1邊-連通圖。第63頁/共115頁K4K3K2K1K=1 =2K2K0K0第64頁/共115頁(4)是1-連通圖，1邊-連通圖。(5)是1-連通圖，k邊-連通圖，k1,2。(6)是k-連通圖，k邊-連通圖，k1,2。(7)是0-連通圖，0邊-連通圖。(8)是0-連通圖，0邊-連通圖。點(diǎn)連通程度為(1)(2)(3)(6)(4)(5)(7)(8)。邊連通程度為(1)(2)(3)(5)(6)(4)(7)(8)。第65

14、頁/共115頁,vi,vj，若vivj，稱vi到vj長度最短的通路為vi到vj的短程線，短程線的長度為vi到vj的距離，記作d 。說明 與無向圖中頂點(diǎn)vi與vj之間的距離d(vi,vj)相比，d除無對稱性外，具有d(vi,vj)所具有的一切性質(zhì)。第66頁/共115頁強(qiáng)連通圖單向連通圖弱連通圖第67頁/共115頁n1nn1則1,2,n-1,n所圍成的回路經(jīng)過D中每個(gè)頂點(diǎn)至少一次。設(shè)D是n階有向圖，D是單向連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的通路。第68頁/共115頁w, u,w), (w,v)Gcu, v在Gc中連通。第69頁/共115頁第70頁/共115頁稱l+k為“極大路徑”，稱使用

15、此種方法證明問題的方法為“擴(kuò)大路徑法”。n有向圖中可以類似地討論，只須注意，在每步擴(kuò)大中保持有向邊方向的一致性。第71頁/共115頁第72頁/共115頁第73頁/共115頁14.5u,v在路徑，用“擴(kuò)大路徑法”擴(kuò)大這條路徑，設(shè)最后得到的“極大路徑”為lv0v1vl，易知l3。若v0與vl相鄰，則l(v0,vl)為長度大于或等于4的圈。否則，由于d(v0)(G)3，因而v0除與l上的v1相鄰?fù)?，還存在l上的頂點(diǎn)vk(k1)和vt(kt l )與v0相鄰，則v0v1vkvtv0為一個(gè)圈且長度大于或等于4第74頁/共115頁第75頁/共115頁第76頁/共115頁第77頁/共115頁r,s，r|V1

16、|，s|V2|。說明 n階零圖為二部圖。第78頁/共115頁K6的子圖K6的子圖K3,3K2,3K3,3K2,3第79頁/共115頁可知，v2iV1且v2i+1V2。又因?yàn)関0V1，所以vkV2，因而k為奇數(shù)，故C的長度為偶數(shù)。第80頁/共115頁vi,vjV1(vi,vj)e，設(shè)v0到vi,vj的短程線分別為i,j，則它們的長度d(v0,vi),d(v0,vj)都是偶數(shù)，于是ije中一定含奇圈，這與已知條件矛盾。類似可證，V2中也不存在相鄰的頂點(diǎn)，于是G為二部圖。第81頁/共115頁10000110000011001112M(G)第82頁/共115頁第83頁/共115頁第84頁/共115頁的

17、終點(diǎn)為不關(guān)聯(lián)為的始點(diǎn)為jijijiijevevevm101則稱(mij)nm為D的關(guān)聯(lián)矩陣，記作M(D)。1-1-1-00110000011-100011-M(D)第85頁/共115頁1101000100120000A第86頁/共115頁第87頁/共115頁第88頁/共115頁第89頁/共115頁第90頁/共115頁第91頁/共115頁第92頁/共115頁第93頁/共115頁第94頁/共115頁pij1 vi 可達(dá) vj0 否則稱(pij)nn為D的可達(dá)矩陣，記作P(D)，簡記為P。 1101101111110001P第95頁/共115頁第96頁/共115頁(3)稱以E1E2為邊集，以E1E2

18、中邊關(guān)聯(lián)的頂點(diǎn)組成的集合為頂點(diǎn)集的圖為G1與G2的交圖，記作G1G2。(4)稱以E1E2為邊集（為集合之間的對稱差運(yùn)算），以E1E2中邊關(guān)聯(lián)的頂點(diǎn)組成的集合為頂點(diǎn)集的圖為G1與G2的環(huán)和，記作G1G2。第97頁/共115頁G1G2(G1G2)-(G1G2)第98頁/共115頁第99頁/共115頁 Dijkstra算法能求一個(gè)頂點(diǎn)到另一頂點(diǎn)最短路徑。它是由Dijkstra于1959年提出的。實(shí)際它能出始點(diǎn)到其它所有頂點(diǎn)的最短路徑。 Dijkstra算法是一種標(biāo)號(hào)法：給賦權(quán)圖的每一個(gè)頂點(diǎn)記一個(gè)數(shù)，稱為頂點(diǎn)的標(biāo)號(hào)（臨時(shí)標(biāo)號(hào)，稱T標(biāo)號(hào)，或者固定標(biāo)號(hào)，稱為P標(biāo)號(hào)）。T標(biāo)號(hào)表示從始頂點(diǎn)到該標(biāo)點(diǎn)的最短路長的

19、上界；P標(biāo)號(hào)則是從始頂點(diǎn)到該頂點(diǎn)的最短路長。 Dijkstra算法步驟如下：第100頁/共115頁111(1)P()0(2,3, )T()jjjvd vvjnd vl 給給頂頂點(diǎn)點(diǎn) 標(biāo)標(biāo) 標(biāo)標(biāo)號(hào)號(hào)，給給頂頂點(diǎn)點(diǎn)標(biāo)標(biāo) 標(biāo)標(biāo)號(hào)號(hào)；000001(2)()()()jjjjjjj jjTd vlvTPTTvTd vd vlvT 在在所所有有 標(biāo)標(biāo)號(hào)號(hào)中中取取最最小小值值，譬譬如如，則則把把的的 標(biāo)標(biāo)號(hào)號(hào)改改為為 標(biāo)標(biāo)號(hào)號(hào)，并并重重新新計(jì)計(jì)算算具具有有 標(biāo)標(biāo)號(hào)號(hào)的的其其它它各各頂頂點(diǎn)點(diǎn)的的 標(biāo)標(biāo)號(hào)號(hào)：選選頂頂點(diǎn)點(diǎn) 的的 標(biāo)標(biāo)號(hào)號(hào)與與中中較較小小者者作作為為 的的新新的的 標(biāo)標(biāo)號(hào)號(hào)。(3)P重重復(fù)復(fù)上上述述步步驟驟，直直到到目目標(biāo)標(biāo)頂頂點(diǎn)點(diǎn)的的標(biāo)標(biāo)號(hào)號(hào)改改為為 標(biāo)標(biāo)號(hào)號(hào)。第101頁/共115頁v1v2v3v4v5v6v7v8v9v10v112817615129341369272149第102頁/共115頁v1v2v3v4v5v6v7v8v9v10v1128176151293413692721490281第103頁/共115頁v1v2v3v4v5v6v7v8v9v10v112817615129341369272149028101第104頁/共115頁v1v2v3v4v5v6v7v8v9v10v1128176151293413692721490831012第105頁/共115頁v1v