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

1、14.1 圖 一無向圖與有向圖 1無序積與多重集 設(shè)A，B為任意的兩個(gè)集合，稱a,b|aAbB為A與B的無序積，記作A&B. 為方便起見，將無序積中的無序?qū),b記為(a,b),并且允許a=b.需要指出的是，無論a,b是否相等，均有(a,b)=(b,a),因而A&B=B&A. 元素可以重復(fù)出現(xiàn)的集合稱為多重集合或者多重集，某元素重復(fù)出現(xiàn)的次數(shù)稱為該元素的重復(fù)度。例如，在多重集合a,a,b,b,b,c,d中，a,b,c,d的重復(fù)度分別為2,3,1,1. 2無向圖與有向圖的定義及表示法 定義14.1 一個(gè)無向圖是一個(gè)有序的二元組,記作G，其中1V稱為頂點(diǎn)集，其元素稱為頂點(diǎn)或結(jié)點(diǎn)。2E稱為邊集，它是

2、無序積V&V的多重子集，其元素稱為無向邊，簡稱邊。定義14.2 一個(gè)有向圖是一個(gè)有序的二元組，記作D，其中 1V同無向圖。2E為邊集，它是笛卡兒積VV的多重子集，其元素稱為有向邊，簡稱邊。 上面給出了無向圖和有向圖的集合定義，但人們總是用圖形來表示它們，即用小圓圈或?qū)嵭狞c(diǎn)表示頂點(diǎn)，用頂點(diǎn)之間的連線表示無向邊，用有方向的連線表示有向邊。 例14.1(1) 給定無向圖G=，其中，V=v1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5). (2) 給定有向圖D=，其中，V=a,b,c,d，E=,. 畫出G與D

3、的圖形。 解 圖14.1中(1),(2)分別給出了無向圖G和有向圖D的圖形。 與定義14.1和定義14.2有關(guān)的還有下面一些概念和規(guī)定。 1n階圖 在圖的定義中，用G表示無向圖，D表示有向圖，但有時(shí)用G泛指圖(無向的或有向的)，可是D只能表示有向圖。另外，為方便起見，有時(shí)用V(G)，E(G)分別表示G的頂點(diǎn)集和邊集，假設(shè)|V(G)|=n,那么稱G為n階圖，對有向圖可做類似規(guī)定。 2有限圖 假設(shè)|V(G)|與|E(G)|均為有限數(shù)，那么稱G為有限圖，本課件中只討論有限圖。 3n階零圖與平凡圖 在圖G中，假設(shè)邊集E(G)=,那么稱G為零圖，此時(shí)，又假設(shè)G為n階圖，那么稱G為n階零圖，記作Nn，特別

4、地，稱N1為平凡圖。 4空圖 在圖的定義中規(guī)定頂點(diǎn)集V為非空集，但在圖的運(yùn)算中可能產(chǎn)生頂點(diǎn)集為空集的運(yùn)算結(jié)果，為此規(guī)定定點(diǎn)集為空集的圖為空圖，并將空圖記為。 5標(biāo)定圖與非標(biāo)定圖、基圖 將圖的集合定義轉(zhuǎn)化成圖形表示之后，常用ek表示無向邊vi，vj或有向邊,并稱頂點(diǎn)或邊用字母標(biāo)定的圖為標(biāo)定圖，否那么稱為非標(biāo)定圖。另外將有向圖各有向邊均改成無向邊后的無向圖稱為原來圖的基圖。易知標(biāo)定圖與非標(biāo)定圖是可以相互轉(zhuǎn)化的，任何無向圖G的各邊均加上箭頭就可以得到以G為基圖的有向圖。 6關(guān)聯(lián)與關(guān)聯(lián)次數(shù)、環(huán)、孤立點(diǎn) 設(shè)G=為無向圖，ek=(vi，vj)E，那么稱vi，vj為ek的端點(diǎn)，ek與vi或ek與vj是彼此相

5、關(guān)聯(lián)的。假設(shè)vivj，那么稱ek與vi或ek與vj的關(guān)聯(lián)次數(shù)為1，假設(shè)vi=vj，那么稱ek與vi的關(guān)聯(lián)次數(shù)為2，并稱ek為環(huán)。任意的vlV，假設(shè)vlvi且vlvj，那么稱ek與vl的關(guān)聯(lián)次數(shù)為0。 設(shè)D=為有向圖，ek=E，稱vi，vj為ek的端點(diǎn)，假設(shè)vi=vj，那么稱ek為D中的環(huán)。無論在無向圖中還是在有向圖中，無邊關(guān)聯(lián)的頂點(diǎn)均稱孤立點(diǎn)。 7相鄰與鄰接 設(shè)無向圖G=，vi，vjV，ek，elE.假設(shè)etE，使得et=vi，vj，那么稱vi與vj是相鄰的。假設(shè)ek與el至少有一個(gè)公共端點(diǎn)，那么稱ek與el是相鄰的。 設(shè)有向圖D=，vi，vjV，ek，elE.假設(shè)etE，使得et=，那么稱v

6、i為et的始點(diǎn)，vj為et的終點(diǎn)，并稱vi鄰接到vj，vj鄰接于vi。假設(shè)ek的終點(diǎn)為el的始點(diǎn)，那么稱ek與el相鄰。 8鄰域與閉鄰域、先驅(qū)元集與后繼元集、關(guān)聯(lián)集 設(shè)無向圖G=，vV，稱 u|uV (u,v)E uv 為v的鄰域，記做NG(v).并稱 NG(v)v 為v的閉鄰域，記做G(v).稱 e|eE e與v相關(guān)聯(lián) 為v的關(guān)聯(lián)集，記做IG(v). 設(shè)有向圖D=，vV，稱 u|uV E uv 為v的后繼元集，記做(v).稱 u|uV E uv 為v的先驅(qū)元集，記做(v).稱 (v)(v) 為v的鄰域，記做ND(v).稱 ND(v)v 為v的閉鄰域，記做D(v). 在圖14.1的(1)圖中，

7、NG(v1)=v2，v5，G(v1)=v1，v2，v5，IG(v1)=e1，e2，e3. 在(2)圖中，(d)=c，(d)=a，c，ND(d)=a，c，D(d)=a，c，d. 9圖的數(shù)學(xué)定義與表示法 給定圖G的數(shù)學(xué)定義，按定義的規(guī)定，一定能畫出它的圖形與之對應(yīng)，但由于頂點(diǎn)放置的位置可以不同，邊的曲直可以不同，所以不同的人畫出的圖形形狀可能不同，但頂點(diǎn)與邊之間的關(guān)聯(lián)關(guān)系是絕對相同的。反之給定某圖G的圖形，假設(shè)非標(biāo)定圖，先將頂點(diǎn)與邊標(biāo)定，那么能唯一地寫出G的數(shù)學(xué)定義形式。 二簡單圖與多重圖 定義14.3 在無向圖中，關(guān)聯(lián)一對頂點(diǎn)的無向邊如果多于1條，那么稱這些邊為平行邊，平行邊的條數(shù)稱為重?cái)?shù)。在有

8、向圖中，關(guān)聯(lián)一對頂點(diǎn)的有向邊如果多于1條，并且這些邊的始點(diǎn)和終點(diǎn)相同(也就是它們的方向相同)，那么稱這些邊為平行邊。含平行邊的圖稱為多重圖，既不含平行邊也不含環(huán)的圖稱為簡單圖。 在圖14.1中，(1)中e5與e6是平行邊，在(2)中，e2與e3是平行邊，注意，e6與e7不是平行邊。(1)，(2)兩個(gè)圖都不是簡單圖。 簡單圖有許多性質(zhì)，在以后逐漸進(jìn)行討論。 三頂點(diǎn)的度數(shù)與握手定理 1頂點(diǎn)的度數(shù) 定義14.4 設(shè)G=為一無向圖，vV，稱v作為邊的端點(diǎn)次數(shù)之和為v的度數(shù)，簡稱為度，記做 dG(v)，在不發(fā)生混淆時(shí)，簡記為d(v).設(shè)D=為有向圖，vV，稱v作為邊的始點(diǎn)次數(shù)之和為v的出度，記做(v)，

9、簡記作d+(v).稱v作為邊的終點(diǎn)次數(shù)之和為v的入度，記做(v)，簡記作d-(v)，稱d+(v)+d-(v)為v的度數(shù)，記做d(v). 2握手定理 定理14.1(握手定理) 設(shè)G=為任意無向圖，V=v1,v2,vn，|E|=m，那么 =2m 證 G中每條邊(包括環(huán))均有兩個(gè)端點(diǎn)，所以在計(jì)算G中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供2度，當(dāng)然，m條邊，共提供2m度。 定理14.2(握手定理) 設(shè)D=為任意有向圖，V=v1,v2,vn，|E|=m，那么 =2m，且=m. 本定理的證明類似于定理14.1 握手定理的推論 任何圖(無向的或有向的)中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù)。 證 設(shè)G=為任意一圖，令 V1=v|

10、vVd(v)為奇數(shù) V2=v|vVd(v)為偶數(shù) 那么V1V2=V，V1V2=，由握手定理可知 2m=+ 由于2m，均為偶數(shù)，所以為偶數(shù)，但因V1中頂點(diǎn)數(shù)為奇數(shù)，所以|V1|必為偶數(shù)。 握手定理也稱為圖論的根本定理，圖中頂點(diǎn)的度數(shù)是圖論中最為根本的概念之一。 下面給出與頂點(diǎn)度數(shù)有關(guān)的概念。 1無向圖G中的最大度和最小度 在無向圖G中，令 (G)=maxd(v)|vV(G)(G)=mind(v)|vV(G)稱(G)，(G)分別為G的最大度 和最小度。 在不引起混淆的情況下，將(G)，(G)分別簡記為和. 2有向圖D中的最大度、最大出度、最大入度與最小度、最小出度、最小入度 在有向圖D中，類似無向

11、圖，可以定義最大度(D)，最小度(D)，另外，令 +(D)=maxd+(v)|vV(D)+(D)=mind+(v)|vV(D)-(D)=maxd-(v)|vV(D)-(D)=mind-(v)|vV(D)分別稱為D的最大出度，最小出度， 最大入度，最小入度。 以上記號可分別簡記為 ，+，+，-，-.3懸掛頂點(diǎn)與懸掛邊；奇度頂點(diǎn)與偶度頂點(diǎn) 稱度數(shù)為1的頂點(diǎn)為懸掛頂點(diǎn)，與它關(guān)聯(lián)的邊稱為懸掛邊。度為偶數(shù)(奇數(shù))的頂點(diǎn)稱為偶度(奇度)頂點(diǎn)。 在圖14.1中，(1)的d(v1)=4(注意，環(huán)提供2度)，= 4，= 1，v4是懸掛頂點(diǎn)，e7是懸掛邊。(2)的d+(a)=4，d-(a)=1(環(huán)e1提供出度1，

12、提供入度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á))。 4度數(shù)列 設(shè)G=為一個(gè)n階無向圖,V=v1,v2,vn,稱d(v1),d(v2),d(vn)為G的度數(shù)列，對于頂點(diǎn)標(biāo)定的無向圖，它的度數(shù)列是唯一的。 設(shè)D=為一個(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的出度列和入度列。 在圖14.1(1)中，按頂點(diǎn)的標(biāo)定順序，度數(shù)列為4,4,2,1,3.在(2)中，按字母順序，度

13、數(shù)列，出度列，入度列分別為5,3,3,3；4,0,2,1；1,3,1,2.5可圖化的與可簡單圖化的非負(fù)整數(shù)列 對于給定的非負(fù)整數(shù)列d=(d1,d2,dn)，假設(shè)存在以V=v1,v2,vn為頂點(diǎn)集的n階無向圖G，使得d(vi)=di，那么稱d是可圖化的。特別地，假設(shè)所得圖是簡單圖，那么稱d是可簡單圖化的。 d=(d1,d2,dn)是否為可圖化的，可由下面定理判別。 定理14.3 設(shè)非負(fù)整數(shù)列d=(d1，d2，dn)，那么d是可圖化的當(dāng)且僅當(dāng) =0(mod 2). 證 由 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter

14、14/14_01_04_01.htm l wsdl 握手定理可知必然性顯然。下面證明充分性。由條件可知，d中有2k(0k )個(gè)奇數(shù)，不妨設(shè)它們?yōu)?d1，d2，dk，dk+1，dk+2，d2k. 可用多種方法做出n階無向圖G=，V= v1，v2，vn.比方邊集如下產(chǎn)生：在頂點(diǎn)vr與vr+k之間連邊，r=1，2，k.假設(shè)di為偶數(shù)，令 di=di，假設(shè)di為奇數(shù)，令di=di1，得d=(d1，d2，dn)，那么di均為偶數(shù)。再在vi處做出di/2條環(huán)，i=1，2，n，將所得各邊集合在一起組成E，那么G的度數(shù)列為d. 其實(shí)，di為偶數(shù)時(shí)，d(vi)=2di/2=2di/2=di，當(dāng)di為奇數(shù)時(shí)，d(

15、vi)=1+2di/2=1+di=1+di1=di ，這就證明了d是可圖化的。 由定理14.3立即可知，(3，3，2，1)，(3，2，2，1，1)等是不可圖化的，而(3，3，2，2)，(3，2，2，2，1)等是可圖化的。 定理14.4 設(shè)G為任意n階無向簡單圖，那么(G)n-1. 證 因?yàn)镚既無 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_03_01.htm l dy14_3 平行邊也無 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part

16、5/chapter14/14_01_02_01.htm l 6 環(huán)，所以G中任何頂點(diǎn)v至多與其余的n-1個(gè)頂點(diǎn)均相鄰，于是d(v)n-1，由于v的任意性，所以(G)n-1. 有了 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_06_01.htm l dl14_3 定理14.3，判某非負(fù)整數(shù)列是否可圖化就很簡單了，但判是否可簡單圖化的，還是不太容易的，定理14.4還是起很大作用的。下例還能提供一些其他方法。 例142 判斷以下各非負(fù)整數(shù)列哪些是 HYPERLINK :/4a.hep :8088/NC

17、ourse/lssxq/courseware/part5/chapter14/14_01_05_02.htm l 5 t _blank 可圖化的？哪些是 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_05_02.htm l 5 t _blank 可簡單圖化的？ (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)中序列不可圖化外，其余各序列都可圖化。但除

18、了(5)中序列外，其余的都是不可簡單圖化的。(2)中序列有5個(gè)數(shù)，假設(shè)它可簡單圖化，設(shè)所得圖為G，那么(G)=max5,4,3,2,2=5，這與定理14.4矛盾。所以(2)中序列不可簡單圖化。類似可證(4)中序列不可簡單圖化。 假設(shè)(3)中序列可以簡單圖化，設(shè)G=以(3)中序列為度數(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)中序列也不可簡單圖化。 (5)中序列是可簡單圖化的，圖14.2中兩個(gè)6階無向簡單圖都以(5)中序列

19、為度數(shù)列。 四圖的同構(gòu) 1兩圖同構(gòu)的定義 定義14.5 設(shè)G1=，G2=為兩個(gè)無向圖(兩個(gè)有向圖)，假設(shè)存在雙射函數(shù)f：V1V2，對于vi，vj V1，(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 . 在圖14.3中，(1)為彼得松(Petersen)圖，(2)，(3)均與(1)同構(gòu)。(4)，(5)，(6)各圖彼此間都不同構(gòu)。 2圖之間的同構(gòu)關(guān)系是等價(jià)關(guān)系 圖之間的同構(gòu)關(guān)系可看成全體圖集合上的二元關(guān)系，這個(gè)二元關(guān)系具有自反性，對稱性和傳遞性，因而它是等價(jià)關(guān)系。在這個(gè)

20、等價(jià)關(guān)系的每一等價(jià)類中均取一個(gè)非標(biāo)定圖作為一個(gè)代表，凡與它同構(gòu)的圖，在同構(gòu)的意義之下都可以看成一個(gè)圖，在圖14.3中，(1)，(2)，(3)可以看成一個(gè)圖，它們都是彼得松圖，其中的(1)可看成這類圖的代表。提到 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_08_01.htm l petersen 彼得松圖，一般是指(1)中圖。 至此，可以這樣說，在圖同構(gòu)的意義下，圖的數(shù)學(xué)定義與圖形表示是一一對應(yīng)的。 關(guān)于圖之間的同構(gòu)問題還應(yīng)該指出以下兩點(diǎn)： a到目前為止，人們還沒有找到判斷兩個(gè)圖是否同構(gòu)的好的算

21、法，還只能根據(jù)定義看是否能找到滿足條件的雙射函數(shù)，顯然這是困難的。 b需要注意的是，不要將兩個(gè)圖同構(gòu)的必要條件當(dāng)成充分條件。假設(shè)G1G2，那么它們的階數(shù)相同，邊數(shù)相同，度數(shù)列相同，等等。破壞這些必要條件的任何一個(gè)，兩個(gè)圖就不會(huì)同構(gòu)，但以上列出的條件都滿足，兩個(gè)圖也不一定同構(gòu)，在圖14.2中的兩個(gè)圖，有相同的度數(shù)列，但它們不同構(gòu)。五完全圖與正那么圖 1完全圖 定義14.6 設(shè)G為n階無向 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_03_01.htm l dy14_3 簡單圖，假設(shè)G中每個(gè)頂點(diǎn)均與

22、其余的n-1個(gè)頂點(diǎn)相鄰， 那么稱G為n階無向完全圖，簡稱n階完全圖，記做Kn(n1)。 設(shè)D為n階有向簡單圖，假設(shè)D中每個(gè)頂點(diǎn)都鄰接到其余的n-1個(gè)頂點(diǎn)，又鄰接于其余的n-1個(gè)頂點(diǎn)， 那么稱D是n階有向完全圖。 設(shè)D為n階有向簡單圖，假設(shè)D的基圖為n階無向完全圖Kn ，那么稱D是n階競賽圖。 在圖14.4中，(1)為K5，(2)為3階有向完全圖，(3)為4階競賽圖。 圖14.4易知，n階無向完全圖，n階有向完全圖，n階競賽圖的邊數(shù)分別為 n(n-1)/2，n(n1)，n(n-1)/2.2正那么圖 定義14.7 設(shè)G為n階無向簡單圖，假設(shè)vV(G)，均有d(v)=k，那么稱G為k-正那么圖。 由

23、定義可知，n階零圖是0-正那么圖， HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_09_01.htm l dy14_6#dy14_6 n階無向完全圖是(n-1)正那么圖，彼得松圖是3-正那么圖。 由 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_04_01.htm l wsdl 握手定理可知，n階k-正那么圖中，邊數(shù)m=kn/2，因而當(dāng)k為奇數(shù)時(shí)，n必為偶數(shù)六子圖與補(bǔ)圖 1子圖 定義14.8 設(shè)G=，

24、G=為兩個(gè)圖(同為無向圖或同為有向圖)，假設(shè)VV且EE，那么稱G是G的子圖，G為G的母圖，記作GG. 又假設(shè)VV或EE，那么稱G為G的真子圖。假設(shè)V=V，那么稱G為G的生成子圖。 設(shè)G=為一圖，V1V且V1，稱以V1為頂點(diǎn)集，以G中兩個(gè)端點(diǎn)都在V1中的邊組成邊集E1的圖為G的V1導(dǎo)出的子圖，記作GV1. 又設(shè)E1E且E1，稱以E1為邊集，以E1中邊關(guān)聯(lián)的頂點(diǎn)為頂點(diǎn)集V1的圖為G的E1導(dǎo)出的子圖，記作GE1. 在圖14.5中，設(shè)G為(1)中圖所表示，取V1=a，b，c，那么V1的導(dǎo)出子圖GV1為(2)中圖所示。取E1=e1，e3，那么E1的導(dǎo)出子圖GE1為(3)中圖所示。圖14.5對于給定的正整

25、數(shù)n和m(mn(n-1)/2)，構(gòu)造出所有非同構(gòu)的n階m條邊的所有非同構(gòu)的無向(有向)簡單圖，這是目前還沒有解決的難題，但對于比擬小的n還是能構(gòu)造出來的。 例143 (1) 畫出4階3條邊的所有非同構(gòu)的無向 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_03_01.htm l dy14_3 簡單圖。(2) 畫出3階2條邊的所有非同構(gòu)的有向簡單圖。 解 (1)由 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_

26、01_04_01.htm l wsdl 握手定理可知，所畫的無向簡單圖各頂點(diǎn)度數(shù)之和為23=6，最大度小于或等于3。于是所求無向簡單圖的度數(shù)列應(yīng)滿足的條件是，將6分成4個(gè)非負(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)的圖，見圖14.6中(1)，(2)，(3). (2) 由握手定理可知，所畫有向簡單圖各頂點(diǎn)度數(shù)之和為4，最大出度和最大入度均小于或等于2.度數(shù)列及入度出度列為 (a) 1，2，1(b) 2，2，0

27、 四個(gè)所要求的有向簡單圖見圖14.6中(4)，(5)，(6)，(7).圖14.6其中3個(gè)無向圖都是 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_09_01.htm l dy14_6 K4的子圖，而且是 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_10_01.htm l dy14_8 生成子圖，4個(gè)有向圖都是3階 HYPERLINK :/4a.hep :8088/NCourse/lssxq/cour

28、seware/part5/chapter14/14_01_09_01.htm l dy14_6 有向完全圖的生成子圖。 試問K4的所有非同構(gòu)的i(i=0，1，2，4，5，6)條邊的生成子圖各有幾個(gè)？ 定義14.9 設(shè)G=為無向圖。(1) 設(shè)eE，從G中去掉邊e，稱為刪除e，并用G-e表示從G中刪除e所得子圖。又設(shè)EE，從G中刪除E中所有的邊，稱為刪除E，并用G-E表示刪除E后所得子圖。(2) 設(shè)vV，從G中去掉v及所關(guān)聯(lián)地一切邊稱為刪除頂點(diǎn)v，并用G-v表示刪除v后所得子圖。又設(shè)VV，稱從G中刪除V中所有頂點(diǎn)為刪除V，并用G-V表示所得子圖。(3) 設(shè)邊e=(u，v)E，先從G中刪除e，然后將

29、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，并用Ge表示所得新圖。(4) 設(shè)u，vV(u，v可能相鄰，也可能不相鄰，且uv)，在u，v之間加新邊(u，v)，稱為加新邊，并用G(u，v) (或G(u，v)表示所得新圖。在收縮邊和加新邊過程中可能產(chǎn)生 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_02_01.htm l 6 環(huán)和 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5

30、/chapter14/14_01_03_01.htm l dy14_3 平行邊。 在圖14.7中，設(shè)(1)中圖為G，那么(2)為G-e5，(3)為G-e1，e5，(4)為G-v5 ，(5)為G-v4,v5，而(6)為Ge5. 圖14.72補(bǔ)圖與自補(bǔ)圖 定義14.10 設(shè)G=為n階無向簡單圖，以V為頂點(diǎn)集，以所有使G成為 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_09_01.htm l dy14_6 完全圖Kn的添加邊組成的集合為邊集的圖，稱為G的補(bǔ)圖，記做. 假設(shè)圖 HYPERLINK :/4

31、a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_08_01.htm l dy14_5 G，那么稱G是自補(bǔ)圖。 14.2 通路與回路 一通路與回路的定義 定義14.11 設(shè)G為無向標(biāo)定圖，G中頂點(diǎn)與邊的交替序列=稱為到的通路，其中，為的端點(diǎn)，r=1，2，l，分別稱為的始點(diǎn)與終點(diǎn)，中邊的條數(shù)稱為它的長度。假設(shè)，那么稱通路為回路。 假設(shè)的所有邊各異，那么稱為簡單通路，又假設(shè)，那么稱為簡單回路。假設(shè)的所有頂點(diǎn)(除與可能相同外)各異，所有邊也各異，那么稱為初級通路或路徑，此時(shí)又假設(shè)，那么稱為初級回路或圈。將長度為奇數(shù)的圈稱為奇圈，長度

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

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

34、以子圖形式畫出它們。 解：(1)長度為1的圈有1個(gè)，記為C11，C11只能用定義或 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_02_01_01.htm l mix 混合表示法表示： C11=Ae1A，以子圖形式畫出為一個(gè)圖：演示1 長度為2的圈在定義意義下有兩個(gè)，記為C21和C22，它們各可以有兩種表示法： C21 = ADA頂點(diǎn)序列表示= Ae3De2A用定義表示C22 = DAD頂點(diǎn)序列表示= De2Ae3D用定義表示顯然C21C22，以子圖形式畫出時(shí)，它們是一個(gè)子圖：演示2 長度為3的圈在定義

35、意義下有6個(gè)，分別記為C3i，i=1,2,3,4,5,6.這里只寫出以A為始(終點(diǎn))的兩個(gè)： C31 = ABe7CA 混合表示法C32 = ABe8CA 混合表示法顯然C3iC3j，i,j=1,2,6，以子圖形式畫出時(shí)，它們是兩個(gè)子圖：演示3 長度為4的圈在定義意義下有8個(gè)，分別記為C4i，i=1,2,8.這里只畫出以D為始(終點(diǎn))的兩個(gè)。 C41 = DABe7CD 混合表示法C42 = DABe8CD 混合表示法易知C4iC4j，i,j=1,2,8,以子圖形式畫出時(shí)，它們是兩個(gè)圖：演示4 (2)長度為3的非初級的簡單回路在定義意義下有3條，以A為始(終點(diǎn))的2條(先經(jīng)過e1與后經(jīng)過e1各

36、一條)，以D為始(終點(diǎn))的為1條。它們均同構(gòu)。畫出來只有一個(gè)圖形：演示5 長度為4的非初級的簡單回路在定義意義下有8條，它們均為同構(gòu)的，畫出來的圖形有兩個(gè)一個(gè)含e7，一個(gè)含e8：演示6 長度為5的非初級的簡單回路在定義意義下有20條，它們均同構(gòu)，畫出的圖形有4個(gè)：演示7 長度為6的非初級的簡單回路在定義意義下有24個(gè)，它們均同構(gòu)，畫出的圖形有兩個(gè)：演示8 二. n階圖中通路與回路的性質(zhì) 定理14.5 在n階圖G中，假設(shè)從頂點(diǎn)vi到vjvivj存在通路，那么從vi到vj存在長度小于或等于n-1的通路。 證：設(shè)=v0e1v1e2elvlv0=vi,vl=vj為G中一條長度為l的通路，假設(shè)ln-1，

37、那么滿足要求，否那么必有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,仍為vi到vj的通路，且長度至少比減少1。假設(shè)還不滿足要求，那么重復(fù)上述過程，由于G是有限圖，經(jīng)過有限步后，必得到vi到vj長度小于或等于n-1的通路。 推論 在n階圖G中，假設(shè)從頂點(diǎn)vi到vjvivj存在通路，那么vi到vj一定存在長度小于或等于n-1的初級通路路徑。 由定理14.5，本推論自然成立。 類似可證明下面的定理和推論。 定理14.6 在一個(gè)n階圖G中

38、，假設(shè)存在vi到自身的回路，那么一定存在vi到自身長度小于或等于n的回路。 推論 在一個(gè)n階圖G中，假設(shè)存在vi到自身的簡單回路，那么一定存在vi到自身長度小于或等于n的初級回路。 例14.5 (1) 無向完全圖Knn3中有幾種非同構(gòu)的圈？ (2) 無向完全圖K3的頂點(diǎn)依次標(biāo)定為a,b,c.在定義意義下K3中有多少個(gè)不同的圈？解 (1) 長度相同的圈都是同構(gòu)的，因而只有長度不同的圈才是非同構(gòu)的，易知Knn3中含長度為3，4，n的圈，所以Knn3中有n-2種非同構(gòu)的圈。 (2) 在同構(gòu)意義下，K3中只有一個(gè)長度為3的圈。但在定義意義下，不同起點(diǎn)終點(diǎn)的圈是不同的，頂點(diǎn)間排列順序不同的圈也看成是不同

39、的， 因而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 圖的連通性 一、無向圖的連通性 定義14.12 設(shè)無向圖G=,u,vV，假設(shè)u,v之間存在通路，那么稱u,v是連通的，記作uv. vV，規(guī)定vv. 由定義不難看出，無向圖中頂點(diǎn)之間的連通關(guān)系 =u,v|u,vV且u與v之間有通路是自反的，對稱的，傳遞的，因而是V上的等價(jià)關(guān)系。 定義14.13 假設(shè)無向圖G是平凡圖或G中任何兩個(gè)頂點(diǎn)都是連通的，那么稱G為連通圖，否那么稱G是非連通

40、圖或別離圖。 易知，完全圖Kn(n1)都是連通圖，而 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_02_01.htm l 3 零圖Nn(n2)都是別離圖。 定義14.14 設(shè)無向圖G=，V關(guān)于頂點(diǎn)之間的連通關(guān)系的商集V/=V1,V2,Vk，Vi為等價(jià)類，稱 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_10_01.htm l dy14_8 導(dǎo)出子圖GVi(i=1,2,k)為G的連通分支，連通分支數(shù)k

41、常記為p(G). 由定義可知，假設(shè)G為連通圖，那么p(G)=1，假設(shè)G為非連通圖，那么p(G)2，在所有的n階無向圖中，n階零圖是連通分支最多的，p(Nn)=n. 二、無向圖中頂點(diǎn)之間的短程線及距離 定義14.15 設(shè)u,v為無向圖G中任意兩個(gè)頂點(diǎn)，假設(shè)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

42、)中，任何兩個(gè)頂點(diǎn)之間的距離都是1，而在n階零圖Nn(n2)中，任何兩個(gè)頂點(diǎn)之間的距離都為. 三、無向圖的連通度 定義14.16 設(shè)無向圖G=，假設(shè)存在VV，且V，使得p(G-V)p(G)，而對于任意的VV，均有p(G-V)=p(G)，那么稱V是G的點(diǎn)割集，假設(shè)V是單元集，即V=v，那么稱v為割點(diǎn)。 圖14.8 在圖14.8中，v2,v4，v3，v5都是點(diǎn)割集，而v3,v5都是割點(diǎn)。注意，v1與 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_05_01.htm l 3 懸掛頂點(diǎn)v6不在任何割集中。

43、 定義14.17 設(shè)無向圖G=，假設(shè)存在EE，且E，使得p(G-E)p(G)，而對于任意的EE，均有p(G-E)=p(G)，那么稱E是G的邊割集，或簡稱為割集。假設(shè)E是單元集，即E=e，那么稱e為割邊或橋。 在圖14.8中，e6,e5,e2,e3,e1,e2,e3,e4,e1,e4,e1,e3,e2,e4都是割集，其中e6,e5是橋。 定義14.18 設(shè)G為無向連通圖且為非完全圖，那么稱 (G)=min|V|V為G的點(diǎn)割集為G的點(diǎn)連通度，簡稱連通度。規(guī)定完全圖Kn(n1)的點(diǎn)連通度為n-1，又規(guī)定非連通圖的點(diǎn)連通度為0.又假設(shè)(G)k，那么稱G是k-連通圖，k為非負(fù)整數(shù)。 (G)有時(shí)簡記為.圖

44、14.8中圖的點(diǎn)連通度為1，此圖為1-連通圖。K5的點(diǎn)連通度=4，所以K5是1-連通圖，2-連通圖，3-連通圖，4-連通圖。圖14.7中，1圖的點(diǎn)連通度=2，所以它是1-連通圖，也是2-連通圖。假設(shè)G是k-連通圖k1那么在G中刪除任何k-1個(gè)頂點(diǎn)后，所得圖一定還是連通的。 定義14.19 設(shè)G是無向連通圖，稱 (G)=min|E| E是G的點(diǎn)割集為G的邊連通度。規(guī)定非連通圖的邊連通度為0.又假設(shè)(G)r，那么稱G是r邊-連通圖。 假設(shè)G是r邊-連通圖，那么在G中任意刪除r-1條邊后，所得圖依然是連通的。完全圖Kn的邊連通度為n-1，因而Kn是r邊-連通圖，0rn-1.圖14.8中圖的邊連通度=

45、1，它只能是1邊-連通圖。(G)也可以簡記為. 設(shè)G1,G2都是n階無向簡單圖，假設(shè)(G1)(G2)，那么稱G1比G2的點(diǎn)連通程度高。假設(shè)(G1)(G2)，那么稱G1比G2的邊連通程度高。例14.6 求圖14.9所示各圖的點(diǎn)連通度，邊連通度，并指出它們各是幾連通圖及幾邊連通圖。最后將它們按點(diǎn)連通程度及邊連通程度排序。 圖14.9解 設(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. 1是k-連通圖，k邊-連通圖，k=1,2,3,4.2是k-連通圖，k邊-連通圖，k=1,2,3.3

46、是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)連通程度為123=64=57=8.邊連通程度為123=5=647=8.定理14.7 對于任何無向圖G，有 (G)(G)(G)本定理證明略。例14.7 1給出一些無向簡單圖，使得=.2給出一些無向簡單圖，使得. 解 1n階無向完全圖Kn和n階零圖Nn都滿足要求。 2在兩個(gè)Knn4之間放置一個(gè)頂點(diǎn)v，使v與兩個(gè)Kn中的每一個(gè)的任意兩個(gè)不同的頂點(diǎn)相鄰，所得簡單圖滿足要求。因?yàn)檫@樣的圖中有

47、一個(gè)割點(diǎn)，所以點(diǎn)連通度為1，又因?yàn)闊o橋，而有兩條邊組成的邊割集，所以邊連通度為2，當(dāng)n=4時(shí)，=3，當(dāng)n5時(shí)，=4.圖14.10中，給出了n=4和n=5的情況。 圖14.10四、有向圖的連通性及其分類 定義14.20 設(shè)D=為一個(gè)有向圖。vi,vjV，假設(shè)從vi到vj存在通路，那么稱vi可達(dá)vj，記作vivj，規(guī)定vi總是可達(dá)自身的，即vivi.假設(shè)vivj且vjvi，那么稱vi與vj是相互可達(dá)的，記作vivj.規(guī)定vivi. 與都是V上的二元關(guān)系，并且不難看出是V上的等價(jià)關(guān)系。 定義14.21 設(shè)D=為有向圖，vi,vjV，假設(shè)vivj，稱vi到vj長度最短的通路為vi到vj的短程線，短程線

48、的長度為vi到vj的距離，記作d. 與無向圖中頂點(diǎn)vi與vj之間的距離d(vi,vj)相比，d除無對稱性外，具有d(vi,vj)所具有的一切性質(zhì)。 定義14.22 設(shè)D=為一個(gè)有向圖。假設(shè)D的 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_02_01.htm l 5 基圖是連通圖，那么稱D是弱連通圖，簡稱為連通圖。假設(shè)vi,vjV ，vivj與vjvi至少成立其一，那么稱D是單向連通圖。假設(shè)均有vivj，那么稱D是強(qiáng)連通圖。 圖14.11在圖14.11中，1為強(qiáng)連通圖，2為單連通圖，3是弱連通圖。

49、由定義可知，強(qiáng)連通圖一定是單向連通圖，單向連通圖一定是弱連通圖。 下面給出強(qiáng)連通圖與單向連通圖的判別定理。 定理14.8 設(shè)有向圖D=，D=v1,v2,vn.D是強(qiáng)連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的回路。 證 充分性顯然。下面證明必要性。由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)至少一次。 定理14.9 設(shè)D是n階有向圖，D是單向連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的通路。 證明略。 五、擴(kuò)大路徑法及極大路徑 設(shè)G=為n階無向圖，E，設(shè)l為G中一條路

50、徑，假設(shè)此路徑的始點(diǎn)或終點(diǎn)與通路外的頂點(diǎn)相鄰，就將它們擴(kuò)到通路中來，繼續(xù)這一過程，直到最后得到的通路的兩個(gè)端點(diǎn)不與通路外的頂點(diǎn)相鄰為止，設(shè)最后得到的通路的兩個(gè)端點(diǎn)不與通路外的頂點(diǎn)相鄰為止，設(shè)最后得到的路徑為l+k長度為l的路徑擴(kuò)大成了長度為l+k的路徑，稱l+k為“極大路徑，稱使用此種方法證明問題的方法為“擴(kuò)大路徑法。演示 例14.8 設(shè)G為nn4階無向簡單圖，(G)3.證明G中存在長度大于或等于4的圈。 證 不妨設(shè)G是連通圖，否那么，因?yàn)镚的各連通分支的最小度也都大于或等于3，因而可對它的某個(gè)連通分支進(jìn)行討論。設(shè)u,v為G中任意兩個(gè)頂點(diǎn)，由G是連通圖，因而u,v之間存在通路，由 HYPERL

51、INK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_02_03_01.htm l dl14_5 定理14.5的推論可知，u,v之間存在路徑，用“擴(kuò)大路徑法擴(kuò)大這條路徑，設(shè)最后得到的“極大路徑為l=v0v1vl，易知l3.假設(shè)v0與v1相鄰，那么l(v0,vl)為長度大于或等于4的圈。否那么，由于d(v0)(G)3，因而v0除與l上的v1相鄰?fù)?，還存在l上的頂點(diǎn)vk(k1)和vt(ktl)與v0相鄰，那么v0v1vkvtv0為一個(gè)圈且長度大于或等于4，見圖14.12. 圖14.12類似地，在有向圖中也可以利用“擴(kuò)大路徑法構(gòu)

52、造圖中的“極大路徑。 六、二部圖及判別定理 定義14.23 設(shè)G=為一個(gè)無向圖，假設(shè)能將V分成V1和V2V1V2=V,V1V2=，使得G中的每條邊的兩個(gè)端點(diǎn)都是一個(gè)屬于V1，另一個(gè)屬于V2，那么稱G為二部圖或稱二分圖，偶圖等，稱V1和V2為互補(bǔ)頂點(diǎn)子集，常將二部圖G記為.又假設(shè)G是簡單二部圖，V1中每個(gè)頂點(diǎn)均與V2中所有頂點(diǎn)相鄰，那么稱G為完全二部圖，記為Kr,s，其中r=|V1|,s=|V2|. 注意，n階零圖為二部圖。 在圖14.13中所示各圖都是二部圖，其中，(1)，(2)，(3)為K6的子圖，(3)為完全二部圖K3,3，常將K3,3畫成與其同構(gòu)的(5)的形式，K3,3是下文中經(jīng)常遇到的

53、圖。(4)是K5的子圖，它是完全二部圖K2,3，K2,3常畫成(6)的形式。 圖14.13一個(gè)圖是否為二部圖，可由下面定理判別。 14.4 圖的矩陣表示 一、無向圖與有向圖的關(guān)聯(lián)矩陣 圖可以用集合來定義，但多半用圖形來表示，此外，還可以用矩陣來表示圖。用矩陣表示圖，便于用代數(shù)方法研究圖的性質(zhì)，也便于計(jì)算機(jī)處理圖。用矩陣表示圖之前，必須將圖的頂點(diǎn)或邊標(biāo)定順序，使其成為標(biāo)定圖。本節(jié)中主要討論無向圖及有向圖的關(guān)聯(lián)矩陣及有向圖的鄰接矩陣和可達(dá)矩陣。 定義14.24 設(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)矩陣，記作M

54、(G). 圖14.14圖14.14所示無向圖的關(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é)果正是 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_04_01.htm l wsdl 握手定理的內(nèi)容，即各頂點(diǎn)的度數(shù)之和等于邊數(shù)的2倍。 4 第j列

55、與第k行相同，當(dāng)且僅當(dāng)邊ej與ek是 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_03_01.htm l dy14_3 平行邊。 5 mij=0當(dāng)且僅當(dāng)vi是 HYPERLINK :/4a.hep :8088/NCourse/lssxq/courseware/part5/chapter14/14_01_02_01.htm l 6 孤立點(diǎn)。 定義14.25 設(shè)有向圖D=中無環(huán)，V=v1,v2,vn，E=e1,e2,em,令 mij= 那么稱(mij)nm為D的關(guān)聯(lián)矩陣，記作M(D). 圖14.15圖14.15所示圖D的關(guān)聯(lián)矩陣為 M(D)=M(D)有如下各條性質(zhì)： 1mij=0，j=1,2,m，從而 mij =0，這說明M(D)中所有元素之和為0. 2M(D)中，負(fù)1的個(gè)數(shù)等于正1的個(gè)數(shù)，都等于邊數(shù)m，這正是有向圖握手定理的內(nèi)容。 3第i行中，正1的個(gè)數(shù)等于d+(vi)，負(fù)1的個(gè)數(shù)等于d-(vi). 4平行邊所對應(yīng)的列相同。 二、有向圖的鄰接矩陣 定義14.26 設(shè)有向圖D