離散數(shù)學(xué)圖的基本概論

離散數(shù)學(xué)圖的基本概論第一頁，共七十八頁，編輯于2023年，星期日計算機科學(xué)廣泛應(yīng)用于運籌學(xué)，信息論，控制論，網(wǎng)絡(luò)理論，化學(xué)生物學(xué)，物理學(xué)。原因在于這些學(xué)科的許多實際問題和理論問題可以概括為圖論。第八、九章介紹與計算機科學(xué)關(guān)系密切的圖論內(nèi)容及其在實際中的應(yīng)用。第二頁，共七十八頁，編輯于2023年，星期日8.1無向圖及有向圖稱{{a,b}|aAbB}為A與B的無序積，記作：A&B。習(xí)慣上，無序?qū)a,b}改記成(a,b)有序組(a,b)均用<a,b>無序積：設(shè)A，B為二集合，一、基本圖類及相關(guān)概念1.無向圖第三頁，共七十八頁，編輯于2023年，星期日無向圖：無向圖G是一個二元組<V,E>，其中(1)V是一個非空集–––頂點集V(G)，每個元素為頂點或結(jié)點；(2)E是無序積V&V的可重子集(元素可重復(fù)出現(xiàn))，E–––邊集E(G)，E中元素稱為無向邊。第四頁，共七十八頁，編輯于2023年，星期日v4實際中，圖是畫出來的，畫法：用小圓圈表示V中的每一個元素，如果(a,b)E，則在頂點a與b之間連線段。如：adcbe1e1e2e3e4e5e6e1e2e3e4e5e6v1v2v3v5第五頁，共七十八頁，編輯于2023年，星期日有向圖：有向圖D是一個二元組<V,E>，其中(1)V是非空集–––頂點集V(D)(2)E是笛卡爾積VV的可重子集，其元素為有向邊實際中，畫法同無向圖，只是要根據(jù)E中元素的次序，由第一元素用方向線段指向第二元素。2.有向圖第六頁，共七十八頁，編輯于2023年，星期日有限圖：V，E均為有窮集合零圖：E

平凡圖：E

且|V|=1(n,m)圖：|V|=n

且|E|=m頂與邊關(guān)聯(lián)：如果ek=(vi,vj)E，稱ek與vi關(guān)聯(lián)，或ek與vj關(guān)聯(lián)。3.相關(guān)概念第七頁，共七十八頁，編輯于2023年，星期日頂與頂相鄰：如果ek=(vi,vj)E，稱vi與vj相鄰；環(huán)：ek=<vi,vj>中，若vi=vj，則ek稱為環(huán)。邊與邊相鄰：如果ek和ei至少有一個公共頂點關(guān)聯(lián)，則稱ek與ei相鄰。若ek為有向邊，則稱vi鄰接到vj,vj鄰接于vi

。第八頁，共七十八頁，編輯于2023年，星期日孤立點：無邊關(guān)聯(lián)的頂點。平行邊：無向圖中，關(guān)聯(lián)一對結(jié)點的無向邊多于一條，平行邊的條數(shù)為重數(shù)；多重圖：包含平行邊的圖。有向圖中，關(guān)聯(lián)一對頂點的無向邊多于一條，且始、終點相同。簡單圖：既不包含平行邊又不包含環(huán)的圖。第九頁，共七十八頁，編輯于2023年，星期日度：(1)在無向圖G=<V,E>中，與頂點v(vV)關(guān)聯(lián)的邊的數(shù)目(每個環(huán)計算兩次)，記作：d(v)。二、度第十頁，共七十八頁，編輯于2023年，星期日(2)在有向圖D=<V,E>中，以頂點v(vV)作為始點的邊的數(shù)目，稱為該頂點的出度，記作：d+(v)；出度與入度之和，稱為頂點v的度：度是圖的性質(zhì)的重要判斷依據(jù)。d(v)=d+(v)+d–(v)以頂點v作為終點的邊的數(shù)目，稱為該頂點的入度，記作：d–(v)。第十一頁，共七十八頁，編輯于2023年，星期日最大度：

(G)=max{d(v)|vV}最小度：(G)=min{d(v)|vV}度與邊數(shù)的關(guān)系：在任何圖中，頂點度數(shù)的總和等于邊數(shù)之和的兩倍。握手定理的推論：任何圖中，度為奇數(shù)的頂點個數(shù)一定為偶數(shù)。(握手定理)第十二頁，共七十八頁，編輯于2023年，星期日出度與入度的關(guān)系：在有向圖中，各頂點的出度之和等于各頂點的入度之和。度數(shù)序列：設(shè)V={v1,v2,…,vn}為圖G的頂點集，稱(d(v1),d(v2),…,d(vn))為G的度數(shù)序列。度數(shù)序列之和必為偶數(shù)(?)。第十三頁，共七十八頁，編輯于2023年，星期日例8.1(3,3,2,3)，(5,2,3,1,4)能成為圖的度數(shù)序列嗎？為什么？解：由于這兩個序列中，奇數(shù)個數(shù)均為奇數(shù)，由握手定理知，它們不能成為圖的度數(shù)序列。第十四頁，共七十八頁，編輯于2023年，星期日例8.2

已知圖G中有10條邊，4個3度頂點，其余頂點的度數(shù)均小于等于2，問G中至少有多少個頂點？為什么？解：圖中邊數(shù)m=10，由握手定理知，G中各頂點度數(shù)之和為20，4個3度頂點占去12度，還剩8度，若其余全是2度頂點,則需要4個頂點來占用8度，所以G至少有8個頂點。第十五頁，共七十八頁，編輯于2023年，星期日正則圖：各頂點的度都相同的圖為正則圖；各頂點的度均為k的圖為k次正則圖。完全圖：(1)設(shè)G=<V,E>是n階的無向簡單圖，如果G中任何一個頂點都與其余n–1個頂點相鄰，則G為無向完全圖，記作：Kn。三、正則圖與完全圖第十六頁，共七十八頁，編輯于2023年，星期日(2)設(shè)D=<V,E>是n階的有向簡單圖，如果D中任意頂點u，vV(uv)，即有有向邊<u,v>，又有有向邊<v,u>，則稱D為n階有向完全圖。如：第十七頁，共七十八頁，編輯于2023年，星期日四、子圖與母圖：(1)G=<V,E>，G'=<V',E'>若V'V，E'E，則G是G'的母圖，

G'是G的子圖，記作：G'

G。(2)若G'G且

V'=V，則G'是G的生成子圖。第十八頁，共七十八頁，編輯于2023年，星期日(3)設(shè)V1V，且V1，以V1為頂點集，以2端點均在V1中的全體邊為邊集的G的子圖，稱為V1導(dǎo)出的導(dǎo)出子圖。(4)設(shè)E1E，且E1，以E1為頂點集，以E1中邊關(guān)聯(lián)的頂點的全體為頂點集的G的子圖，稱為E1導(dǎo)出的導(dǎo)出子圖。第十九頁，共七十八頁，編輯于2023年，星期日例8.3

列舉下圖的一些子圖、真子圖、生成子圖、導(dǎo)出子圖。e3e1e2e4e5v3v4v1v2解：自己對照定義做一做！(1)子圖：子圖的定義？舉例(2)真子圖：舉例(3)生成子圖：定義？舉例(4)導(dǎo)出子圖：定義？舉例第二十頁，共七十八頁，編輯于2023年，星期日補圖：給定一個圖G=<V,E>，以V為頂點集，以所有能使G成為完全圖的添加邊組成邊集的圖。記作：～G五、補圖如:(1)(2)第二十一頁，共七十八頁，編輯于2023年，星期日相對補圖：設(shè)G'G,如果另一個圖G''=<V'',E''>，滿足(1)E''=E–E'(2)V''中僅包含E''中的邊所關(guān)聯(lián)的結(jié)點。則G''是子圖G'相對于G的補圖。如：圖為的子圖，則圖(1)(2)(3)為(1)相對于(2)的補圖。第二十二頁，共七十八頁，編輯于2023年，星期日圖同構(gòu)：對于G=<V,E>，G'=<V',E'>，如果存在g:VV'

滿足：

(1)任意邊e=(vi,vj)E，當(dāng)且僅當(dāng)e'=(g(vi),g(vj))E'(2)e與e'的重數(shù)相同則說G

G'由于同構(gòu)圖頂點之間一一對應(yīng)，邊之間一一對應(yīng)，關(guān)聯(lián)關(guān)系對應(yīng)相同，所以可以看成同一個圖。六、同構(gòu)圖第二十三頁，共七十八頁，編輯于2023年，星期日例8.4

畫出4個頂點3條邊的所有可能非同構(gòu)的無向簡單圖。解：直觀上容易看出，下面三個圖是4個頂點3條邊的所有非同構(gòu)的無向簡單圖。第二十四頁，共七十八頁，編輯于2023年，星期日例8.5

畫出3個頂點2條邊的所有可能非同構(gòu)的有向簡單圖。解：3個頂點2條邊的無向簡單圖只有一個：由這個圖可派生出下列4個非同構(gòu)的有向簡單圖：課堂練習(xí)：畫出4個頂點4條邊的無向簡單圖。第二十五頁，共七十八頁，編輯于2023年，星期日

8.2通路、回路、圖的連通性通路與回路：給定圖G=<V,E>，設(shè)G中頂點與邊的交替序列

=v0

e1

v1

e2…el

vl

滿足：vi–1vi是ei的端點，(G為有向圖時,要求vi–1,vi分別為ei的始點、終點)，i=1,2,…,l，則為頂點v0到vl的通路。中邊的數(shù)目l稱為的長度。v0=vl時，稱為回路。一、通路與回路的概念第二十六頁，共七十八頁，編輯于2023年，星期日簡單通路：

=v0

e1

v1

e2…ek

vk為通路且邊e1

e2…ek互不相同，又稱之為跡，可簡用v0

v1…vk來表示。簡單回路(v0=vk)又稱為閉跡。初級通路或基本通路：

=v0

e1

v1

e2…ek

vk為通路且頂點v0

v1…vk互不相同。初級通路一定是簡單通路，但簡單通路不一定是一條初級通路?；净芈罚簐0

=vk。第二十七頁，共七十八頁，編輯于2023年，星期日例8.6

就下面兩圖列舉長度為5的通路，簡單通路，回路，簡單回路，再列舉長度為3的基本通路和回路。v1e1e4v2v3v4v5e3e5e2e7e6(1)(2)v5v1e2e5v2v3v4e1e7e3e8e6e4解：試對照定義，自己做一做！如：第二十八頁，共七十八頁，編輯于2023年，星期日v1(1)中v1e1v2e2v5e3v1e1v2e4v3為v1到v3的通路；v1e1v2e4v3e5v4e7v5e3v1為v1到v1的一條簡單回路；v1e1v2e4v3e5v4e6v2e2v5為v1到v5的一條簡單通路。e1e4v2v3v4v5e3e5e2e7e6(1)第二十九頁，共七十八頁，編輯于2023年，星期日(2)中v1e2v2e5v3e7v4v1到v4的長度為了的基本通路；v1e2v2e3v5e1v1是v1到v1的長度為了的基本回路。(2)v5v1e2e5v2v3v4e1e7e3e8e6e4第三十頁，共七十八頁，編輯于2023年，星期日二、通路與回路的性質(zhì)：(1)在一個n階圖中，如果從頂點vi到vj(vivj)存在通路，則從vi到vj存在長度小于或等于n–1的通路。如果L>n–1，則此通路的頂點數(shù)L+1>n，從而必有頂點vs，它在序列中不止出現(xiàn)一次，即有序列vi…vs…vs…vj

。證明：設(shè)vi…vk…vj為vi到vj的長度為L的一條通路，則序列中必有L+1個頂點。在路中去掉vs到vs的這些邊，至少去掉一條邊后仍是vi到vj的一條通路。此通路比原來如此重復(fù)下去，必可得到一條從vi到vj的不多于n–1條邊的通路。通路的長度至少少1。第三十一頁，共七十八頁，編輯于2023年，星期日(2)在n階圖中，如果從vi到vj(vivj)存在通路，則必存在從vi到vj的長度小于等于

n–1的基本通路。(3)在n階圖中，如果存在從vi到自身的回路，則從vi到自身存在長度等于n的回路。(4)在n階圖中，如果從vi到自身存在一條簡單回路，則從vi到自身存在長度等于n的初級回路。第三十二頁，共七十八頁，編輯于2023年，星期日兩頂點連通：u,v為無向圖G的兩個頂點，u到v存在一條通路。連通圖：G中任何兩個頂點是連通的；否則是分離圖。三、圖的連通性第三十三頁，共七十八頁，編輯于2023年，星期日連通性的性質(zhì)：無向圖中頂點之間的連通關(guān)系是頂點集V上的等價關(guān)系。(1)自反性：由于規(guī)定任何頂點到自身總是連通的；證明：(2)對稱性：無向圖中頂點之間的連通是相互的；(3)傳遞性：由連通性的定義可知。第三十四頁，共七十八頁，編輯于2023年，星期日連通分支：無向圖G中每個劃分塊稱為G的一個連通分支，p(G)表示連通分支的個數(shù)。p(G)=1為連通圖。第三十五頁，共七十八頁，編輯于2023年，星期日點割集：無向圖G=<V,E>為連通圖，如果V'V，且在G中刪除V'中所有頂點(包括與該頂點關(guān)聯(lián)的邊)后所得子圖是不連通的或是平凡圖，而刪除V'中任何真子集中的頂點時，所得子圖仍連通，則V'是G的點割集。

如果點割集中只有一個頂點，該點為割點。四、連通圖的連通度第三十六頁，共七十八頁，編輯于2023年，星期日點連通度：G為無向連通圖，記k(G)=min{|V'|V'是G的點割集}，稱k(G)為G的點連通度。由定義知，點連通度即使G不連通的需刪除頂點的最少數(shù)目。完全圖Kn的連通度k(G)=n–1。存在割點的連通圖連通度為1，分離圖的連通度為0；第三十七頁，共七十八頁，編輯于2023年，星期日邊割集：設(shè)無向圖G=<V,E>連通，邊集E'E，在G中刪除E'中所有邊后所得子圖不連通，而刪除E'中的任何子集中的邊后，所得子圖仍連通，則E'為G的邊割集。如果邊割集中只有一邊時，該邊為割邊(或橋)第三十八頁，共七十八頁，編輯于2023年，星期日邊連通度：設(shè)G為無向連通圖，記(G)=min{|E'|E'是G的邊割集}，(G)為G的邊連通度。連通度的性質(zhì)：k(G)(G)(G)第三十九頁，共七十八頁，編輯于2023年，星期日五、有向圖的連通性：(1)如果有向圖D=<V,E>中所有有向邊的方向去掉后所得圖為無向連通圖，則說D為弱連通圖。(2)u,vV，如果存在u到v的一條通路，則說u可達v。(3)弱連通圖<V,E>中，任何一對頂點之間，至少有一頂點可達另一個頂點，則<V,E>是單向連通的；任何兩個頂點之間互相可達，稱<V,E>強連通。第四十頁，共七十八頁，編輯于2023年，星期日有向連通圖的性質(zhì)：(1)強連通一定單向連通，單向連通一定弱連通。反過來都不成立。第四十一頁，共七十八頁，編輯于2023年，星期日(2)有向圖D強連通，當(dāng)且僅當(dāng)D中存在一條回路，它至少經(jīng)過每個頂點一次。(充分性)如果D中存在回路C，它經(jīng)過D中的每個頂點至少一次，則D中的任意兩個頂點都在回路中，所以，D中任意兩個頂點都是可達的，因而D是強連通的。證明：第四十二頁，共七十八頁，編輯于2023年，星期日因為vi可達vi+1,i=1,2,…，n–1，讓這些通路首尾相連，(2)有向圖D強連通，當(dāng)且僅當(dāng)D中存在一條回路，它至少經(jīng)過每個頂點一次。(必要性)D是強連通的，則D中任何兩個頂點都是可達的。則得一回路。顯然每個頂點在回路中至少出現(xiàn)一次。證明：所以vi到vi+1存在通路，不妨設(shè)D中的頂點為v1,v2,…,vn，且vn到v1也存在通路，第四十三頁，共七十八頁，編輯于2023年，星期日8.3圖的矩陣表示鄰接矩陣：設(shè)G=<V,E>是一個簡單圖，它有n個頂點，V={v1,v2,…,vn}，令aij=1<vi,vj>E(或(vi,vj)E)0<vi,vj>E(或(vi,vj)E)稱A(G)=(aij)為G的鄰接矩陣。一、鄰接矩陣及其性質(zhì)第四十四頁，共七十八頁，編輯于2023年，星期日鄰接矩陣的特性：在無向圖中：(1)鄰接陣是對稱陣；(2)同一行或者同一列的元素和為對應(yīng)頂點的度數(shù)(3)矩陣中所有元素的和為邊數(shù)的2倍第四十五頁，共七十八頁，編輯于2023年，星期日在有向圖中：(1)同一行的元素和為對應(yīng)頂點的出度(2)同一列的元素和為對應(yīng)頂點的入度(3)aij=2m(邊的數(shù)目)第四十六頁，共七十八頁，編輯于2023年，星期日鄰接矩陣可推廣到多重圖或帶權(quán)圖，這時令aij為vi到vj的邊的重數(shù)或邊上的權(quán)值W(vi,vj)。鄰接陣多用于有向圖。第四十七頁，共七十八頁，編輯于2023年，星期日關(guān)聯(lián)矩陣：(1)設(shè)G=<V,E>為(n,m)無向圖,V={v1,v2,…,vn},E={e1,e2,…,em},令：mij=10稱M(G)=(mij)nxm為G的關(guān)聯(lián)矩陣。vi

關(guān)聯(lián)ejvi

不關(guān)聯(lián)ej二、關(guān)聯(lián)矩陣及其性質(zhì)第四十八頁，共七十八頁，編輯于2023年，星期日(2)設(shè)D=<V,E>是有向圖且無環(huán)，令：mij=10則稱M(D)=(mij)nxm為D的關(guān)聯(lián)矩陣。–1D中vi是ej的始點vi

與ej不關(guān)聯(lián)vi

是ej的終點第四十九頁，共七十八頁，編輯于2023年，星期日無向圖的關(guān)聯(lián)矩陣的性質(zhì)：(握手定理)第五十頁，共七十八頁，編輯于2023年，星期日有向圖的關(guān)聯(lián)矩陣的性質(zhì)：由mij的定義知第五十一頁，共七十八頁，編輯于2023年，星期日通路數(shù)與回路數(shù)的矩陣算法：(1)設(shè)A是有向圖D的鄰接矩陣，V={v1,v2,…,vn}，Al(l1)中元素aij(l)為vi到vj長度為l的通路數(shù)通路總數(shù)回路數(shù)三、應(yīng)用1.求通路數(shù)與回路數(shù)第五十二頁，共七十八頁，編輯于2023年，星期日(2)設(shè)A是有向圖D的鄰接矩陣，B1=A，B2=A+A2,……，Br=A+A2+…+Ar，則Br中元素bij(r)

為D中vi到vj長度小于等于r的通路數(shù)，2.求可達矩陣第五十三頁，共七十八頁，編輯于2023年，星期日可達矩陣：設(shè)D=<V,E>為一有向圖，V={v1,v2,…,vn}，令pij=10ijpii=1i=1,2,…,n

稱(pij)nxn

為D的可達矩陣。vi

可達vj否則第五十四頁，共七十八頁，編輯于2023年，星期日例.求下圖的可達矩陣，判斷它是否為強連通圖？V1V4V2V3V5解：1.寫出鄰接矩陣第五十五頁，共七十八頁，編輯于2023年，星期日2.計算A2,A3,A4,A5.第五十六頁，共七十八頁，編輯于2023年，星期日3.計算B=A+A2+A3+A4+A5,并求出第五十七頁，共七十八頁，編輯于2023年，星期日可達矩陣的求法：由鄰接矩陣A計算A2,A+A2,……A+A2+…+A(n–1)=B=(bij(n–1))nn

pij=1bij(n–1)

00bij(n–1)

=0則i

jpii=1即得可達矩陣P(D)=(pij)nxn

第五十八頁，共七十八頁，編輯于2023年，星期日8.4最短路徑問題帶權(quán)圖：對于有向圖或無向圖的每條邊附加一個實數(shù)w(e)，則得帶權(quán)圖。如果G1是帶權(quán)圖G的子圖，稱w(e)為邊e上的權(quán)(當(dāng)e=<vi,vj>時，權(quán)記作wij)，記作：G=<V,E,W>一、帶權(quán)圖及其最短路徑問題第五十九頁，共七十八頁，編輯于2023年，星期日G=<V,E,W>為帶權(quán)圖，且G中各邊帶的權(quán)均大于等于0，從頂點u到頂點v的所有通路中求帶權(quán)最小的通路問題，稱為最短路徑問題。最短路徑問題：如果v1v2…vn–1vn是v1到vn的最短路徑，則v1v2…vn–1也必然是v1從到vn–1的最短路徑。求最短路徑的標號法的基本思想：第六十頁，共七十八頁，編輯于2023年，星期日標號法：(1)符號說明(i)li(r)*為頂點v1到頂點vi最短路徑的權(quán)(ii)lj(r)為v1到vj最短路徑權(quán)的上界，如果vj獲得lj(r)

，稱vj在第r步獲得t標號lj(r)(r0)如果頂點vi獲得了標號li(r)*，稱vi在第r步獲得p標號li(r)*(iii)Pr={v|v已獲得p標號}，稱之為第r步通過集(r0)(iv)Tr=V–Pr

稱之為第r步未通過集(r0)二、求最短路徑問題的標號法第六十一頁，共七十八頁，編輯于2023年，星期日(2)算法：開始，r0，v1獲p標號：l1(0)*=0，P0={v1}，T0=V–{v1}，vj(j1)的t標號：lj(0)=w1j=w1j

0v1與vj相鄰v1與vj不相鄰第六十二頁，共七十八頁，編輯于2023年，星期日修改通過集和未通過集：Pr=Pr–1∪{vi}，

Tr=Tr–1∪{vi}，step1.求下一個p標號頂點設(shè)lj(r)*=min{lj(r–1)}，r1。vjTr–1頂點vi處，表明vi獲得p標號。查Tr：若Tr=，則算法結(jié)束，否則轉(zhuǎn)step2將lj(r)*標在相應(yīng)第六十三頁，共七十八頁，編輯于2023年，星期日step2.修改Tr中各頂點的t標號lj(r)=min{lj(r–1),li(r)*+wij}，li(r)*是剛剛獲得p標號頂點的p標號。令r

r+1，轉(zhuǎn)step1。第六十四頁，共七十八頁，編輯于2023年，星期日例8.7

求下圖中頂點v0與v5之間的最短路徑v0v2v1v4v3v5121475326第六十五頁，共七十八頁，編輯于2023年，星期日解：利用標號法算法解此題開始，r0，v0獲p標號：

l0(0)*=0l1(0)=w01=1通過集P0={v0}，未通過集T0={v1，

v2，v3，

v4，v5}，l2(0)=w02=4l4(0)=

=l5(0)

l3(0)=w03=未通過集的t標號：v0v2v1v4v3v5121475326第六十六頁，共七十八頁，編輯于2023年，星期日第一步：r=1，計算=l1(1)*=1，所以i=1，P1={v0,v1}，T1={v2,v3,v4,v5}修改未通過集的t標號：l2(1)=min{l2(0),l1(1)*+w12}=min{4,3}=3l3(1)=min{l3(0),l1(1)*+w13}=min{,8}=8l4(1)=min{l4(0),l1(1)*+w14}=6l5(1)=min{l5(0),l1(1)*+w15}=vi獲p標號l1(1)*，修改通過集與未通過集:第六十七頁，共七十八頁，編輯于2023年，星期日修改通過集與未通過集

P2={v0,v1,

v2}，T2={v3,v4,v5}修改未通過集的t標號：l3(2)=min{l3(1),l2(2)*+w23}=min{8,3+}=8l4(2)=min{l4(1),l2(2)*+w24}=min{6,3+1}=4l5(2)=min{l5(0),l2(2)*+w25}=min{,3+}=第六十八頁，共七十八頁，編輯于2023年，星期日修改通過集與未通過集

P3={v0,v1,

v2,v4},T3={v5,v3}修改未通過集的t標號：l3(3)=min{l3(2),l4(3)*+w43}=min{8,4+3}=7l5(3)=min{l5(2),l4(3)*+w45}=min{,4+