圖的基本概念課件

第14章圖的基本概念離散數(shù)學(xué)本章內(nèi)容14.1 圖14.2 通路與回路14.3 圖的連通性14.4 圖的矩陣表示14.5 圖的運算 基本要求 作業(yè)圖的基本概念14.1圖的基本概念圖的定義圖的一些概念和規(guī)定簡單圖和多重圖頂點的度數(shù)與握手定理圖的同構(gòu)完全圖與正則圖子圖與補(bǔ)圖圖的基本概念無序積與多重集合

元素可以重復(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一個無向圖是一個有序的二元組<V，E>,記作G，其中 （1）V≠

稱為頂點集，其元素稱為頂點或結(jié)點。 （2）E稱為邊集，它是無序積V&V的多重子集，其元素稱為無向邊，簡稱邊。定義14.2一個有向圖是一個有序的二元組<V，E>，記作D，其中 （1）V≠

稱為頂點集，其元素稱為頂點或結(jié)點。 （2）E為邊集，它是笛卡兒積V×V的多重子集，其元素稱為有向邊，簡稱邊。無向圖和有向圖說明可以用圖形表示圖，即用小圓圈（或?qū)嵭狞c）表示頂點，用頂點之間的連線表示無向邊，用有方向的連線表示有向邊。圖的基本概念例14.1例14.1(1)給定無向圖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表示無向圖，但有時用G泛指圖(無向的或有向的)。D只能表示有向圖。V(G)，E(G)分別表示G的頂點集和邊集。若|V(G)|＝n，則稱G為n階圖。若|V(G)|與|E(G)|均為有限數(shù)，則稱G為有限圖。若邊集E(G)＝

，則稱G為零圖，此時，又若G為n階圖，則稱G為n階零圖，記作Nn，特別地，稱N1為平凡圖。在圖的定義中規(guī)定頂點集V為非空集，但在圖的運算中可能產(chǎn)生頂點集為空集的運算結(jié)果，為此規(guī)定頂點集為空集的圖為空圖，并將空圖記為

。圖的基本概念標(biāo)定圖與非標(biāo)定圖、基圖將圖的集合定義轉(zhuǎn)化成圖形表示之后，常用ek表示無向邊(vi,vj)（或有向邊<vi,vj>），并稱頂點或邊用字母標(biāo)定的圖為標(biāo)定圖，否則稱為非標(biāo)定圖。將有向圖各有向邊均改成無向邊后的無向圖稱為原來圖的基圖。易知標(biāo)定圖與非標(biāo)定圖是可以相互轉(zhuǎn)化的，任何無向圖G的各邊均加上箭頭就可以得到以G為基圖的有向圖。圖的基本概念關(guān)聯(lián)與關(guān)聯(lián)次數(shù)、環(huán)、孤立點設(shè)G＝<V,E>為無向圖，ek＝(vi,vj)∈E， 稱vi,vj為ek的端點，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)。

若端點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的端點。 若vi＝vj，則稱ek為D中的環(huán)。無論在無向圖中還是在有向圖中，無邊關(guān)聯(lián)的頂點均稱為孤立點。圖的基本概念相鄰與鄰接設(shè)無向圖G＝<V，E>，vi，vj∈V，ek，el∈E。 若

et∈E，使得et＝(vi，vj)，則稱vi與vj是相鄰的。 若ek與el至少有一個公共端點，則稱ek與el是相鄰的。設(shè)有向圖D＝<V，E>，vi，vj∈V，ek，el∈E。 若

et∈E，使得et＝<vi，vj>，則稱vi為et的始點，vj為et的終點，并稱vi鄰接到vj，vj鄰接于vi。 若ek的終點為el的始點，則稱ek與el相鄰。圖的基本概念鄰域設(shè)無向圖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}圖的基本概念簡單圖與多重圖定義14.3在無向圖中，關(guān)聯(lián)一對頂點的無向邊如果多于1條，則稱這些邊為平行邊，平行邊的條數(shù)稱為重數(shù)。 在有向圖中，關(guān)聯(lián)一對頂點的有向邊如果多于1條，并且這些邊的始點和終點相同(也就是它們的方向相同)，則稱這些邊為平行邊。 含平行邊的圖稱為多重圖。

既不含平行邊也不含環(huán)的圖稱為簡單圖。例如：在圖14.1中， (a)中e5與e6是平行邊， (b)中e2與e3是平行邊，但e6與e7不是平行邊。 (a)和(b)兩個圖都不是簡單圖。圖的基本概念頂點的度數(shù)定義14.4設(shè)G＝<V,E>為一無向圖，

v∈V，稱v作為邊的端點次數(shù)之和為v的度數(shù)，簡稱為度，記做dG(v)。 在不發(fā)生混淆時，簡記為d(v)。 設(shè)D＝<V，E>為有向圖，

v∈V， 稱v作為邊的始點次數(shù)之和為v的出度，記做d+D(v)，簡記作d+(v)。 稱v作為邊的終點次數(shù)之和為v的入度，記做d-D(v)，簡記作d-(v)。

稱d+(v)+d-(v)為v的度數(shù)，記做d(v)。圖的基本概念圖的度數(shù)的相關(guān)概念在無向圖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的頂點為懸掛頂點，與它關(guān)聯(lián)的邊稱為懸掛邊。度為偶數(shù)(奇數(shù))的頂點稱為偶度(奇度)頂點。圖的基本概念圖的度數(shù)舉例d(v1)＝4(注意，環(huán)提供2度)，△＝4，δ＝1，v4是懸掛頂點，e7是懸掛邊。d+(a)＝4，d-(a)＝1

(環(huán)e1提供出度1，提供入度1)，d(a)＝4+1＝5。△＝5，δ＝3，△+＝4(在a點達(dá)到)δ+＝0(在b點達(dá)到)△-＝3(在b點達(dá)到)δ-＝1(在a和c點達(dá)到)圖的基本概念握手定理定理14.1設(shè)G＝<V,E>為任意無向圖，V＝{v1,v2,…,vn}， |E|＝m，則說明 任何無向圖中，各頂點度數(shù)之和等于邊數(shù)的兩倍。證明 G中每條邊(包括環(huán))均有兩個端點， 所以在計算G中各頂點度數(shù)之和時， 每條邊均提供2度，當(dāng)然，m條邊，共提供2m度。定理14.2設(shè)D＝<V,E>為任意有向圖，V＝{v1,v2,…,vn}， |E|＝m，則圖的基本概念握手定理的推論推論 任何圖(無向的或有向的)中，奇度頂點的個數(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中頂點度數(shù)為奇數(shù)，所以|V1|必為偶數(shù)。圖的基本概念問題研究問題：在一個部門的25個人中間，由于意見不同，是否可能每個人恰好與其他5個人意見一致？解答：不可能?？紤]一個圖，其中頂點代表人，如果兩個人意見相同，可用邊連接，所以每個頂點都是奇數(shù)度。存在奇數(shù)個度數(shù)為奇數(shù)的圖，這是不可能的。說明： (1)很多離散問題可以用圖模型求解。 (2)為了建立一個圖模型，需要決定頂點和邊分別代表什么。 (3)在一個圖模型中，邊經(jīng)常代表兩個頂點之間的關(guān)系。圖的基本概念度數(shù)列設(shè)G＝<V,E>為一個n階無向圖，V＝{v1,v2,…,vn}，稱d(v1)，d(v2)，…，d(vn)為G的度數(shù)列。對于頂點標(biāo)定的無向圖，它的度數(shù)列是唯一的。反之，對于給定的非負(fù)整數(shù)列d＝{d1,d2,…,dn}，若存在V＝{v1,v2,…,vn}為頂點集的n階無向圖G，使得d(vi)＝di，則稱d是可圖化的。特別地，若所得圖是簡單圖，則稱d是可簡單圖化的。類似地，設(shè)D＝<V,E>為一個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ù)列舉例按頂點的標(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ù)個奇數(shù)度點。 奇數(shù)度點兩兩之間連一邊，剩余度用環(huán)來實現(xiàn)。5331圖的基本概念定理14.3的證明由握手定理可知必然性顯然。下面證明充分性。由已知條件可知，d中有2k(0≤k≤[n/2])個奇數(shù)，不妨設(shè)它們?yōu)閐1，d2，…，dk，dk+1，dk+2，…，d2k

?？捎枚喾N方法做出n階無向圖G＝<V,E>，V＝{v1,v2,…vn}。比如邊集如下產(chǎn)生：在頂點vr與vr+k之間連邊，r＝1,2,…,k。若di為偶數(shù)，令d

i＝di，若di為奇數(shù)，令d

i＝di-1，得d

＝(d

1，d

2，…，d

n)，則d

i均為偶數(shù)。再在vi處做出d

i/2條環(huán),i＝1,…,n，將所得各邊集合在一起組成E，則G的度數(shù)列為d。其實，di為偶數(shù)時，d(vi)＝2·d

i/2＝2·di/2＝di，當(dāng)di為奇數(shù)時，d(vi)＝1+2·d

i/2＝1+d

i＝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階無向簡單圖，則△(G)≤n-1。證明 因為G既無平行邊也無環(huán)， 所以G中任何頂點v至多與其余的n-1個頂點均相鄰， 于是d(v)≤n-1，由于v的任意性，所以△(G)≤n-1。例14.2判斷下列各非負(fù)整數(shù)列哪些是可圖化的？哪些是可簡單圖化的？ (1)(5,5,4,4,2,1) 不可圖化。(2)(5,4,3,2,2)

可圖化，不可簡單圖化。若它可簡單圖化， 設(shè)所得圖為G，則(G)＝max{5,4,3,2,2}＝5， 這與定理14.4矛盾。圖的基本概念例14.2(3)(3,3,3,1) 可圖化，不可簡單圖化。假設(shè)該序列可以簡單圖化， 設(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度頂點，這是矛盾的， 因而(3)中序列也不可簡單圖化。

(4)(d1,d2,…dn)，d1>d2>…>dn≥1且為偶數(shù)?？蓤D化，不可簡單圖化。圖的基本概念例14.2(5)(4,4,3,3,2,2) 可簡單圖化。下圖中兩個6階無向簡單圖都以(5)中序列為度數(shù)列。圖的基本概念圖的同構(gòu)定義14.5設(shè)G1＝<V1,E1>，G2＝<V2,E2>為兩個無向圖， 若存在雙射函數(shù)f：V1→V2，對于vi,vj∈V1，(vi,vj)∈E1 當(dāng)且僅當(dāng) (f(vi),f(vj))∈E2， 并且 (vi,vj)與(f(vi),f(vj))的重數(shù)相同， 則稱G1與G2是同構(gòu)的，記做G1≌G2。說明 (1)類似地，可以定義兩個有向圖的同構(gòu)。 (2)圖的同構(gòu)關(guān)系看成全體圖集合上的二元關(guān)系。 (3)圖的同構(gòu)關(guān)系是等價關(guān)系。

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

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

n階零圖是0-正則圖

n階無向完全圖是(n-1)-正則圖 彼得森圖是3-正則圖說明 n階k-正則圖中，邊數(shù)m＝kn/2。 當(dāng)k為奇數(shù)時，n必為偶數(shù)。圖的基本概念子圖定義14.8設(shè)G＝<V,E>，G＝<V

,E

>為兩個圖(同為無向圖或同為有向圖)，若V

V且E

E，則稱G

是G的子圖，G為G

的母圖，記作G

G。 若V

V或E

E，則稱G

為G的真子圖。 若V＝V，則稱G

為G的生成子圖。 設(shè)G＝<V,E>為一圖，V1

V且V1≠

，稱以V1為頂點集，以G中兩個端點都在V1中的邊組成邊集E1的圖為G的V1導(dǎo)出的子圖，記作G[V1]。 設(shè)E1

E且E1≠

，稱以E1為邊集，以E1中邊關(guān)聯(liá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)的無向簡單圖。 由握手定理可知，所畫的無向簡單圖各頂點度數(shù)之和為2×3＝6，最大度小于或等于3。于是所求無向簡單圖的度數(shù)列應(yīng)滿足的條件是，將6分成4個非負(fù)整數(shù)，每個整數(shù)均大于或等于0且小于或等于3，并且奇數(shù)的個數(shù)為偶數(shù)。將這樣的整數(shù)列排出來只有下面三種情況：(1)2，2，1，1

(2)3，1，1，1

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

由握手定理可知，所畫有向簡單圖各頂點度數(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階無向簡單圖，以V為頂點集，以所有使G成為完全圖Kn的添加邊組成的集合為邊集的圖，稱為G的補(bǔ)圖，記作G。 若圖G≌G，則稱為G是自補(bǔ)圖。(1)為自補(bǔ)圖(2)和(3)互為補(bǔ)圖圖的基本概念定義14.10定義14.10設(shè)G＝<V,E>為無向圖。(1)設(shè)e∈E，用G-e表示從G中去掉邊e，稱為刪除e。 設(shè)E

E，用G-E

表示從G中刪除E

中所有的邊，稱為刪除E

。(2)設(shè)v∈V，用G-v表示從G中去掉v及所關(guān)聯(lián)的一切邊，稱為刪除頂點v。 設(shè)V

V，用G-V

表示從G中刪除V

中所有頂點，稱為刪除V

。(3)設(shè)邊e＝(u,v)∈E，用G\e表示從G中刪除e后，將e的兩個端點u,v用一個新的頂點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)，稱為加新邊。說明 在收縮邊和加新邊過程中可能產(chǎn)生環(huán)和平行邊。圖的基本概念舉例GG－e5G－{e1,

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

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

＝v0e1v1e2…vkes+1

…elvl,Г

仍為vi到vj的通路， 且長度至少比Г減少1。 若Г

還不滿足要求，則重復(fù)上述過程，由于G是有限圖，經(jīng)過有限步后，必得到vi到vj長度小于或等于n-1的通路。圖的基本概念定理14.6推論在n階圖G中，若從頂點vi到vj（vi≠vj）存在通路，則vi到vj一定存在長度小于或等于n-1的初級通路（路徑）。

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

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

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

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

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

u,v,w∈V(G)，則

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

設(shè)無向圖G＝<V,E>，若存在V

V，且V

≠

，使得p(G-V

)>p(G)，而對于任意的V

V

，均有p(G-V

)＝p(G)，則稱V

是G的點割集。 若V

是單元集，即V

＝{v}，則稱v為割點。{v2,v4},{v3},{v5}都是點割集v3,v5都是割點v1與v6不在任何割集中。圖的基本概念無向圖的邊割集定義14.16 設(shè)無向圖G＝<V,E>，若存在E

E，且E

≠

，使得p(G-E

)>p(G)，而對于任意的E

E

，均有p(G-E

)＝p(G)，則稱E

是G的邊割集，或簡稱為割集。 若E

是單元集，即E＝{e}，則稱e為割邊或橋。{e6},{e5},{e2,e3},{e1,e2},{e3,e4},{e1,e4},{e1,e3},{e2,e4}都是割集，e6,e5是橋。圖的基本概念點連通度定義14.17 設(shè)G為無向連通圖且為非完全圖，則稱

K(G)＝min{|V

||V

為G的點割集} 為G的點連通度，簡稱連通度。說明連通度是為了產(chǎn)生一個不連通圖需要刪去的點的最少數(shù)目。 規(guī)定完全圖Kn(n≥1)的點連通度為n-1， 規(guī)定非連通圖的點連通度為0， 若K(G)≥k，則稱G是k-連通圖，k為非負(fù)整數(shù)。說明 K(G)有時簡記為K。 上例中圖的點連通度為1，此圖為1-連通圖。

K5的點連通度K＝4，所以K5是1-連通圖，2-連通圖，3-連通圖，4-連通圖。

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

圖的基本概念邊連通度定義14.18

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

λ(G)＝min{|E

||E

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

λ(G)也可以簡記為λ。

若G是r邊-連通圖，則在G中任意刪除r-1條邊后，所得圖依然是連通的。 完全圖Kn的邊連通度為n-1，因而Kn是r邊-連通圖，0≤r≤n-1。 圖14.8中圖的邊連通度λ＝1，它只能是1邊-連通圖。圖的基本概念例14.6求所示各圖的點連通度，邊連通度，并指出它們各是幾連通圖及幾邊連通圖。最后將它們按點連通程度及邊連通程度排序。K＝λ＝4K＝λ＝3K＝λ＝2K＝λ＝1K=1λ=2K＝λ＝2K＝λ＝0K＝λ＝0圖的基本概念例14.6的解答設(shè)第i個圖的點連通度為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邊-連通圖。點連通程度為(1)>(2)>(3)＝(6)>(4)＝(5)>(7)＝(8)。邊連通程度為(1)>(2)>(3)＝(5)＝(6)>(4)>(7)＝(8)。圖的基本概念定理14.7定理14.7對于任何無向圖G，有

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

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

(2)給出一些無向簡單圖，使得K<λ<δ。解答(1)n階無向完全圖Kn和n階零圖Nn都滿足要求。(2)在兩個Kn(n≥4)之間放置一個頂點v，使v與兩個Kn中的每一個的任意兩個不同的頂點相鄰，所得簡單圖滿足要求。 因為這樣的圖中有一個割點，所以點連通度為1， 又因為無橋，而有兩條邊組成的邊割集，所以邊連通度為2， 當(dāng)n＝4時，δ＝3，當(dāng)n≥5時，δ＝4。圖的基本概念有向圖的連通性定義14.19

設(shè)D＝<V,E>為一個有向圖。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ī)定vi

vi。說明→與

都是V上的二元關(guān)系，并且不難看出

是V上的等價關(guān)系。定義14.20

設(shè)D＝<V,E>為有向圖，vi,vj∈V，若vi→vj，稱vi到vj長度最短的通路為vi到vj的短程線， 短程線的長度為vi到vj的距離，記作d<vi,vj>。說明與無向圖中頂點vi與vj之間的距離d(vi,vj)相比，d<vi,vj>除無對稱性外，具有d(vi,vj)所具有的一切性質(zhì)。圖的基本概念連通圖定義14.21

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

vj，則稱D是強(qiáng)連通圖。說明 強(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)過每個頂點至少一次的回路。證明

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

充分性顯然。 下面證明必要性。 由D的強(qiáng)連通性可知，vi→vi+1，i＝1,2,…,n-1。 設(shè)Гi為vi到vi+1的通路。 又因為vn→v1，設(shè)Гn為vn到v1的通路，則Г1,Г2,…,Гn-1,Гn所圍成的回路經(jīng)過D中每個頂點至少一次。定理14.9設(shè)D是n階有向圖，D是單向連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個頂點至少一次的通路。證明 略。問題設(shè)有向圖D是單向連通圖，但不是強(qiáng)連通圖，問在D中至少加幾條邊所得圖D

就能成為強(qiáng)連通圖？圖的基本概念擴(kuò)大路徑法設(shè)G＝<V,E>為n階無向圖，E≠

，設(shè)Гl為G中一條路徑， 若此路徑的始點或終點與通路外的頂點相鄰，就將它們擴(kuò)到通路中來。 繼續(xù)這一過程，直到最后得到的通路的兩個端點不與通路外的頂點相鄰為止。 設(shè)最后得到的路徑為Гl+k(長度為l的路徑擴(kuò)大成了長度為l+k的路徑)，稱Гl+k為“極大路徑”， 稱使用此種方法證明問題的方法為“擴(kuò)大路徑法”。有向圖中可以類似地討論，只須注意，在每步擴(kuò)大中保持有向邊方向的一致性。圖的基本概念關(guān)于極大路徑的說明由某條路經(jīng)擴(kuò)大出的極大路徑不唯一。極大路徑不一定是圖中最長的路徑。圖的基本概念例14.8例14.8設(shè)G為n（n≥4）階無向簡單圖，δ(G)≥3。 證明G中存在長度大于或等于4的圈。證明

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

設(shè)G＝<V,E>為一個無向圖，若能將V分成V1和V2(V1∪V2＝V,V1∩V2＝

)，使得G中的每條邊的兩個端點都是一個屬于V1，另一個屬于V2，則稱G為二部圖（或稱二分圖，偶圖等），稱V1和V2為互補(bǔ)頂點子集。 常將二部圖G記為<V1,V2,E>。 若G是簡單二部圖，V1中每個頂點均與V2中所有頂點相鄰，則稱G為完全二部圖，記為Kr,s，其中r＝|V1|，s＝|V2|。說明

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

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中任意兩頂點不相鄰,V2中任意兩點也不相鄰。 若存在vi,vj∈V1相鄰，令(vi,vj)＝e， 設(shè)v0到vi,vj的短程線分別為Гi,Гj， 則它們的長度d(v0,vi),d(v0,vj)都是偶數(shù)， 于是Гi∪Гj∪e中一定含奇圈，這與已知條件矛盾。 類似可證，V2中也不存在相鄰的頂點，于是G為二部圖。圖的基本概念14.4圖的矩陣表示定義14.23

設(shè)無向圖G＝<V,E>，V＝{v1,v2,…,vn}，E＝{e1,e2,…,em}，令mij為頂點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>中無環(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)為頂點vi鄰接到頂點vj邊的條數(shù)，稱(aij(1))n×n為D的鄰接矩陣，記作A(D)，或簡記為A。圖的基本概念有向圖中的通路數(shù)與回路數(shù)定理14.11

設(shè)A為n階有向圖D的鄰接矩陣,則Al(l

1