圖的基本概念

第14章圖的基本概念離散數(shù)學(xué)中國(guó)地質(zhì)大學(xué)本科生課程本章內(nèi)容14.1 圖14.2 通路與回路14.3 圖的連通性14.4 圖的矩陣表示14.5 圖的運(yùn)算

基本要求

作業(yè)整理課件14.1圖的基本概念圖的定義圖的一些概念和規(guī)定簡(jiǎn)單圖和多重圖頂點(diǎn)的度數(shù)與握手定理圖的同構(gòu)完全圖與正則圖子圖與補(bǔ)圖整理課件無(wú)序積與多重集合

元素可以重復(fù)出現(xiàn)的集合稱為多重集合或者多重集，某元素重復(fù)出現(xiàn)的次數(shù)稱為該元素的重復(fù)度。 例如在多重集合{a,a,b,b,b,c,d}中，

a,b,c,d的重復(fù)度分別為2,3,1,1。整理課件定義14.1一個(gè)無(wú)向圖是一個(gè)有序的二元組<V，E>,記作G，其中 （1）V≠稱為頂點(diǎn)集，其元素稱為頂點(diǎn)或結(jié)點(diǎn)。 （2）E稱為邊集，它是無(wú)序積V&V的多重子集，其元素稱為無(wú)向邊，簡(jiǎn)稱邊。定義14.2一個(gè)有向圖是一個(gè)有序的二元組<V，E>，記作D，其中 （1）V≠稱為頂點(diǎn)集，其元素稱為頂點(diǎn)或結(jié)點(diǎn)。 （2）E為邊集，它是笛卡兒積V×V的多重子集，其元素稱為有向邊，簡(jiǎn)稱邊。無(wú)向圖和有向圖說(shuō)明可以用圖形表示圖，即用小圓圈（或?qū)嵭狞c(diǎn)）表示頂點(diǎn)，用頂點(diǎn)之間的連線表示無(wú)向邊，用有方向的連線表示有向邊。整理課件例14.1例14.1(1)給定無(wú)向圖G＝<V,E>，其中V＝{v1,v2,v3,v4,v5}，

E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}.(2)給定有向圖D=<V,E>，其中V＝{a,b,c,d}，

E＝{<a,a>,<a,b>,<a,b>,<a,d>,<c,d>,<d,c>,<c,b>}。

畫出G與D的圖形。整理課件圖的一些概念和規(guī)定G表示無(wú)向圖，但有時(shí)用G泛指圖(無(wú)向的或有向的)。D只能表示有向圖。V(G)，E(G)分別表示G的頂點(diǎn)集和邊集。若|V(G)|＝n，則稱G為n階圖。若|V(G)|與|E(G)|均為有限數(shù)，則稱G為有限圖。若邊集E(G)＝，則稱G為零圖，此時(shí)，又若G為n階圖，則稱G為n階零圖，記作Nn，特別地，稱N1為平凡圖。在圖的定義中規(guī)定頂點(diǎn)集V為非空集，但在圖的運(yùn)算中可能產(chǎn)生頂點(diǎn)集為空集的運(yùn)算結(jié)果，為此規(guī)定頂點(diǎn)集為空集的圖為空?qǐng)D，并將空?qǐng)D記為。整理課件標(biāo)定圖與非標(biāo)定圖、基圖將圖的集合定義轉(zhuǎn)化成圖形表示之后，常用ek表示無(wú)向邊(vi,vj)（或有向邊<vi,vj>），并稱頂點(diǎn)或邊用字母標(biāo)定的圖為標(biāo)定圖，否則稱為非標(biāo)定圖。將有向圖各有向邊均改成無(wú)向邊后的無(wú)向圖稱為原來(lái)圖的基圖。易知標(biāo)定圖與非標(biāo)定圖是可以相互轉(zhuǎn)化的，任何無(wú)向圖G的各邊均加上箭頭就可以得到以G為基圖的有向圖。整理課件關(guān)聯(lián)與關(guān)聯(lián)次數(shù)、環(huán)、孤立點(diǎn)設(shè)G＝<V,E>為無(wú)向圖，ek＝(vi,vj)∈E， 稱vi,vj為ek的端點(diǎn)，ek與vi或ek與vj是彼此相關(guān)聯(lián)的。 若vi≠vj，則稱ek與vi或ek與vj的關(guān)聯(lián)次數(shù)為1。 若vi＝vj，則稱ek與vi的關(guān)聯(lián)次數(shù)為2，并稱ek為環(huán)。

若端點(diǎn)vl不與邊ek關(guān)聯(lián)，則稱ek與vl的關(guān)聯(lián)次數(shù)為0。設(shè)D＝<V,E>為有向圖，ek＝<vi,vj>∈E， 稱vi,vj為ek的端點(diǎn)。 若vi＝vj，則稱ek為D中的環(huán)。無(wú)論在無(wú)向圖中還是在有向圖中，無(wú)邊關(guān)聯(lián)的頂點(diǎn)均稱為孤立點(diǎn)。整理課件相鄰與鄰接設(shè)無(wú)向圖G＝<V，E>，vi，vj∈V，ek，el∈E。 若et∈E，使得et＝(vi，vj)，則稱vi與vj是相鄰的。 若ek與el至少有一個(gè)公共端點(diǎn)，則稱ek與el是相鄰的。設(shè)有向圖D＝<V，E>，vi，vj∈V，ek，el∈E。 若et∈E，使得et＝<vi，vj>，則稱vi為et的始點(diǎn)，vj為et的終點(diǎn)，并稱vi鄰接到vj，vj鄰接于vi。 若ek的終點(diǎn)為el的始點(diǎn)，則稱ek與el相鄰。整理課件鄰域設(shè)無(wú)向圖G＝<V，E>，v∈V，

稱{u|u∈V∧(u,v)∈E∧u≠v}為v的鄰域，記做NG(v)。稱NG(v)∪{v}為v的閉鄰域，記做NG(v)。稱{e|e∈E∧e與v相關(guān)聯(lián)}為v的關(guān)聯(lián)集，記做IG(v)。設(shè)有向圖D＝<V，E>，v∈V，

稱{u|u∈V∧<v,u>∈E∧u≠v}為v的后繼元集，記做Г+D(v)。 稱{u|u∈V∧<u,v>∈E∧u≠v}為v的先驅(qū)元集，記做Г-D(v)。

稱Г+D(v)∪Г-D(v)為v的鄰域，記做ND(v)。

稱ND(v)∪{v}為v的閉鄰域，記做ND(v)。整理課件舉例NG(v1)＝Г+D(d)＝{v2，v5}NG(v1)＝{v1，v2，v5}IG(v1)＝{e1，e2，e3}{c}Г-D(d)＝{a，c}ND(d)＝{a，c}ND(d)＝{a，c，d}整理課件簡(jiǎn)單圖與多重圖定義14.3在無(wú)向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的無(wú)向邊如果多于1條，則稱這些邊為平行邊，平行邊的條數(shù)稱為重?cái)?shù)。 在有向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的有向邊如果多于1條，并且這些邊的始點(diǎn)和終點(diǎn)相同(也就是它們的方向相同)，則稱這些邊為平行邊。 含平行邊的圖稱為多重圖。

既不含平行邊也不含環(huán)的圖稱為簡(jiǎn)單圖。例如：在圖14.1中， (a)中e5與e6是平行邊， (b)中e2與e3是平行邊，但e6與e7不是平行邊。 (a)和(b)兩個(gè)圖都不是簡(jiǎn)單圖。整理課件頂點(diǎn)的度數(shù)定義14.4設(shè)G＝<V,E>為一無(wú)向圖，v∈V，稱v作為邊的端點(diǎn)次數(shù)之和為v的度數(shù)，簡(jiǎn)稱為度，記做dG(v)。 在不發(fā)生混淆時(shí)，簡(jiǎn)記為d(v)。 設(shè)D＝<V，E>為有向圖，v∈V， 稱v作為邊的始點(diǎn)次數(shù)之和為v的出度，記做d+D(v)，簡(jiǎn)記作d+(v)。 稱v作為邊的終點(diǎn)次數(shù)之和為v的入度，記做d-D(v)，簡(jiǎn)記作d-(v)。

稱d+(v)+d-(v)為v的度數(shù)，記做d(v)。整理課件圖的度數(shù)的相關(guān)概念在無(wú)向圖G中，

最大度 △(G)＝max{d(v)|v∈V(G)}

最小度

δ(G)＝min{d(v)|v∈V(G)}在有向圖D中，

最大出度 △+(D)＝max{d+(v)|v∈V(D)}

最小出度

δ+(D)＝min{d+(v)|v∈V(D)}

最大入度

△-(D)＝max{d-(v)|v∈V(D)}

最小入度

δ-(D)＝min{d-(v)|v∈V(D)}稱度數(shù)為1的頂點(diǎn)為懸掛頂點(diǎn)，與它關(guān)聯(lián)的邊稱為懸掛邊。度為偶數(shù)(奇數(shù))的頂點(diǎn)稱為偶度(奇度)頂點(diǎn)。整理課件圖的度數(shù)舉例d(v1)＝4(注意，環(huán)提供2度)，△＝4，δ＝1，v4是懸掛頂點(diǎn)，e7是懸掛邊。d+(a)＝4，d-(a)＝1

(環(huán)e1提供出度1，提供入度1)，d(a)＝4+1＝5。△＝5，δ＝3，△+＝4(在a點(diǎn)達(dá)到)δ+＝0(在b點(diǎn)達(dá)到)△-＝3(在b點(diǎn)達(dá)到)δ-＝1(在a和c點(diǎn)達(dá)到)整理課件握手定理定理14.1設(shè)G＝<V,E>為任意無(wú)向圖，V＝{v1,v2,…,vn}， |E|＝m，則說(shuō)明 任何無(wú)向圖中，各頂點(diǎn)度數(shù)之和等于邊數(shù)的兩倍。證明 G中每條邊(包括環(huán))均有兩個(gè)端點(diǎn)， 所以在計(jì)算G中各頂點(diǎn)度數(shù)之和時(shí)， 每條邊均提供2度，當(dāng)然，m條邊，共提供2m度。定理14.2設(shè)D＝<V,E>為任意有向圖，V＝{v1,v2,…,vn}， |E|＝m，則整理課件握手定理的推論推論 任何圖(無(wú)向的或有向的)中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù)。證明 設(shè)G＝<V，E>為任意一圖，令

V1＝{v|v∈V∧d(v)為奇數(shù)}

V2＝{v|v∈V∧d(v)為偶數(shù)} 則V1∪V2＝V，V1∩V2＝，由握手定理可知由于2m和，所以為偶數(shù)，但因V1中頂點(diǎn)度數(shù)為奇數(shù)，所以|V1|必為偶數(shù)。整理課件問題研究問題：在一個(gè)部門的25個(gè)人中間，由于意見不同，是否可能每個(gè)人恰好與其他5個(gè)人意見一致？解答：不可能。考慮一個(gè)圖，其中頂點(diǎn)代表人，如果兩個(gè)人意見相同，可用邊連接，所以每個(gè)頂點(diǎn)都是奇數(shù)度。存在奇數(shù)個(gè)度數(shù)為奇數(shù)的圖，這是不可能的。說(shuō)明： (1)很多離散問題可以用圖模型求解。 (2)為了建立一個(gè)圖模型，需要決定頂點(diǎn)和邊分別代表什么。 (3)在一個(gè)圖模型中，邊經(jīng)常代表兩個(gè)頂點(diǎn)之間的關(guān)系。整理課件度數(shù)列設(shè)G＝<V,E>為一個(gè)n階無(wú)向圖，V＝{v1,v2,…,vn}，稱d(v1)，d(v2)，…，d(vn)為G的度數(shù)列。對(duì)于頂點(diǎn)標(biāo)定的無(wú)向圖，它的度數(shù)列是唯一的。反之，對(duì)于給定的非負(fù)整數(shù)列d＝{d1,d2,…,dn}，若存在V＝{v1,v2,…,vn}為頂點(diǎn)集的n階無(wú)向圖G，使得d(vi)＝di，則稱d是可圖化的。特別地，若所得圖是簡(jiǎn)單圖，則稱d是可簡(jiǎn)單圖化的。類似地，設(shè)D＝<V,E>為一個(gè)n階有向圖，V＝{v1,v2,…,vn}，稱d(v1)，d(v2)，…，d(vn)為D的度數(shù)列，另外稱d+(v1)，d+(v2)，…，d+(vn)與d-(v1)，d-(v2)，…，d-(vn)分別為D的出度列和入度列。整理課件度數(shù)列舉例按頂點(diǎn)的標(biāo)定順序，度數(shù)列為 4,4,2,1,3。按字母順序，度數(shù)列，出度列，入度列分別為 5,3,3,3 4,0,2,1 1,3,1,2整理課件可圖化的充要條件定理14.3設(shè)非負(fù)整數(shù)列d＝(d1，d2，…，dn)，則d是可圖化的當(dāng)且僅當(dāng)證明 必要性。由握手定理顯然得證。

充分性。由已知條件可知，d中有偶數(shù)個(gè)奇數(shù)度點(diǎn)。 奇數(shù)度點(diǎn)兩兩之間連一邊，剩余度用環(huán)來(lái)實(shí)現(xiàn)。5331整理課件定理14.3的證明由握手定理可知必然性顯然。下面證明充分性。由已知條件可知，d中有2k(0≤k≤[n/2])個(gè)奇數(shù)，不妨設(shè)它們?yōu)閐1，d2，…，dk，dk+1，dk+2，…，d2k

?？捎枚喾N方法做出n階無(wú)向圖G＝<V,E>，V＝{v1,v2,…vn}。比如邊集如下產(chǎn)生：在頂點(diǎn)vr與vr+k之間連邊，r＝1,2,…,k。若di為偶數(shù)，令di＝di，若di為奇數(shù)，令di＝di-1，得d＝(d1，d2，…，dn)，則di均為偶數(shù)。再在vi處做出di/2條環(huán),i＝1,…,n，將所得各邊集合在一起組成E，則G的度數(shù)列為d。其實(shí)，di為偶數(shù)時(shí)，d(vi)＝2·di/2＝2·di/2＝di，當(dāng)di為奇數(shù)時(shí)，d(vi)＝1+2·di/2＝1+di＝1+di-1＝di，這就證明了d是可圖化的。整理課件可圖化舉例由定理14.3立即可知， (3,3,2,1)，(3,2,2,1,1)等是不可圖化的， (3,3,2,2)，(3,2,2,2,1)等是可圖化的。整理課件定理14.4定理14.4設(shè)G為任意n階無(wú)向簡(jiǎn)單圖，則△(G)≤n-1。證明 因?yàn)镚既無(wú)平行邊也無(wú)環(huán)， 所以G中任何頂點(diǎn)v至多與其余的n-1個(gè)頂點(diǎn)均相鄰， 于是d(v)≤n-1，由于v的任意性，所以△(G)≤n-1。例14.2判斷下列各非負(fù)整數(shù)列哪些是可圖化的？哪些是可簡(jiǎn)單圖化的？ (1)(5,5,4,4,2,1) 不可圖化。(2)(5,4,3,2,2)

可圖化，不可簡(jiǎn)單圖化。若它可簡(jiǎn)單圖化， 設(shè)所得圖為G，則(G)＝max{5,4,3,2,2}＝5， 這與定理14.4矛盾。整理課件例14.2(3)(3,3,3,1) 可圖化，不可簡(jiǎn)單圖化。假設(shè)該序列可以簡(jiǎn)單圖化， 設(shè)G＝<V，E>以該序列為度數(shù)列。 不妨設(shè)V＝{v1,v2,v3,v4} 且d(v1)＝d(v2)＝d(v3)＝3,d(v4)＝1， 由于d(v4)＝1，因而v4只能與v1，v2，v3之一相鄰， 于是v1，v2，v3不可能都是3度頂點(diǎn)，這是矛盾的， 因而(3)中序列也不可簡(jiǎn)單圖化。

(4)(d1,d2,…dn)，d1>d2>…>dn≥1且為偶數(shù)。可圖化，不可簡(jiǎn)單圖化。整理課件例14.2(5)(4,4,3,3,2,2) 可簡(jiǎn)單圖化。下圖中兩個(gè)6階無(wú)向簡(jiǎn)單圖都以(5)中序列為度數(shù)列。整理課件圖的同構(gòu)定義14.5設(shè)G1＝<V1,E1>，G2＝<V2,E2>為兩個(gè)無(wú)向圖， 若存在雙射函數(shù)f：V1→V2，對(duì)于vi,vj∈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)的，記做G1≌G2。說(shuō)明 (1)類似地，可以定義兩個(gè)有向圖的同構(gòu)。 (2)圖的同構(gòu)關(guān)系看成全體圖集合上的二元關(guān)系。 (3)圖的同構(gòu)關(guān)系是等價(jià)關(guān)系。

(4)在圖同構(gòu)的意義下，圖的數(shù)學(xué)定義與圖形表示 是一一對(duì)應(yīng)的。

整理課件圖的同構(gòu)舉例彼得森(Petersen)圖整理課件完全圖定義14.6設(shè)G為n階無(wú)向簡(jiǎn)單圖，若G中每個(gè)頂點(diǎn)均與其余的n-1個(gè)頂點(diǎn)相鄰，則稱G為n階無(wú)向完全圖，簡(jiǎn)稱n階完全圖，記做Kn(n≥1)。 設(shè)D為n階有向簡(jiǎn)單圖，若D中每個(gè)頂點(diǎn)都鄰接到其余的n-1個(gè)頂點(diǎn)，又鄰接于其余的n-1個(gè)頂點(diǎn)，則稱D是n階有向完全圖。 設(shè)D為n階有向簡(jiǎn)單圖，若D的基圖為n階無(wú)向完全圖Kn，則稱D是n階競(jìng)賽圖。整理課件完全圖舉例n階無(wú)向完全圖的邊數(shù)為： n(n-1)/2n階有向完全圖的邊數(shù)為： n(n-1)n階競(jìng)賽圖的邊數(shù)為： n(n-1)/2K53階有向完全圖4階競(jìng)賽圖整理課件正則圖定義14.7設(shè)G為n階無(wú)向簡(jiǎn)單圖，若v∈V(G)，均有d(v)＝k，則稱G為k-正則圖。舉例

n階零圖是0-正則圖

n階無(wú)向完全圖是(n-1)-正則圖 彼得森圖是3-正則圖說(shuō)明 n階k-正則圖中，邊數(shù)m＝kn/2。 當(dāng)k為奇數(shù)時(shí)，n必為偶數(shù)。整理課件子圖定義14.8設(shè)G＝<V,E>，G＝<V,E>為兩個(gè)圖(同為無(wú)向圖或同為有向圖)，若VV且EE，則稱G是G的子圖，G為G的母圖，記作GG。 若VV或EE，則稱G為G的真子圖。 若V＝V，則稱G為G的生成子圖。 設(shè)G＝<V,E>為一圖，V1V且V1≠，稱以V1為頂點(diǎn)集，以G中兩個(gè)端點(diǎn)都在V1中的邊組成邊集E1的圖為G的V1導(dǎo)出的子圖，記作G[V1]。 設(shè)E1E且E1≠，稱以E1為邊集，以E1中邊關(guān)聯(lián)的頂點(diǎn)為頂點(diǎn)集V1的圖為G的E1導(dǎo)出的子圖，記作G[E1]。整理課件導(dǎo)出子圖舉例在上圖中，設(shè)G為(1)中圖所表示，取V1＝{a,b,c}，則V1的導(dǎo)出子圖G[V1]為(2)中圖所示。取E1＝{e1,e3}，則E1的導(dǎo)出子圖G[E1]為(3)中圖所示。整理課件例14.3(1)畫出4階3條邊的所有非同構(gòu)的無(wú)向簡(jiǎn)單圖。 由握手定理可知，所畫的無(wú)向簡(jiǎn)單圖各頂點(diǎn)度數(shù)之和為2×3＝6，最大度小于或等于3。于是所求無(wú)向簡(jiǎn)單圖的度數(shù)列應(yīng)滿足的條件是，將6分成4個(gè)非負(fù)整數(shù)，每個(gè)整數(shù)均大于或等于0且小于或等于3，并且奇數(shù)的個(gè)數(shù)為偶數(shù)。將這樣的整數(shù)列排出來(lái)只有下面三種情況：(1)2，2，1，1

(2)3，1，1，1

(3)2，2，2，0將每種度數(shù)列所有非同構(gòu)的圖都畫出來(lái)即得所要求的全部非同構(gòu)的圖。對(duì)于給定的正整數(shù)n和m(m≤n(n-1)/2)，構(gòu)造出所有非同構(gòu)的n階m條邊的所有非同構(gòu)的無(wú)向(有向)簡(jiǎn)單圖，這是目前還沒有解決的難題。整理課件例14.3(2)畫出3階2條邊的所有非同構(gòu)的有向簡(jiǎn)單圖。

由握手定理可知，所畫有向簡(jiǎn)單圖各頂點(diǎn)度數(shù)之和為4，最大出度和最大入度均小于或等于2。度數(shù)列及入度出度列為1,2,1入度列為0,1,1或0,2,0或1,0,1出度列為1,1,0或1,0,1或0,2,02,2,0入度列為1,1,0出度列為1,1,0整理課件定義14.9定義14.9設(shè)G＝<V,E>為n階無(wú)向簡(jiǎn)單圖，以V為頂點(diǎn)集，以所有使G成為完全圖Kn的添加邊組成的集合為邊集的圖，稱為G的補(bǔ)圖，記作G。 若圖G≌G，則稱為G是自補(bǔ)圖。(1)為自補(bǔ)圖(2)和(3)互為補(bǔ)圖整理課件定義14.10定義14.10設(shè)G＝<V,E>為無(wú)向圖。(1)設(shè)e∈E，用G-e表示從G中去掉邊e，稱為刪除e。 設(shè)EE，用G-E表示從G中刪除E中所有的邊，稱為刪除E。(2)設(shè)v∈V，用G-v表示從G中去掉v及所關(guān)聯(lián)的一切邊，稱為刪除頂點(diǎn)v。 設(shè)VV，用G-V表示從G中刪除V中所有頂點(diǎn)，稱為刪除V。(3)設(shè)邊e＝(u,v)∈E，用G\e表示從G中刪除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,v∈V(u,v可能相鄰，也可能不相鄰)，用G∪(u,v)(或G+(u,v))表示在u,v之間加一條邊(u,v)，稱為加新邊。說(shuō)明 在收縮邊和加新邊過程中可能產(chǎn)生環(huán)和平行邊。整理課件舉例GG－e5G－{e1,

e4}G－v5G－{v4,v5}G\e5整理課件14.2通路與回路定義14.11設(shè)G為無(wú)向標(biāo)定圖，G中頂點(diǎn)與邊的交替序列Г＝vi0ej1vi1ej2vi2…ejivil稱為vi0到vil的通路，其中，vir-1,vir為ejr的端點(diǎn)，r＝1，2，…，l，vi0，vil分別稱為Г的始點(diǎn)與終點(diǎn)，Г中邊的條數(shù)稱為它的長(zhǎng)度。 若vi0＝vil，則稱通路為回路。 若Г的所有邊各異，則稱Г為簡(jiǎn)單通路， 又若vi0＝vil，則稱Г為簡(jiǎn)單回路。 若Г的所有頂點(diǎn)(除vi0與vij可能相同外)各異，所有邊也各異，則稱Г為初級(jí)通路或路徑， 又若vi0＝vil，則稱Г為初級(jí)回路或圈。 將長(zhǎng)度為奇數(shù)的圈稱為奇圈，長(zhǎng)度為偶數(shù)的圈稱為偶圈。整理課件關(guān)于通路與回路的說(shuō)明在初級(jí)通路與初級(jí)回路的定義中，仍將初級(jí)回路看成初級(jí)通路(路徑)的特殊情況，只是在應(yīng)用中初級(jí)通路(路徑)都是始點(diǎn)與終點(diǎn)不相同的，長(zhǎng)為1的圈只能由環(huán)生成，長(zhǎng)為2的圈只能由平行邊生成，因而在簡(jiǎn)單無(wú)向圖中，圈的長(zhǎng)度至少為3。若Г中有邊重復(fù)出現(xiàn)，則稱Г為復(fù)雜通路， 又若vi0＝vil，則稱Г為復(fù)雜回路。在有向圖中，通路、回路及分類的定義與無(wú)向圖中非常相似，只是要注意有向邊方向的一致性。在以上的定義中，將回路定義成通路的特殊情況，即回路也是通路，又初級(jí)通路(回路)是簡(jiǎn)單通路(回路)，但反之不真。整理課件通路和回路的簡(jiǎn)單表示法只用邊的序列表示通路(回路)。定義14.11中的Г可以表示成ej1,ej2,…,ejl。在簡(jiǎn)單圖中也可以只用頂點(diǎn)序列表示通路(回路)。定義中的Г也可以表示成vi0,vi2,…,vil。為了寫出非標(biāo)定圖中的通路(回路)，可以先將非標(biāo)定圖標(biāo)成標(biāo)定圖，再寫出通路與回路。在非簡(jiǎn)單標(biāo)定圖中，當(dāng)只用頂點(diǎn)序列表示不出某些通路(回路)時(shí)，可在頂點(diǎn)序列中加入一些邊(這些邊是平行邊或環(huán))，可稱這種表示法為混合表示法。整理課件定理14.5定理14.5在n階圖G中，若從頂點(diǎn)vi到vj（vi≠vj）存在通路，則從vi到vj存在長(zhǎng)度小于或等于n-1的通路。證明

設(shè)Г＝v0e1v1e2…elvl(v0＝vi,vl＝vj)為G中一條長(zhǎng)度為l的通路， 若l≤n-1，則Г滿足要求， 否則必有l(wèi)+1>n，即Г上的頂點(diǎn)數(shù)大于G中的頂點(diǎn)數(shù)， 于是必存在k,s,0≤k<s≤l，使得vs＝vk, 即在Г上存在vs到自身的回路Csk, 在Г上刪除Csk上的一切邊及除vs外的一切頂點(diǎn)， 得Г＝v0e1v1e2…vkes+1

…elvl,Г仍為vi到vj的通路， 且長(zhǎng)度至少比Г減少1。 若Г還不滿足要求，則重復(fù)上述過程，由于G是有限圖，經(jīng)過有限步后，必得到vi到vj長(zhǎng)度小于或等于n-1的通路。整理課件定理14.6推論在n階圖G中，若從頂點(diǎn)vi到vj（vi≠vj）存在通路，則vi到vj一定存在長(zhǎng)度小于或等于n-1的初級(jí)通路（路徑）。

定理14.6在一個(gè)n階圖G中，若存在vi到自身的回路，則一定存在vi到自身長(zhǎng)度小于或等于n的回路。推論在一個(gè)n階圖G中，若存在vi到自身的簡(jiǎn)單回路，則一定存在vi到自身長(zhǎng)度小于或等于n的初級(jí)回路。整理課件例14.4例14.4無(wú)向完全圖Kn(n≥3)中有幾種非同構(gòu)的圈？解答 長(zhǎng)度相同的圈都是同構(gòu)的， 因而只有長(zhǎng)度不同的圈才是非同構(gòu)的， 易知Kn(n≥3)中含長(zhǎng)度為3，4，…，n的圈， 所以Kn(n≥3)中有n-2種非同構(gòu)的圈。整理課件例14.5例14.5無(wú)向完全圖K3的頂點(diǎn)依次標(biāo)定為a,b,c。在定義意義下K3中有多少個(gè)不同的圈？解答 在同構(gòu)意義下，K3中只有一個(gè)長(zhǎng)度為3的圈。 但在定義意義下，不同起點(diǎn)(終點(diǎn))的圈是不同的， 頂點(diǎn)間排列順序不同的圈也看成是不同的， 因而K3中有6個(gè)不同的長(zhǎng)為3的圈：

abca，acba，bacb，bcab，cabc，cbac 如果只考慮起點(diǎn)(終點(diǎn))的差異， 而不考慮順時(shí)針逆時(shí)針的差異，應(yīng)有3種不同的圈， 當(dāng)然它們都是同構(gòu)的，畫出圖來(lái)只有一個(gè)。整理課件14.3圖的連通性無(wú)向圖的連通性無(wú)向圖中頂點(diǎn)之間的短程線及距離無(wú)向圖的連通程度：點(diǎn)割集、割點(diǎn)、邊割集、割邊、連通度有向圖的連通性及判別方法擴(kuò)大路徑法與極大路徑二部圖及其判別方法整理課件無(wú)向圖的連通性定義14.12設(shè)無(wú)向圖G＝<V,E>，u,v∈V，若u,v之間存在通路，則稱u,v是連通的，記作u～v。

v∈V，規(guī)定v～v。 無(wú)向圖中頂點(diǎn)之間的連通關(guān)系 ～＝{（u,v）|u,v∈V且u與v之間有通路} 是自反的、對(duì)稱的、傳遞的，因而～是V上的等價(jià)關(guān)系。整理課件連通圖與連通分支若無(wú)向圖G是平凡圖或G中任何兩個(gè)頂點(diǎn)都是連通的，則稱G為連通圖，否則稱G是非連通圖或分離圖。說(shuō)明：完全圖Kn(n≥1)都是連通圖 零圖Nn(n≥2)都是分離圖。定義14.13

設(shè)無(wú)向圖G＝<V,E>，V關(guān)于頂點(diǎn)之間的連通關(guān)系～的商集V/～＝{V1,V2,…,Vk}，Vi為等價(jià)類，稱導(dǎo)出子圖G[Vi](i＝1,2,…,k)為G的連通分支，連通分支數(shù)k常記為p(G)。說(shuō)明 若G為連通圖，則p(G)＝1。 若G為非連通圖，則p(G)≥2。 在所有的n階無(wú)向圖中，n階零圖是連通分支最多的， p(Nn)＝n。整理課件無(wú)向圖中頂點(diǎn)之間的短程線及距離定義14.14

設(shè)u,v為無(wú)向圖G中任意兩個(gè)頂點(diǎn)，若u～v，稱u,v之間長(zhǎng)度最短的通路為u,v之間的短程線，短程線的長(zhǎng)度稱為u,v之間的距離，記作d(u,v)。 當(dāng)u,v不連通時(shí)，規(guī)定d(u,v)＝∞。距離有以下性質(zhì)： (1)d(u,v)≥0，u＝v時(shí)，等號(hào)成立。 (2)具有對(duì)稱性，d(u,v)＝d(v,u)。 (3)滿足三角不等式：u,v,w∈V(G)，則

d(u,v)+d(v,w)≥d(u,w)說(shuō)明：在完全圖Kn(n≥2)中，任何兩個(gè)頂點(diǎn)之間的距離都是1。 在n階零圖Nn(n≥2)中，任何兩個(gè)頂點(diǎn)之間的距離都為∞。整理課件如何定義連通度問題：如何定量地比較無(wú)向圖的連通性的強(qiáng)與弱？點(diǎn)連通度：為了破壞連通性，至少需要?jiǎng)h除多少個(gè)頂點(diǎn)？邊連通度：為了破壞連通性，至少需要?jiǎng)h除多少條邊？“破壞連通性”是指“變得更加不連通”。整理課件無(wú)向圖的點(diǎn)割集定義14.15

設(shè)無(wú)向圖G＝<V,E>，若存在VV，且V≠，使得p(G-V)>p(G)，而對(duì)于任意的VV，均有p(G-V)＝p(G)，則稱V是G的點(diǎn)割集。 若V是單元集，即V＝{v}，則稱v為割點(diǎn)。{v2,v4},{v3},{v5}都是點(diǎn)割集v3,v5都是割點(diǎn)v1與v6不在任何割集中。整理課件無(wú)向圖的邊割集定義14.16 設(shè)無(wú)向圖G＝<V,E>，若存在EE，且E≠，使得p(G-E)>p(G)，而對(duì)于任意的EE，均有p(G-E)＝p(G)，則稱E是G的邊割集，或簡(jiǎn)稱為割集。 若E是單元集，即E＝{e}，則稱e為割邊或橋。{e6},{e5},{e2,e3},{e1,e2},{e3,e4},{e1,e4},{e1,e3},{e2,e4}都是割集，e6,e5是橋。整理課件點(diǎn)連通度定義14.17 設(shè)G為無(wú)向連通圖且為非完全圖，則稱K(G)＝min{|V||V為G的點(diǎn)割集} 為G的點(diǎn)連通度，簡(jiǎn)稱連通度。說(shuō)明連通度是為了產(chǎn)生一個(gè)不連通圖需要?jiǎng)h去的點(diǎn)的最少數(shù)目。 規(guī)定完全圖Kn(n≥1)的點(diǎn)連通度為n-1， 規(guī)定非連通圖的點(diǎn)連通度為0， 若K(G)≥k，則稱G是k-連通圖，k為非負(fù)整數(shù)。說(shuō)明 K(G)有時(shí)簡(jiǎn)記為K。 上例中圖的點(diǎn)連通度為1，此圖為1-連通圖。

K5的點(diǎn)連通度K＝4，所以K5是1-連通圖，2-連通圖，3-連通圖，4-連通圖。

若G是k-連通圖（k≥1）則在G中刪除任何k-1個(gè)頂點(diǎn)后，所得圖一定還是連通的。

整理課件邊連通度定義14.18

設(shè)G是無(wú)向連通圖，稱

λ(G)＝min{|E||E

是G的邊割集} 為G的邊連通度。 規(guī)定非連通圖的邊連通度為0。 若λ(G)≥r，則稱G是r邊-連通圖。說(shuō)明

λ(G)也可以簡(jiǎn)記為λ。

若G是r邊-連通圖，則在G中任意刪除r-1條邊后，所得圖依然是連通的。 完全圖Kn的邊連通度為n-1，因而Kn是r邊-連通圖，0≤r≤n-1。 圖14.8中圖的邊連通度λ＝1，它只能是1邊-連通圖。整理課件例14.6求所示各圖的點(diǎn)連通度，邊連通度，并指出它們各是幾連通圖及幾邊連通圖。最后將它們按點(diǎn)連通程度及邊連通程度排序。K＝λ＝4K＝λ＝3K＝λ＝2K＝λ＝1K=1λ=2K＝λ＝2K＝λ＝0K＝λ＝0整理課件例14.6的解答設(shè)第i個(gè)圖的點(diǎn)連通度為Ki，邊連通度為λi，I＝1,2,…,8。容易看出，K1＝λ1＝4，K2＝λ2＝3，K3＝λ3＝2，K4＝λ4＝1，

K5=1λ5=2，K6＝λ6＝2，K7＝λ7＝0，K8＝λ8＝0。 (1)是k-連通圖，k邊-連通圖，k＝1,2,3,4。 (2)是k-連通圖，k邊-連通圖，k＝1,2,3。 (3)是k-連通圖，k邊-連通圖，k＝1,2。 (4)是1-連通圖，1邊-連通圖。 (5)是1-連通圖，k邊-連通圖，k＝1,2。 (6)是k-連通圖，k邊-連通圖，k＝1,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)。整理課件定理14.7定理14.7對(duì)于任何無(wú)向圖G，有

K(G)≤λ(G)≤δ(G)例14.7

(1)給出一些無(wú)向簡(jiǎn)單圖，使得K＝λ＝δ。

(2)給出一些無(wú)向簡(jiǎn)單圖，使得K<λ<δ。解答(1)n階無(wú)向完全圖Kn和n階零圖Nn都滿足要求。(2)在兩個(gè)Kn(n≥4)之間放置一個(gè)頂點(diǎn)v，使v與兩個(gè)Kn中的每一個(gè)的任意兩個(gè)不同的頂點(diǎn)相鄰，所得簡(jiǎn)單圖滿足要求。 因?yàn)檫@樣的圖中有一個(gè)割點(diǎn)，所以點(diǎn)連通度為1， 又因?yàn)闊o(wú)橋，而有兩條邊組成的邊割集，所以邊連通度為2， 當(dāng)n＝4時(shí)，δ＝3，當(dāng)n≥5時(shí)，δ＝4。整理課件有向圖的連通性定義14.19

設(shè)D＝<V,E>為一個(gè)有向圖。vi,vj∈V，若從vi到vj存在通路，則稱vi可達(dá)vj，記作vi→vj， 規(guī)定vi總是可達(dá)自身的，即vi→vi。 若vi→vj且vj→vi，則稱vi與vj是相互可達(dá)的，記作vi

vj。 規(guī)定vivi。說(shuō)明→與都是V上的二元關(guān)系，并且不難看出是V上的等價(jià)關(guān)系。定義14.20

設(shè)D＝<V,E>為有向圖，vi,vj∈V，若vi→vj，稱vi到vj長(zhǎng)度最短的通路為vi到vj的短程線， 短程線的長(zhǎng)度為vi到vj的距離，記作d<vi,vj>。說(shuō)明與無(wú)向圖中頂點(diǎn)vi與vj之間的距離d(vi,vj)相比，d<vi,vj>除無(wú)對(duì)稱性外，具有d(vi,vj)所具有的一切性質(zhì)。整理課件連通圖定義14.21

設(shè)D＝<V,E>為一個(gè)有向圖。若D的基圖是連通圖，則稱D是弱連通圖，簡(jiǎn)稱為連通圖。 若vi,vj∈V，vi→vj與vj→vi至少成立其一，則稱D是單向連通圖。 若均有vi

vj，則稱D是強(qiáng)連通圖。說(shuō)明 強(qiáng)連通圖一定是單向連通圖， 單向連通圖一定是弱連通圖。強(qiáng)連通圖單向連通圖弱連通圖整理課件強(qiáng)連通圖與單向連通圖的判定定理定理14.8設(shè)有向圖D＝<V,E>，V＝{v1,v2,…,vn}。D是強(qiáng)連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的回路。證明

充分性顯然。 下面證明必要性。 由D的強(qiáng)連通性可知，vi→vi+1，i＝1,2,…,n-1。 設(shè)Гi為vi到vi+1的通路。 又因?yàn)関n→v1，設(shè)Гn為vn到v1的通路，則Г1,Г2,…,Гn-1,Гn所圍成的回路經(jīng)過D中每個(gè)頂點(diǎn)至少一次。定理14.9設(shè)D是n階有向圖，D是單向連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的通路。證明 略。整理課件強(qiáng)連通圖與單向連通圖的判定定理定理14.8設(shè)有向圖D＝<V,E>，V＝{v1,v2,…,vn}。D是強(qiáng)連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的回路。證明

充分性顯然。 下面證明必要性。 由D的強(qiáng)連通性可知，vi→vi+1，i＝1,2,…,n-1。 設(shè)Гi為vi到vi+1的通路。 又因?yàn)関n→v1，設(shè)Гn為vn到v1的通路，則Г1,Г2,…,Гn-1,Гn所圍成的回路經(jīng)過D中每個(gè)頂點(diǎn)至少一次。定理14.9設(shè)D是n階有向圖，D是單向連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的通路。證明 略。問題設(shè)有向圖D是單向連通圖，但不是強(qiáng)連通圖，問在D中至少加幾條邊所得圖D就能成為強(qiáng)連通圖？整理課件擴(kuò)大路徑法設(shè)G＝<V,E>為n階無(wú)向圖，E≠，設(shè)Гl為G中一條路徑， 若此路徑的始點(diǎn)或終點(diǎn)與通路外的頂點(diǎn)相鄰，就將它們擴(kuò)到通路中來(lái)。 繼續(xù)這一過程，直到最后得到的通路的兩個(gè)端點(diǎn)不與通路外的頂點(diǎn)相鄰為止。 設(shè)最后得到的路徑為Гl+k(長(zhǎng)度為l的路徑擴(kuò)大成了長(zhǎng)度為l+k的路徑)，稱Гl+k為“極大路徑”， 稱使用此種方法證明問題的方法為“擴(kuò)大路徑法”。有向圖中可以類似地討論，只須注意，在每步擴(kuò)大中保持有向邊方向的一致性。整理課件關(guān)于極大路徑的說(shuō)明由某條路經(jīng)擴(kuò)大出的極大路徑不唯一。極大路徑不一定是圖中最長(zhǎng)的路徑。整理課件例14.8例14.8設(shè)G為n（n≥4）階無(wú)向簡(jiǎn)單圖，δ(G)≥3。 證明G中存在長(zhǎng)度大于或等于4的圈。證明

不妨設(shè)G是連通圖，否則，因?yàn)镚的各連通分支的最小度也都大于或等于3，因而可對(duì)它的某個(gè)連通分支進(jìn)行討論。 設(shè)u,v為G中任意兩個(gè)頂點(diǎn)，由G是連通圖，因而u,v之間存在通路，由定理14.5的推論可知，u,v之間存在路徑，用“擴(kuò)大路徑法”擴(kuò)大這條路徑，設(shè)最后得到的“極大路徑”為Гl＝v0v1…vl，易知l≥3。 若v0與vl相鄰，則Гl∪(v0,vl)為長(zhǎng)度大于或等于4的圈。 否則，由于d(v0)≥δ(G)≥3，因而v0除與Гl上的v1相鄰?fù)猓€存在Гl上的頂點(diǎn)vk(k≠1)和vt(k＜t＜l)與v0相鄰，則v0v1…vk…vtv0為一個(gè)圈且長(zhǎng)度大于或等于4，見圖。整理課件二部圖定義14.22

設(shè)G＝<V,E>為一個(gè)無(wú)向圖，若能將V分成V1和V2(V1∪V2＝V,V1∩V2＝)，使得G中的每條邊的兩個(gè)端點(diǎn)都是一個(gè)屬于V1，另一個(gè)屬于V2，則稱G為二部圖（或稱二分圖，偶圖等），稱V1和V2為互補(bǔ)頂點(diǎn)子集。 常將二部圖G記為<V1,V2,E>。 若G是簡(jiǎn)單二部圖，V1中每個(gè)頂點(diǎn)均與V2中所有頂點(diǎn)相鄰，則稱G為完全二部圖，記為Kr,s，其中r＝|V1|，s＝|V2|。說(shuō)明

n階零圖為二部圖。整理課件二部圖舉例K6的子圖K6的子圖K3,3K2,3K3,3K2,3整理課件二部圖的判定定理定理14.10一個(gè)無(wú)向圖G＝<V,E>是二部圖當(dāng)且僅當(dāng)G中無(wú)奇數(shù)長(zhǎng)度的回路。證明 必要性。 若G中無(wú)回路，結(jié)論顯然成立。 若G中有回路，只需證明G中無(wú)奇圈。 設(shè)C為G中任意一圈，令C＝vi1vi2…vilvi1，易知l≥2。 不妨設(shè)vi1∈V1，則必有vil∈V-V1=V2， 而l必為偶數(shù)，于是C為偶圈， 由C的任意性可知結(jié)論成立。整理課件二部圖的判定定理 充分性。 不妨設(shè)G為連通圖，否則可對(duì)每個(gè)連通分支進(jìn)行討論。 設(shè)v0為G中任意一個(gè)頂點(diǎn)，令

V1＝{v|v∈V(G)∧d(v0,v)為偶數(shù)}

V2＝{v|v∈V(G)∧d(v0,v)為奇數(shù)} 易知，V1≠,V2≠,V1∩V2＝，V1∪V2＝V(G)。 下面只要證明V1中任意兩頂點(diǎn)不相鄰,V2中任意兩點(diǎn)也不相鄰。 若存在vi,vj∈V1相鄰，令(vi,vj)＝e， 設(shè)v0到vi,vj的短程線分別為Гi,Гj， 則它們的長(zhǎng)度d(v0,vi),d(v0,vj)都是偶數(shù)， 于是Гi∪Гj∪e中一定含奇圈，這與已知條件矛盾。 類似可證，V2中也不存在相鄰的頂點(diǎn)，于是G為二部圖。整理課件14.4圖的矩陣表示定義14.23

設(shè)無(wú)向圖G＝<V,E>，V＝{v1,v2,…,vn}，E＝{e1,e2,…,em}，令mij為頂點(diǎn)vi與邊ej的關(guān)聯(lián)次數(shù)，則稱(mij)n×m為G的關(guān)聯(lián)矩陣，記作M(G)。整理課件有向圖的關(guān)聯(lián)矩陣定義14.24

設(shè)有向圖D＝<V,E>中無(wú)環(huán)，V＝{v1,v2,…,vn}，E＝{e1,e2,…,em}，令則稱(mij)n×m為D的關(guān)聯(lián)矩陣，記作M(D)。整理課件有向圖的鄰接矩陣定義14.25

設(shè)有向圖D＝<V,E>，V＝{v1,v2,…,vn}，E＝{e1,e2,…，em}，令aij(1)為頂點(diǎn)vi鄰接到頂點(diǎn)vj邊的條數(shù)，稱(aij(1))n×n為D的鄰接矩陣，記作A(D)，或簡(jiǎn)記為A。整理課件有向圖中的通路數(shù)與回路數(shù)定理14.11

設(shè)A為n階有向圖D