離散圖的通路回路

1、. -吳揚(yáng)揚(yáng)制-1 主要內(nèi)容：主要內(nèi)容：n圖同構(gòu)圖同構(gòu)n圖的通路回路圖的通路回路n基本概念基本概念n性質(zhì)性質(zhì)n一個(gè)應(yīng)用實(shí)例一個(gè)應(yīng)用實(shí)例 . -吳揚(yáng)揚(yáng)制-211.1 11.1 圖的基本概念圖的基本概念 5. 5. 圖的同構(gòu)圖的同構(gòu)n圖同構(gòu)：設(shè)圖同構(gòu)：設(shè)G G1 1=V=,G,G2 2=V=,若存在雙射函數(shù)若存在雙射函數(shù)f:Vf:V1 1VV2 2, , 使得使得 u,vu,v V V1 1,u,v,u,v E E1 1 iff f(u),f(v) iff f(u),f(v) E E2 2, ,且且u,vu,v與與f(u),f(v)f(u),f(v) 的重?cái)?shù)相等，則稱的重?cái)?shù)相等，則稱G G1 1與

2、與G G2 2同構(gòu)，記作同構(gòu)，記作G G1 1 G G2 2. .指指(u,v)(u,v)或或例例6 6：下列兩個(gè)圖同構(gòu)：下列兩個(gè)圖同構(gòu)：b bc cd de ea a5 54 42 21 13 3 有有f:a,b,c,d,e1,2,3,4,5,f:a,b,c,d,e1,2,3,4,5, f(a)=1,f(b)=3,f(c)=5,f(d)=2,f(e)=4 f(a)=1,f(b)=3,f(c)=5,f(d)=2,f(e)=4 顯然，顯然，f f雙射且（雙射且（a,b)a,b)與與(f(a),f(b)=(1,3)(f(a),f(b)=(1,3)重?cái)?shù)相等重?cái)?shù)相等,n同構(gòu)的必要條件：同構(gòu)的必要條件：

3、(2)|E(2)|E1 1|=|E|=|E2 2|;|;等。且度數(shù)相同的頂點(diǎn)數(shù)相, )vdeg()vdeg() 3(2i1iVviVvi(1)|V(1)|V1 1|=|V|=|V2 2|;|;P P223223 例題例題311.2 11.2 通路回路和連通性通路回路和連通性 1.1.通路和回路通路和回路(1)(1)n定義定義: :設(shè)設(shè)G=,vG=,v0 0,v,v1 1,v,vn n V,V,e e1 1,e,e2 2,e,en n E, E, 其中其中e ei i關(guān)聯(lián)于關(guān)聯(lián)于v vi-1i-1和和v vi i(i=1,2,n),(i=1,2,n), 稱稱v v0 0e e1 1v v1 1e

4、 e2 2een nv vn n為頂點(diǎn)為頂點(diǎn)v v0 0到頂點(diǎn)到頂點(diǎn)v vn n的的通路通路， 稱稱v v0 0和和v vn n分別為該通路的分別為該通路的起點(diǎn)起點(diǎn)和和終點(diǎn)終點(diǎn)， 稱通路上邊的數(shù)目為該通路的稱通路上邊的數(shù)目為該通路的長(zhǎng)度長(zhǎng)度， 若若v v0 0=v=vn n, ,則稱該通路為則稱該通路為回路回路。 若通路若通路( (回路回路) )的所有邊各不相同，則稱之為的所有邊各不相同，則稱之為簡(jiǎn)單通路簡(jiǎn)單通路( (回路回路) )。 若通路若通路( (回路回路) )的所有頂點(diǎn)各不相同，則稱之為的所有頂點(diǎn)各不相同，則稱之為基本通路基本通路( (回路回路) )。例例1 1：v v2 2c cv

5、v3 3d dv v4 4V V2 2c cv v3 3d dv v4 4e ev v2 2通路性質(zhì)連通定義連通性質(zhì)V V1 1V V2 2V V3 3V V5 5V V4 4a ab bc cd de ef fv v2 2c cv v3 3d dv v4 4v v4 4d dv v3 3c cv v2 2v v2 2c cv v3 3d dv v4 4e ev v2 2基本通基本通( (回回) )路一定是路一定是簡(jiǎn)單通簡(jiǎn)單通( (回回) )路路, ,反之不一定成立。反之不一定成立。V V1 1V V2 2V V3 3V V5 5V V4 4a ab bc cd de ef fg g. -吳揚(yáng)

6、揚(yáng)制-4n性質(zhì)性質(zhì): :n定理設(shè)定理設(shè)G=,|V|=n,u,vG=,|V|=n,u,v V,V,若存在從若存在從u u到到v v的通路，的通路， 則存在一條從則存在一條從u u到到v v的長(zhǎng)度不超過(guò)的長(zhǎng)度不超過(guò)n-1n-1的通路。的通路。證明證明: : 設(shè)設(shè)v v0 0e e1 1v v1 1e e2 2eem mv vm m為頂點(diǎn)為頂點(diǎn)u u到頂點(diǎn)到頂點(diǎn)v v的通路的通路(v(v0 0=u,v=u,vm m=v),=v),長(zhǎng)度為長(zhǎng)度為m,m, 若若mn-1,mn-1,則則v v0 0 e e1 1 v v1 1 e e2 2eem mv vm m為長(zhǎng)度不超過(guò)為長(zhǎng)度不超過(guò)n-1n-1的從的從u

7、 u到到v v的通路；的通路； 若若mn-1,mn-1,則則m+1n,vm+1n,v0 0e e1 1v v1 1e e2 2eem mv vm m中至少有一個(gè)頂點(diǎn)出現(xiàn)兩次以上，中至少有一個(gè)頂點(diǎn)出現(xiàn)兩次以上， 不妨設(shè)不妨設(shè)v vi i=v=vj j(0i(0i jm),jm),從上述通路中刪去從上述通路中刪去v vi i到到e ej j這段循環(huán)，這段循環(huán)，11.2 11.2 通路回路和連通性通路回路和連通性 1. 1. 通路和回路通路和回路(2)(2)v v0 0v v1 1v vi iv vi+1i+1v vj-1j-1v vj j則則v v0 0e e1 1v v1 1e e2 2vvi

8、ie ej+1j+1eem mv vm m是長(zhǎng)度為是長(zhǎng)度為m-(j-i)m-(j-i)的從的從u u到到v v的通路的通路, ,重復(fù)上述過(guò)程可得到重復(fù)上述過(guò)程可得到長(zhǎng)度不超過(guò)長(zhǎng)度不超過(guò)n-1n-1的的u u到到v v的通路。的通路。如例如例1 e e1 1e e2 2e ej je ej+1j+1e ei i. -吳揚(yáng)揚(yáng)制-511.2 11.2 通路回路和連通性通路回路和連通性 1. 1. 通路和回路通路和回路(3)(3)n推論設(shè)推論設(shè)G=,|V|=n,u,vG=,|V|=n,u,v V,V,若存在從若存在從u u到到v v的通路，的通路， 則存在一條從則存在一條從u u到到v v的長(zhǎng)度不超過(guò)

9、的長(zhǎng)度不超過(guò)n-1n-1的基本通路。的基本通路。n定理設(shè)定理設(shè)G=, |V|=n, uG=, |V|=n, u V, V, 若存在從若存在從u u到到u u的回路，的回路， 則存在一條從則存在一條從u u到到u u的長(zhǎng)度不超過(guò)的長(zhǎng)度不超過(guò)n n的回路。的回路。n推論設(shè)推論設(shè)G=, |V|=n, uG=, |V|=n, u V, V, 若存在從若存在從u u到到u u的回路，的回路， 則存在一條從則存在一條從u u到到u u的長(zhǎng)度不超過(guò)的長(zhǎng)度不超過(guò)n n的基本回路。的基本回路。 設(shè)設(shè)G=,|V|=n,G=,|V|=n,則則(1)(1)任何基本通路的長(zhǎng)度均不大于任何基本通路的長(zhǎng)度均不大于n-1n-

10、1。(2)(2)任何基本回路的長(zhǎng)度均不大于任何基本回路的長(zhǎng)度均不大于n n。對(duì)簡(jiǎn)單通路對(duì)簡(jiǎn)單通路( (回路回路) )是否也成立是否也成立, ,為什么為什么? ?. -吳揚(yáng)揚(yáng)制-611.2 11.2 通路回路和連通性通路回路和連通性 1. 1. 通路和回路通路和回路(4)(4)例例2 2：過(guò)河問(wèn)題：過(guò)河問(wèn)題( (P P225225).).限定：每次只能帶一樣限定：每次只能帶一樣“東西東西”； 不能把狗和羊、羊和菜、狗和羊和菜單獨(dú)留在一邊。不能把狗和羊、羊和菜、狗和羊和菜單獨(dú)留在一邊。解：解：VV原岸的狀態(tài)集原岸的狀態(tài)集,E,E狀態(tài)變化狀態(tài)變化. . M-Man,D-Dog,S-Sheep,C-C

11、abbage M-Man,D-Dog,S-Sheep,C-Cabbage； V=M,D,S,C,M,D,S,M,D,C,M,S,C,M,S,D,C,D,S,C, V=M,D,S,C,M,D,S,M,D,C,M,S,C,M,S,D,C,D,S,C, M,D,S,CM,D,S,C D,C D,CM,D,CM,D,C D D C CM,D,SM,D,SM,S,CM,S,C S S M,S M,S 從結(jié)點(diǎn)從結(jié)點(diǎn)M,D,S,CM,D,S,C到結(jié)點(diǎn)到結(jié)點(diǎn)的通路就是安全的運(yùn)送方案的通路就是安全的運(yùn)送方案. . MDSCD,CM,SD,C,MSDS,M,CM,S,D CS C,M,DM,S C,D MSCD7

12、11.2 11.2 通路回路和連通性通路回路和連通性 2. 2. 圖的連通性圖的連通性(1)(1)n定義：定義：n設(shè)設(shè)G=,|V|=n,u,vG=,|V|=n,u,v V,V,若存在若存在u u到到v v的通路，則稱的通路，則稱u u到到v v是是可達(dá)可達(dá)的。的。 如果如果u u可達(dá)可達(dá)v v，從，從u u到到v v最短通路的長(zhǎng)度稱為最短通路的長(zhǎng)度稱為u u到到v v的的距離距離，記作，記作d(ud(u，v)v)。 n設(shè)設(shè)G=G=為無(wú)向圖，若為無(wú)向圖，若G G的任何兩個(gè)頂點(diǎn)是可達(dá)的，則稱的任何兩個(gè)頂點(diǎn)是可達(dá)的，則稱G G是是連通圖連通圖。n設(shè)設(shè)G=G=為有向圖，若為有向圖，若 u,vu,v V

13、 V，(1) u(1) u和和v v相互可達(dá)，相互可達(dá)，則稱則稱G G是是強(qiáng)連通圖；強(qiáng)連通圖；(2)(2) u u和和v v至少有一個(gè)可達(dá)另一個(gè)，至少有一個(gè)可達(dá)另一個(gè)，則稱則稱G G是是單向連通圖；單向連通圖；(3) G(3) G的底圖是連通的，則稱的底圖是連通的，則稱G G是是弱連通圖。弱連通圖。例例3 3：（a)a)（b)b)(c)(c)(d)(d)(e)(e)n有向圖的極大強(qiáng)有向圖的極大強(qiáng)( (單向、弱單向、弱) )連通子圖，稱為強(qiáng)連通子圖，稱為強(qiáng)( (單向、弱單向、弱) )連通分圖連通分圖. .如如例例1 1中中連通性質(zhì)8n性質(zhì)性質(zhì)n無(wú)向圖無(wú)向圖G G，結(jié)點(diǎn)間的可達(dá)性是結(jié)點(diǎn)集合上的等價(jià)

14、關(guān)系，因此它決定了，結(jié)點(diǎn)間的可達(dá)性是結(jié)點(diǎn)集合上的等價(jià)關(guān)系，因此它決定了 結(jié)點(diǎn)集合的一個(gè)劃分。結(jié)點(diǎn)集合的一個(gè)劃分。每個(gè)劃分塊導(dǎo)出的子圖稱為每個(gè)劃分塊導(dǎo)出的子圖稱為G G的連通分圖的連通分圖，G G的連通分圖的個(gè)數(shù)記為的連通分圖的個(gè)數(shù)記為p(G)p(G)。如例如例3(b)3(b)n定理有向圖強(qiáng)連通定理有向圖強(qiáng)連通 iff iff 存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的回路。存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的回路。如例如例3,(3,(證明證明P P227227) )n設(shè)設(shè)G=G=為有向圖，定義為有向圖，定義V V上的二元關(guān)系上的二元關(guān)系R Ri i(i=1,2,3),(i=1,2,3), u,vu,v V V， uRu

15、R1 1v iff v iff 在在G G中中u u和和v v相互可達(dá)；相互可達(dá)； uR uR2 2v iff v iff 在在G G中中u u可達(dá)可達(dá)v v或或v v可達(dá)可達(dá)u u； uR uR3 3v iff v iff 在在G G的底圖中的底圖中u u可達(dá)可達(dá)v v， 則則(1)R(1)R1 1和和R R3 3是等價(jià)關(guān)系是等價(jià)關(guān)系;(2)R;(2)R2 2是相容關(guān)系，但不是等價(jià)關(guān)系。是相容關(guān)系，但不是等價(jià)關(guān)系。11.2 11.2 通路回路和連通性通路回路和連通性 2. 2. 圖的連通性圖的連通性(2)(2)R R1 1的等價(jià)類是什么子圖？的等價(jià)類是什么子圖？分析例分析例1 1. -吳揚(yáng)揚(yáng)

16、制-9 資源分配圖資源分配圖-有向圖的一個(gè)應(yīng)用實(shí)例有向圖的一個(gè)應(yīng)用實(shí)例(1)(1)n 資源分配問(wèn)題資源分配問(wèn)題n計(jì)算機(jī)系統(tǒng)中的程序共享系統(tǒng)資源，如磁盤、計(jì)算機(jī)系統(tǒng)中的程序共享系統(tǒng)資源，如磁盤、CPUCPU、主存貯器等，、主存貯器等，n當(dāng)一個(gè)程序要求使用某種資源，它需向操作系統(tǒng)發(fā)出請(qǐng)求。當(dāng)一個(gè)程序要求使用某種資源，它需向操作系統(tǒng)發(fā)出請(qǐng)求。n對(duì)資源的請(qǐng)求可能發(fā)生沖突，如程序?qū)Y源的請(qǐng)求可能發(fā)生沖突，如程序A A控制著資源控制著資源r r1 1，請(qǐng)求資源，請(qǐng)求資源r r2 2； 但程序但程序B B控制著資源控制著資源r r2 2，請(qǐng)求資源，請(qǐng)求資源r r1 1。這種情況稱為處于死鎖狀態(tài)。這種情況稱為

17、處于死鎖狀態(tài)。n資源分配圖資源分配圖 令令P Pt t=p=p1 1，p pm m 為計(jì)算機(jī)系統(tǒng)在時(shí)間為計(jì)算機(jī)系統(tǒng)在時(shí)間t t的程序集合，的程序集合， R Rt t=r=r1 1，r r2 2，r rn n 為計(jì)算機(jī)系統(tǒng)在時(shí)刻為計(jì)算機(jī)系統(tǒng)在時(shí)刻t t的資源集合，的資源集合， 資源分配圖資源分配圖G Gt t=R=E是有向圖，其中是有向圖，其中 rE iff E iff 程序程序p pk k已分配到資源已分配到資源r ri i且等待資源且等待資源r rj j。時(shí)刻時(shí)刻t t計(jì)算機(jī)系統(tǒng)處于死鎖狀態(tài)計(jì)算機(jī)系統(tǒng)處于死鎖狀態(tài) iff iff 資源分配圖資源分配圖G Gt t中包含強(qiáng)連通分圖。中包含強(qiáng)連通分圖。例. -吳揚(yáng)揚(yáng)制-10 資源分配圖資源分配圖-有向圖的一個(gè)應(yīng)用實(shí)例有向圖的一個(gè)應(yīng)用實(shí)例(2)(2)例例: :設(shè)設(shè)R Rt t=r=r1 1,r,r2 2,r,r3 3,r,r4 4 ，P Pt t=p=p1 1,p,p2 2,p,p3 3,p,p