圖論-圖的基本概念和例題

1、圖論圖的基本概念和例題圖論圖的基本概念和例題引言圖論以圖為研究對象，這種圖以若干個(gè)給定的點(diǎn)和連接兩點(diǎn)的線構(gòu)成。借以描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有的特定關(guān)系。圖論是離散數(shù)學(xué)的重要組成部分，是近代應(yīng)用數(shù)學(xué)的重要分支。圖論圖的基本概念和例題圖論最早起源于一些數(shù)學(xué)游戲難題研究：如：迷宮問題，地圖四色問題和哈密頓環(huán)游世界問題等。1936年 科尼格 出版圖論第一本專著有限圖與無限圖理論。發(fā)展：1736年 歐拉 （創(chuàng)始人）發(fā)表了“哥尼斯堡七橋問題無解”論文；1847年 克希霍夫 用圖論分析“電網(wǎng)絡(luò)問題”；里程碑圖論圖的基本概念和例題作為描述事務(wù)之間關(guān)系的手

2、段或稱工具，目前，圖論在許多領(lǐng)域，諸如，計(jì)算機(jī)科學(xué)、物理學(xué)、化學(xué)、運(yùn)籌學(xué)、信息論、控制論、網(wǎng)絡(luò)通訊、社會科學(xué)以及經(jīng)濟(jì)管理、軍事、國防、工農(nóng)業(yè)生產(chǎn)等方面都得到廣泛的應(yīng)用，也正是因?yàn)樵诒姸喾矫娴膽?yīng)用中，圖論自身才得到了非常迅速的發(fā)展。 圖論圖的基本概念和例題14.1 圖的基本概念圖：用點(diǎn)和線來刻劃離散事物集合中的每對事物間以某種方式相聯(lián)系的數(shù)學(xué)模型。無序積：設(shè)A , B為任意的兩集合，稱a , b| aAbB 為A與B的無序積，記作：A&B , 其中無序?qū) , b記為(a , b) , 且對任意 (a , b)A&B ,有(a , b)=(b , a),即：A&B= B&A區(qū)分幾何圖形圖論圖的基

3、本概念和例題圖的嚴(yán)格數(shù)學(xué)定義：1、無向圖是一個(gè)有序的二元組,記為G； 其中 V,稱為頂點(diǎn)集，其元素稱為頂點(diǎn)或結(jié)點(diǎn)； E稱為邊集,是V&V的多重子集。 其元素稱為無向邊。2、有向圖是一個(gè)有序的二元組,記為D； 其中 V , 為頂點(diǎn)集； E為邊集,是VV的多重子集。 其元素稱為有向邊。圖論圖的基本概念和例題給定無向圖 G=，其中V=v1,v2,v3,v4,v5E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5) 返回12返回15圖論圖的基本概念和例題給定有向圖D=，其中V=a , b , c , dE=, ,返回13圖論圖的基本概念和例

4、題3、相關(guān)概念及規(guī)定|V(G)|= 空圖，記為 G泛指圖 ，D只能用于有向圖 V(G) 、 E(G) 分別表示G的頂點(diǎn)集、邊集；|V(G)|、|E(G)| 分別表示G的頂點(diǎn)數(shù)、邊數(shù)，若均有限，稱G為有限圖； |V(G)|= n n 階圖， E(G)= 零圖 即只有頂點(diǎn)； |V(G)|= n 且 E(G)= n 階零圖，記作Nn稱N1為平凡圖，即只有一個(gè)頂點(diǎn)；圖論圖的基本概念和例題頂點(diǎn)或邊用字母標(biāo)定的圖標(biāo)定圖，否則為非標(biāo)定圖常用ek表示一條無向邊(vi,vj) 或有向邊有向圖各有向邊均改為無向邊后的圖稱為原有向圖的基圖4、關(guān)聯(lián)與相鄰點(diǎn)和邊的關(guān)聯(lián)：若 ei =(u , v) 或 ei=則 u ,

5、v與ei相關(guān)聯(lián)，稱u , v是ei的端點(diǎn)，若uv,則稱ei與u 或ei與v的關(guān)聯(lián)次數(shù)為1；環(huán)：一條邊的兩個(gè)關(guān)聯(lián)的點(diǎn)是同一點(diǎn)的邊稱為環(huán)。圖論圖的基本概念和例題無向圖中若兩點(diǎn)間有多條邊,稱這些邊為平行邊；平行邊：在有向圖中,始點(diǎn)和終點(diǎn)均相同的邊稱為平行邊；邊與邊的相鄰：若 ei與ej至少有一個(gè)公共端點(diǎn)，稱ei ，ej兩邊相鄰； 若 ei= ，則稱u為始點(diǎn)，v 為終點(diǎn)，并稱u鄰接到v，v鄰接于u點(diǎn)與點(diǎn)的相鄰：若 ei = (u , v) 或 ei= 稱u , v 兩點(diǎn)相鄰；孤立點(diǎn)：與任何邊均不關(guān)聯(lián)的點(diǎn)稱為孤立點(diǎn)。圖論圖的基本概念和例題兩點(diǎn)間平行邊的條數(shù)稱為邊的重?cái)?shù)；含平行邊的圖稱為多重圖，不含平行邊

6、和環(huán)的圖稱為簡單圖。稱 e|eEe與v相關(guān)聯(lián) 為v的關(guān)聯(lián)集，記作IG(v);5、鄰域設(shè)無向圖 G= , v V, 稱u|uV(u , v)Euv 為v的鄰域，記作NG(v),并稱 NG(v)v 為v的閉鄰域，記作NG(v) ,示例圖論圖的基本概念和例題 設(shè)有向圖 D=, v V, 稱 u|uVEuv 為v的后繼元集，記作+D(v), 稱 u|uVEuv 為v的先驅(qū)元集，記作-D(v), 稱 +D(v) -D(v) 為v的鄰域，記作ND(v), 并稱 ND(v)v 為v的閉鄰域，記作ND(v).示例圖論圖的基本概念和例題6、點(diǎn)的度數(shù)設(shè)無向圖 G= , v V, 稱v作為邊的端點(diǎn)的次數(shù)之和為v的度

7、數(shù)，簡稱度，記作dG(v), 簡記為d(v);設(shè)有向圖G=, vV, 稱以v為始點(diǎn)的邊的條數(shù)為該點(diǎn)的出度,記作dD+(v), 簡記為d+(v); 以v為終點(diǎn)的邊的條數(shù)為該點(diǎn)的入度,記作dD- (v), 簡記為d- (v);稱 d+(v)+d-(v)為v的度數(shù)，記作d (v)。圖論圖的基本概念和例題在有向圖D中，稱+(D) = maxd+(v)| vV(D) 為D的最大出度，記為+(D) = mind+(v)| vV(D) 為D的最小出度，記為+-(D) = maxd-(v)| vV(D) 為D的最大入度，記為-(D) = mind-(v)| vV(D) 為D的最小入度，記為-在無向圖G中，稱(

8、G) = maxd (v)| vV(G) 為G的最大度，簡記為； (G) = mind (v)| vV(G) 為G的最小度，簡記為；懸掛頂點(diǎn)（相關(guān)聯(lián)的邊為懸掛邊）：度數(shù)為一的頂點(diǎn)。偶度（奇度）頂點(diǎn) 示例圖論圖的基本概念和例題二、圖的基本定理：定理1：在任意無向圖中,結(jié)點(diǎn)度數(shù)和等于邊數(shù)的二倍。 即 d(v1)+ d(v2)+ d(vn)=2m 其中 |V|=n , |E|=m （又稱握手定理）定理2：在任意有向圖中所有結(jié)點(diǎn)的入度之和等于所有 結(jié)點(diǎn)的出度之和。 即 d(v1)+ d(v2)+ d(vn)=2m 且d+(v1)+ d+(v2)+ d+(vn)= d-(v1)+ d-(v2)+ d-(

9、vn)=m推論：在任何圖中, 奇度頂點(diǎn)的個(gè)數(shù)必為偶數(shù)。圖論圖的基本概念和例題定理4： 設(shè)G為任意n階無向簡單圖，則(G) n-1設(shè)G=,為一個(gè)n階無向圖，V= v1,v2,vn,稱 d(v1), d(v2), d(vn) 為G的度數(shù)列，反之，給定非負(fù)整數(shù)列 d=(d1,d2, ,dn),若存在以V= v1,v2,vn為頂點(diǎn)集的n階無向圖,使得d(vi)=di , 則稱d是可圖化的。若所得圖為簡單圖，則稱d是可簡單圖化的。定理3：設(shè)非負(fù)整數(shù)列d=(d1,d2, ,dn), 則d是可圖化的當(dāng)且僅當(dāng) 為偶數(shù)。圖論圖的基本概念和例題例142 判斷下列各非負(fù)整數(shù)列哪些是可圖化的？哪些是可簡單圖化的？ (

10、1) (5,5,4,4,2,1)(2) (5,4,3,2,2)(3) (3,3,3,1)(4) (d1,d2,dn)，d1d2dn1 且 為偶數(shù)(5) (4,4,3,3,2,2) 解 易知，除(1)中序列不可圖化外，其余各序列都可圖化。但除了(5)中序列外，其余的都是不可簡單圖化的。(2)中序列有5個(gè)數(shù)，若它可簡單圖化，設(shè)所得圖為G，則(G)=max5,4,3,2,2=5，這與定理4矛盾。所以(2)中序列不可簡單圖化。類似可證(4)中序列不可簡單圖化。 圖論圖的基本概念和例題假設(shè)(3)中序列可以簡單圖化，設(shè)G=以(3)中序列為度數(shù)列。不妨設(shè)V=v1，v2，v3，v4 且d(v1)= d(v2)

11、=d(v3)=3,d(v4)=1，由于d(v4)1，因而v4只能與v1，v2，v3之一相鄰，于是v1，v2，v3不可能都是3度頂點(diǎn)，這是矛盾的，因而(3)中序列也不可簡單圖化。 (5)中序列是可簡單圖化的，如下圖所示：圖論圖的基本概念和例題三、圖的同構(gòu)設(shè)G1=, G2=為兩個(gè)無向圖（有向圖），若存在雙射函數(shù) f : V1 V2,對于 vi , vjV1 , ( vi, vj)E1 (E1)當(dāng)且僅當(dāng) (f(vi) , f(vj) E2 (E2 ) 并且 ( vi, vj) ()與 (f(vi) , f(vj) ()的重?cái)?shù)相同，則稱G1與G2是同構(gòu)，記作G1G2 圖論圖的基本概念和例題不同構(gòu)（1）

12、為彼得松(Petersen)圖 ，（2）（3）均與（1）同構(gòu)（1）（2）（3）圖論圖的基本概念和例題圖之間的同構(gòu)關(guān)系是等價(jià)關(guān)系 圖之間的同構(gòu)關(guān)系 可看成全體圖集合上的二元關(guān)系，這個(gè)二元關(guān)系 具有自反性，對稱性和傳遞性，因而它是等價(jià)關(guān)系。在這個(gè)等價(jià)關(guān)系的每一等價(jià)類中均取一個(gè)非標(biāo)定圖作為一個(gè)代表，凡與它同構(gòu)的圖，在同構(gòu)的意義之下都可以看成一個(gè)圖，在圖14.3中，(1)，(2)，(3)可以看成一個(gè)圖，它們都是彼得松圖，其中的(1)可看成這類圖的代表。提到彼得松圖，一般是指(1)中圖。 至此，可以這樣說，在圖同構(gòu)的意義下，圖的數(shù)學(xué)定義與圖形表示是一一對應(yīng)的。 圖論圖的基本概念和例題關(guān)于圖之間的同構(gòu)問題

13、還應(yīng)該指出以下兩點(diǎn)： a到目前為止，人們還沒有找到判斷兩個(gè)圖是否同構(gòu)的好的算法，還只能根據(jù)定義看是否能找到滿足條件的雙射函數(shù)，顯然這是困難的。 b需要注意的是，不要將兩個(gè)圖同構(gòu)的必要條件當(dāng)成充分條件。若G1 G2，則它們的階數(shù)相同，邊數(shù)相同，度數(shù)列相同，等等。破壞這些必要條件的任何一個(gè)，兩個(gè)圖就不會同構(gòu)，但以上列出的條件都滿足，兩個(gè)圖也不一定同構(gòu)，見圖有相同的度數(shù)列，但它們不同構(gòu)。 圖論圖的基本概念和例題四、 完全圖和補(bǔ)圖G=為n階無向簡單圖，若G中每個(gè)頂點(diǎn)均與其余的n-1個(gè)頂點(diǎn)相鄰，則稱G為n階無向完全圖,記作Kn(n1）D=為n階有向簡單圖，若D中每一對頂點(diǎn)間均有方向相反的兩邊關(guān)聯(lián),則稱D

14、是n階有向完全圖； D=為n階有向簡單圖，若D的基圖為n階無向完全圖， 則稱D是n階競賽圖。圖論圖的基本概念和例題n階無向完全圖， n階有向完全圖， n階競賽圖的邊數(shù)分別為 n(n-1)/2 ，n(n-1) , n(n-1)/2設(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ù)時(shí)，n必為偶數(shù)。 圖論圖的基本概念和例題設(shè)G=，G=為兩個(gè)圖（同為無向圖或有向 圖），若VV且E E , 則稱G是G的子圖, G為G的母圖

15、，記作GG；若VV且EE , 則稱G是G的真子圖，若V=V，則稱G是G的生成子圖。設(shè)G=為一圖， V1V且V1，E1E且E1GV1：以V1為頂點(diǎn)集，以G中兩個(gè)端點(diǎn)都在V1中的邊 組成邊集的圖，稱為V1導(dǎo)出的子圖。GE1：以E1為邊集，以E1中邊關(guān)聯(lián)的頂點(diǎn)組成頂點(diǎn)集 的圖，稱為E1 導(dǎo)出的子圖。V1=a,b,cE1=e1,e3圖論圖的基本概念和例題例143 (1) 畫出4階3條邊的所有非同構(gòu)的無向簡單圖。 (2) 畫出3階2條邊的所有非同構(gòu)的有向簡單圖。 解 (1)由握手定理可知，所畫的無向簡單圖各頂點(diǎn)度數(shù)之和為23=6，最大度小于或等于3。于是所求無向簡單圖的度數(shù)列應(yīng)滿足的條件是，將6分成4個(gè)

16、非負(fù)整數(shù)，每個(gè)整數(shù)均大于或等于0且小于或等于3，并且奇數(shù)的個(gè)數(shù)為偶數(shù)。將這樣的整數(shù)列排出來只有下面三種情況： (a) 3，1，1，1(b) 2，2，1，1(c) 2，2，2，0 將每種度數(shù)列所有非同構(gòu)的圖都畫出來即得所要求的全部非同構(gòu)的圖 圖論圖的基本概念和例題(2) 由握手定理可知，所畫有向簡單圖各頂點(diǎn)度數(shù)之和為4，最大出度和最大入度均小于或等于2.度數(shù)列及入度出度列為 (b) 2，2，0 (a) 1，2，1其中3個(gè)無向圖都是K4的子圖，而且是生成子圖，4個(gè)有向圖都是3階有向完全圖的生成子圖。 試問K4的所有非同構(gòu)的i(i=0，1，2，4，5，6)條邊的生成子圖各有幾個(gè)？ 圖論圖的基本概念和

17、例題自補(bǔ)圖 互為補(bǔ)圖設(shè)G =為無向圖，GE 從G中去掉邊E ，稱為刪除E ；Ge 從G中去掉邊e，稱為刪除邊e；設(shè)G =為n階無向簡單圖，以V為頂點(diǎn)集，以所有使G成為完全圖Kn添加邊組成的集合為邊集的圖,稱為G的補(bǔ)圖，記作G；若圖GG，則G是自補(bǔ)圖圖論圖的基本概念和例題G(u , v)在u , v(u,vV) 之間加一條邊(u , v),稱為加新邊。Gv 從G中去掉v及所關(guān)聯(lián)的一切邊，稱為刪除頂點(diǎn)v；GV 從G中去掉V及所關(guān)聯(lián)的一切邊，稱為刪除V ；G e 從G中刪除e后，將e的兩個(gè)端點(diǎn)u,v用一個(gè)新的頂點(diǎn)w代替,使w關(guān)聯(lián)e以外u,v關(guān)聯(lián)的所有邊，稱為邊E的收縮；圖論圖的基本概念和例題圖論圖的

18、基本概念和例題下面兩組數(shù)，是否是可以簡單圖化的？若是，請給出盡量多的非同構(gòu)的無向簡單圖以它為度數(shù)列。 （1）2，2，2，3，3，6（2）2，2，2，2，3，3不可簡單圖化。 (2) 可簡單圖化。共有下面4種非同構(gòu)情況，它們都是K6的子圖. 圖論圖的基本概念和例題畫出K4的所有非同構(gòu)的生成子圖。 圖論圖的基本概念和例題在一次象棋比賽中，n名選手中的任意兩名選手之間至多只下一盤，又每人至少下一盤，證明：總能找到兩名選手，他們下棋的盤數(shù)相同。 證明： 做無向圖G=，其中V=v|v為選手 E=(u，v)|u，vVu與v下過棋uv 則G為無向簡單圖。d(v)：v下棋次數(shù)。由已知條件可知，1d(v)n-1

19、。于是 d(v1)，d(v2)，d(vn)只能取從1到n-1中取值。由鴿巢原理，這n個(gè)頂點(diǎn)度數(shù)至少有 =2個(gè)相同，即至少有2個(gè)人下棋次數(shù)相同。 圖論圖的基本概念和例題14.2 通路與回路 定義14.11 設(shè)G為無向標(biāo)定圖，G中頂點(diǎn)與邊的交替序列= 稱為 到 的通路，其中 ， 為 的端點(diǎn)，r=1,2,l, , 分別稱為的始點(diǎn)與終點(diǎn)，中邊的條數(shù)稱為它的長度。若 ，則稱通路為回路。若的所有邊各異，則稱為簡單通路，又若 ，則稱為簡單回路。圖論圖的基本概念和例題若的所有頂點(diǎn)(除 與 可能相同外)各異，所有邊也各異，則稱為初級通路或路徑，此時(shí)又若 ，則稱為初級回路或圈。將長度為奇數(shù)的圈稱為奇圈，長度為偶數(shù)

20、的圈稱為偶圈。 注意，在初級通路與初級回路的定義中，仍將初級回路看成初級通路(路徑)的特殊情況，只是在應(yīng)用中初級通路(路徑)都是始點(diǎn)與終點(diǎn)不相同的，長為1的圈只能由環(huán)生成，長為2的圈只能由平行邊生成，因而在簡單無向圖中，圈的長度至少為3. 另外，若中有邊重復(fù)出現(xiàn)，則稱為復(fù)雜通路，又若 ，則稱為復(fù)雜回路。 在有向圖中，通路、回路及分類的定義與無向圖中非常相似，只是要注意有向邊方向的一致性。 圖論圖的基本概念和例題用頂點(diǎn)與邊的交替序列定義了通路與回路，但還可以用更簡單的表示法表示通路與回路。 只用邊的序列表示通路(回路)。定義14.11中的可以表示成 .(2) 在簡單圖中也可以只用頂點(diǎn)序列表示通路

21、(回路)。定義中的也可以表示成 .(3) 為了寫出非標(biāo)定圖中的通路(回路)，可以先將非標(biāo)定圖標(biāo)成標(biāo)定圖，再寫出通路與回路。(4) 在非簡單標(biāo)定圖中，當(dāng)只用頂點(diǎn)序列表示不出某些通路(回路)時(shí)，可在頂點(diǎn)序列中加入一些邊(這些邊是平行邊或環(huán))，可稱這種表示法為混合表示法。 圖論圖的基本概念和例題例：設(shè)有向圖D=如下圖所示 (1) 在圖中找出所有定義意義下長度分別為1,2,3,4的圈 (至少用一種表示法寫出它們，并以子圖形式畫出它們)。(2) 在圖中找出所有非初級的定義意義下長度分別為3,4,5,6的簡單回路，并以子圖形式畫出它們。 解：(1)長度為1的圈有1個(gè) 長度為2的圈在定義意義下有兩個(gè)，Ae3

22、De2A , De2Ae3D,它們同構(gòu) 長度為3的圈在定義意義下有6個(gè)， 它們是兩個(gè)子圖長度為4的圈在定義意義下有8個(gè)，它們是兩個(gè)子圖圖論圖的基本概念和例題定理 在n階圖G中，若從頂點(diǎn)vi到vj（vivj）存在通路，則從vi到vj存在長度小于或等于（n-1）的通路。證：設(shè)=v0e1v1e2elvl（v0=vi,vl=vj）為G中一條長度為l的通路，若ln-1，則滿足要求， 否則必有l(wèi)+1n，即上的頂點(diǎn)數(shù)大于G中的頂點(diǎn)數(shù)， 于是必存在k,s,0ksl,使得vs=vk, 即在上存在vs到自身的回路Csk, 在上刪除Csk上的一切邊及除vs外的一切頂點(diǎn)， 得= v0e1v1e2vkes+1 elvl

23、,仍為vi到vj的通路，且長度至少比減少1。 若還不滿足要求，則重復(fù)上述過程，由于G是有限圖，經(jīng)過有限步后，必得到vi到vj長度小于或等于n-1的通路。 圖論圖的基本概念和例題推論 在n階圖G中，若從頂點(diǎn)vi到vj（vivj）存在通路，則vi到vj一定存在長度小于或等于n-1的初級通路（路徑）。 定理 在一個(gè)n階圖G中，若存在vi到自身的回路，則一定存在vi到自身長度小于或等于n的回路。 推論 在一個(gè)n階圖G中，若存在vi到自身的簡單回路，則一定存在vi到自身長度小于或等于n的初級回路。 圖論圖的基本概念和例題例 (1) 無向完全圖Kn（n3）中有幾種非同構(gòu)的圈？ (2) 無向完全圖K3的頂點(diǎn)

24、依次標(biāo)定為a,b,c.在定義意義下K3中有多少個(gè)不同的圈？ 解 (1) 長度相同的圈都是同構(gòu)的，因而只有長度不同的圈才是非同構(gòu)的，易知Kn（n3）中含長度為3,4,n的圈，所以Kn（n3）中有n-2種非同構(gòu)的圈。 (2) 在同構(gòu)意義下，K3中只有一個(gè)長度為3的圈。但在定義意義下，不同起點(diǎn)（終點(diǎn)）的圈是不同的，頂點(diǎn)間排列順序不同的圈也看成是不同的， 因而K3中有6個(gè)不同的長為3的圈：abca,acba,bacb,bcab,cabc,cbac。如果只考慮起點(diǎn)（終點(diǎn)）的差異，而不考慮順時(shí)針逆時(shí)針的差異，應(yīng)有3種不同的圈，當(dāng)然它們都是同構(gòu)的，畫出圖來只有一個(gè)。 圖論圖的基本概念和例題14.3 圖的連通

25、性 一、無向圖的連通性 定義1 設(shè)無向圖G=,u,vV，若u,v之間存在通路，則稱u,v是連通的，記作uv. vV，規(guī)定vv. 由定義不難看出，無向圖中頂點(diǎn)之間的連通關(guān)系 =（u,v）|u,vV且u與v之間有通路是自反的，對稱的，傳遞的，因而是V上的等價(jià)關(guān)系定義2 若無向圖G是平凡圖或G中任何兩個(gè)頂點(diǎn)都是連通的，則稱G為連通圖，否則稱G是非連通圖或分離圖。 完全圖Kn(n1)都是連通圖，而零圖Nn(n2)都是分離圖。 圖論圖的基本概念和例題定義3 設(shè)無向圖G=，V關(guān)于頂點(diǎn)之間的連通關(guān)系的商集 V/=V1,V2,Vk，Vi為等價(jià)類，稱導(dǎo)出子圖GVi(i=1,2,k)為G的連通分支，連通分支數(shù)k常

26、記為p(G) 由定義可知，若G為連通圖，則p(G)=1，若G為非連通圖，則p(G)2，在所有的n階無向圖中，n階零圖是連通分支最多的，p(Nn)=n. 圖論圖的基本概念和例題定義4 設(shè)u,v為無向圖G中任意兩個(gè)頂點(diǎn)，若u v，稱u,v之間長度最短的通路為u,v之間的短程線，短程線的長度稱為u,v之間的距離，記作d(u,v).當(dāng)u,v不連通時(shí)，規(guī)定d(u,v)=. 距離有以下性質(zhì)： 1d(u,v)0，u=v時(shí)，等號成立。2具有對稱性，d(u,v)=d(v,u)。3滿足三角不等式： u,v,wV(G)，則d(u,v)+d(v,w)d(u,w) 在完全圖Kn(n2)中，任何兩個(gè)頂點(diǎn)之間的距離都是1，

27、而在n階零圖Nn(n2)中，任何兩個(gè)頂點(diǎn)之間的距離都為. 圖論圖的基本概念和例題定義5 設(shè)無向圖G=，若存在VV，且V，使得p(G-V)p(G)，而對于任意的V V，均有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與懸掛頂點(diǎn)v6不在任何割集中。 圖論圖的基本概念和例題定義6 設(shè)無向圖G=，若存在EE，且E，使得p(G-E)p(G)，而對于任意的EE，均有p(G-E)=p(G)，則稱E是G的邊割集，或簡稱為割集。若E是單元集，即E=e，則稱e為割邊或橋。 在右圖中，e6,e5,e2,

28、e3,e1,e2,e3,e4,e1,e4,e1,e3,e2,e4都是割集，其中e6,e5是橋。 圖論圖的基本概念和例題定義7 設(shè)G為無向連通圖且為非完全圖，則稱 (G)=min|V|V為G的點(diǎn)割集為G的點(diǎn)連通度，簡稱連通度。規(guī)定完全圖Kn(n1)的點(diǎn)連通度為n-1，又規(guī)定非連通圖的點(diǎn)連通度為0.又若(G)k，則稱G是k-連通圖，k為非負(fù)整數(shù)。若G是k-連通圖（k1）則在G中刪除任何k-1個(gè)頂點(diǎn)后，所得圖一定還是連通的。 圖論圖的基本概念和例題定義8 設(shè)G是無向連通圖，稱 (G)=min|E| E是G的點(diǎn)割集為G的邊連通度。規(guī)定非連通圖的邊連通度為0.又若(G)r，則稱G是r邊-連通圖。 若G是

29、r邊-連通圖，則在G中任意刪除r-1條邊后，所得圖依然是連通的 完全圖Kn的邊連通度為n-1，因而Kn是r邊-連通圖，0rn-1. 設(shè)G1,G2都是n階無向簡單圖，若(G1)(G2)，則稱G1比G2的點(diǎn)連通程度高。若(G1)(G2)，則稱G1比G2的邊連通程度高。 圖論圖的基本概念和例題例1 求圖中所示各圖的點(diǎn)連通度，邊連通度，并指出它們各是幾連通圖及幾邊連通圖。最后將它們按點(diǎn)連通程度及邊連通程度排序。 解 設(shè)第i個(gè)圖的點(diǎn)連通度為i，邊連通度為i，i=1,2,8.容易看出，1=1=4，2=2=3，3=3=2，4=4=1，5=1，5=2，6=6=2，7=7=0，8=8=0. 圖論圖的基本概念和例

30、題定理1 對于任何無向圖G，有 (G)(G)(G)例2 （1）給出一些無向簡單圖，使得=. （2）給出一些無向簡單圖，使得. 解 （1）n階無向完全圖Kn和n階零圖Nn都滿足要求。 圖論圖的基本概念和例題二、有向圖的連通性及其分類 定義9 設(shè)D=為一個(gè)有向圖。vi,vjV，若從vi到vj存在通路，則稱vi可達(dá)vj，記作vivj，規(guī)定vi總是可達(dá)自身的，即vivi.若vivj且vjvi，則稱vi與vj是相互可達(dá)的，記作vi vj.規(guī)定 vi vi. 與都是V上的二元關(guān)系，并且不難看出是V上的等價(jià)關(guān)系。 定義10設(shè)D=為有向圖，vi,vjV，若vivj，稱vi到vj長度最短的通路為vi到vj的短程

31、線，短程線的長度為vi到vj的距離，記作d. 圖論圖的基本概念和例題與無向圖中頂點(diǎn)vi與vj之間的距離d(vi,vj)相比，d除無對稱性外，具有d(vi,vj)所具有的一切性質(zhì)。 定義11 設(shè)D=為一個(gè)有向圖。若D的基圖是連通圖，則稱D是弱連通圖，簡稱為連通圖。若vi,vjV ，vivj與vjvi至少成立其一，則稱D是單向連通圖。若均有vivj，則稱D是強(qiáng)連通圖。 強(qiáng)連通圖一定是單向連通圖，單向連通圖一定是弱連通圖。 強(qiáng)連通圖單向連通圖弱連通圖圖論圖的基本概念和例題 定理2 設(shè)有向圖D=，D=v1,v2,vn.D是強(qiáng)連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的回路。 證 充分性顯然。下面證明必

32、要性。由D的強(qiáng)連通性可知，vivi+1，i=1,2,n-1，設(shè)i為vi到vi+1的通路。又因?yàn)関nv1，設(shè)n為vn到v1的通路，則1,2,n-1,n所圍成的回路經(jīng)過D中每個(gè)頂點(diǎn)至少一次。 圖論圖的基本概念和例題 定理3 設(shè)D是n階有向圖，D是單向連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的通路。 圖論圖的基本概念和例題三、擴(kuò)大路徑法及極大路徑 設(shè)G=為n階無向圖，E，設(shè)l為G中一條路徑，若此路徑的始點(diǎn)或終點(diǎn)與通路外的頂點(diǎn)相鄰，就將它們擴(kuò)到通路中來，繼續(xù)這一過程，直到最后得到的通路的兩個(gè)端點(diǎn)不與通路外的頂點(diǎn)相鄰為止，設(shè)最后得到的路徑為l+k（長度為l的路徑擴(kuò)大成了長度為l+k的路徑），稱l+k為

33、“極大路徑”，稱使用此種方法證明問題的方法為“擴(kuò)大路徑法”。（演示） 圖論圖的基本概念和例題例3 設(shè)G為n（n4）階無向簡單圖，(G)3.證明G中存在長度大于或等于4的圈。 證 不妨設(shè)G是連通圖，否則，因?yàn)镚的各連通分支的最小度也都大于或等于3，因而可對它的某個(gè)連通分支進(jìn)行討論。設(shè)u,v為G中任意兩個(gè)頂點(diǎn)，由G是連通圖，因而u,v之間存在通路，由定理的推論可知，u,v之間存在路徑，用“擴(kuò)大路徑法”擴(kuò)大這條路徑，設(shè)最后得到的“極大路徑”為l=v0v1vl，易知l3.若v0與v1相鄰，則l(v0,vl)為長度大于或等于4的圈。否則，由于d(v0)(G)3，因而v0除與l上的v1相鄰?fù)?，還存在l上的

34、頂點(diǎn)vk(k1)和vt(ktl)與v0相鄰，則v0v1vkvtv0為一個(gè)圈且長度大于或等于4，見下圖. 圖論圖的基本概念和例題四、二部圖及判別定理 定義12 設(shè)G=為一個(gè)無向圖，若能將V分成V1和V2（V1V2=V,V1V2=），使得G中的每條邊的兩個(gè)端點(diǎn)都是一個(gè)屬于V1，另一個(gè)屬于V2，則稱G為二部圖（或稱二分圖，偶圖等），稱V1和V2為互補(bǔ)頂點(diǎn)子集，常將二部圖G記為.又若G是簡單二部圖，V1中每個(gè)頂點(diǎn)均與V2中所有頂點(diǎn)相鄰，則稱G為完全二部圖，記為Kr,s，其中r=|V1|,s=|V2|. 注意，n階零圖為二部圖。 圖論圖的基本概念和例題在圖上中所示各圖都是二部圖，其中，(1)，(2)，(

35、3)為K6的子圖，(3)為完全二部圖K3,3，常將K3,3畫成與其同構(gòu)的(5)的形式，K3,3是下文中經(jīng)常遇到的圖。(4)是K5的子圖，它是完全二部圖K2,3，K2,3常畫成(6)的形式。 圖論圖的基本概念和例題定理4 n(n2)階無向圖G是二部圖當(dāng)且僅當(dāng)G中無奇圈。 證 必要性。若G中無圈，結(jié)論顯然成立。若G中有圈，設(shè)C為G中任意一圈，令C= vi1vi2vilvi1，易知l2.不妨設(shè)vi1V1 ，則vi1,vi2,vil依次交替屬于V1，V2，且有vilV-V1=V2，而l必為偶數(shù)，于是C為偶圈，由C的任意性可知結(jié)論成立。 圖論圖的基本概念和例題充分性。不妨設(shè)G為連通圖，否則可對每個(gè)連通分

36、支進(jìn)行討論。設(shè)v0為G中任意一個(gè)頂點(diǎn)，令 V1=v|vV(G)d(v0,v)為偶數(shù)V2=v|vV(G)d(v0,v)為奇數(shù) 易知，V1 ,V2,V1V2= ，V1V2=V(G).下面只要證明V1中任意兩頂點(diǎn)不相鄰，V2中任意兩點(diǎn)也不相鄰。若存在vi,vjV1相鄰，令（vi,vj）=e，設(shè)v0到vi,vj的短程線分別為i,j，則它們的長度d(v0,vi),d(v0,vj)都是偶數(shù)，于是ije中一定含奇圈，這與已知條件矛盾，類似可證，V2中也不存在相鄰的頂點(diǎn)，于是G為二部圖。 圖論圖的基本概念和例題習(xí)題：1、設(shè)無向圖中只有兩個(gè)奇度頂點(diǎn)u和v，試證明u與v必連通。反證法：假設(shè)u與v不連通，即u與v之

37、間沒有通路， 則u與v處于不同的連通分支中。不妨設(shè)u在G1，v在G2中，于是G1 ， G2作為G的子圖，他們中均只含一個(gè)奇度頂點(diǎn)，與握手定理相矛盾。圖論圖的基本概念和例題2、設(shè)G為n階無向簡單圖，試證： （1）當(dāng)(G)n/2時(shí),證明G是連通的。 （2）當(dāng)(G)(n+k-1)/2時(shí),證明G是k-連通圖。反證法：假設(shè)G至少有兩個(gè)連通分支，設(shè)G1，G2為其中的兩個(gè)，并設(shè)G1，G2的階數(shù)分別為n1和n2，則n1+n2n,且minn1,n2 n/2，于是對任意的vV(G1)，dG1(v)= dG(v) n/2-1n/2這與(G)n/2矛盾，所以G是連通的。圖論圖的基本概念和例題要證明G是k-連通圖，只需

38、證明從G中刪除任意k-1個(gè)頂點(diǎn)后，所得圖仍然是連通的。設(shè)V為V(G)的任意子集，且|V|=k-1，令G=G-V，則G為n-(k-1)=n-k+1=n階無向簡單圖。而(G) (G)-(k-1) (n+k-1)/2-(k-1)=(n-k+1)/2=n/2由（1）可知，G連通，故G為k-連通圖。圖論圖的基本概念和例題14.4 圖的矩陣表示 用矩陣表示圖，便于用代數(shù)方法研究圖的性質(zhì)，也便于計(jì)算機(jī)處理圖。用矩陣表示圖之前，必須將圖的頂點(diǎn)或邊標(biāo)定順序，使其成為標(biāo)定圖。定義 設(shè)無向圖G=，V=v1,v2,vn，E=e1,e2,em，令mij為頂點(diǎn)vi與邊ej的關(guān)聯(lián)次數(shù)，則稱(mij)nm為G的關(guān)聯(lián)矩陣，記作

39、M(G). 所示無向圖的關(guān)聯(lián)矩陣為 M(G)= 圖論圖的基本概念和例題關(guān)聯(lián)矩陣M(G)有以下性質(zhì)： 1 mij=2(j=1,2,m)即M(G)每列元素之和均為2，這正說明每條邊關(guān)聯(lián)兩個(gè)頂點(diǎn)（環(huán)所關(guān)聯(lián)的兩個(gè)端點(diǎn)重合）。 2 mij =d(vi)，即M(G)第i行元素之和為vi的度數(shù)，i=1,2,n. 3 d(vi)= mij= mij= 2=2m,這個(gè)結(jié)果正是握手定理的內(nèi)容，即各頂點(diǎn)的度數(shù)之和等于邊數(shù)的2倍。 4 第j列與第k行相同，當(dāng)且僅當(dāng)邊ej與ek是平行邊。 5 mij=0當(dāng)且僅當(dāng)vi是孤立點(diǎn)。 圖論圖的基本概念和例題定義 設(shè)有向圖D=中無環(huán)，V=v1,v2,vn，E=e1,e2,em,令 mij= 則稱(mij)nm為D的關(guān)聯(lián)矩陣，記作M(D). M(D)= 圖論圖的基本概念和例題M(D)有如下各條性質(zhì)： 1 mij=0，j=1,2,m，從而 mij =0，這說明M(D)中所有元素之和為0 2