圖的基本概念ppt課件

1、1第十四章圖的根本概念第十四章圖的根本概念第四部分：圖論第四部分：圖論2七橋問題七橋問題q問題問題q尋覓走遍哥尼斯堡尋覓走遍哥尼斯堡Knigsberg城的城的7座橋，且只許走過每座橋一座橋，且只許走過每座橋一次，最后又回到原出發(fā)點(diǎn)次，最后又回到原出發(fā)點(diǎn)q求解求解q1736年瑞士大數(shù)學(xué)家歐拉年瑞士大數(shù)學(xué)家歐拉LeonhardEuler發(fā)表了關(guān)于發(fā)表了關(guān)于“哥尼斯堡七橋問題的論文哥尼斯堡七橋問題的論文圖論的第一篇論文。他指出圖論的第一篇論文。他指出從一點(diǎn)出發(fā)不反復(fù)的走遍七橋，從一點(diǎn)出發(fā)不反復(fù)的走遍七橋，最后又回到原來出發(fā)點(diǎn)是不能夠最后又回到原來出發(fā)點(diǎn)是不能夠的。的。3圖論圖論 圖論是近年來開展迅速

2、而又運(yùn)用廣泛的一圖論是近年來開展迅速而又運(yùn)用廣泛的一門新興學(xué)科。它最早來源于一些數(shù)學(xué)游戲的門新興學(xué)科。它最早來源于一些數(shù)學(xué)游戲的難題研討，如難題研討，如1736年歐拉年歐拉L.Euler)所處理所處理的哥尼斯堡七橋問題。以及在民間廣為流傳的哥尼斯堡七橋問題。以及在民間廣為流傳的一些游戲問題：例如迷宮問題、棋盤上馬的一些游戲問題：例如迷宮問題、棋盤上馬的行走道路問題的行走道路問題4棋盤上馬的行走道路問題棋盤上馬的行走道路問題q 在中國象棋中，馬走在中國象棋中，馬走“日字，即每步從日字，即每步從 12 矩形的一矩形的一個(gè)頂點(diǎn)跳到相對的頂點(diǎn)。如圖，馬從個(gè)頂點(diǎn)跳到相對的頂點(diǎn)。如圖，馬從M3，2一次只一

3、次只能跳到能跳到A、B、C、D、E、F、G、H中的任何一個(gè)位置中的任何一個(gè)位置。q 問題：馬能否從棋盤上恣意一點(diǎn)出發(fā)，不反復(fù)、不脫漏問題：馬能否從棋盤上恣意一點(diǎn)出發(fā)，不反復(fù)、不脫漏地走遍整個(gè)棋盤即每一點(diǎn)都走到并且只到一次？地走遍整個(gè)棋盤即每一點(diǎn)都走到并且只到一次？ 5棋盤上馬的行走道路問題棋盤上馬的行走道路問題q 將馬目前所在位置涂成白色，用涂色的方法，將棋盤上的點(diǎn)分為黑、白相間的兩類6周游世界各國的問題周游世界各國的問題q 英國數(shù)學(xué)家哈密頓于1859年以游戲的方式提出：把一個(gè)正十二面體的二十個(gè)頂點(diǎn)看成二十個(gè)城市，要求找出一條經(jīng)過每個(gè)城市恰好一次而回到出發(fā)點(diǎn)的道路。這條道路就稱“哈密頓圈。一百

4、多年來，對哈密頓問題的研討，促進(jìn)了圖論的開展。 7四色猜測四色猜測q問題：任何一張地圖只用問題：任何一張地圖只用四種顏色就能使具有共同四種顏色就能使具有共同邊境的國家著上不同的顏邊境的國家著上不同的顏色色q用數(shù)學(xué)言語表示，即：用數(shù)學(xué)言語表示，即：“將平面恣意地細(xì)分為不相將平面恣意地細(xì)分為不相重疊的區(qū)域，每一個(gè)區(qū)域重疊的區(qū)域，每一個(gè)區(qū)域總可以用總可以用1，2，3，4這四這四個(gè)數(shù)字之一來標(biāo)志，而不個(gè)數(shù)字之一來標(biāo)志，而不會(huì)使相鄰的兩個(gè)區(qū)域得到會(huì)使相鄰的兩個(gè)區(qū)域得到一樣的數(shù)字一樣的數(shù)字 8圖論圖論q圖論不斷開展，它在處理運(yùn)籌學(xué)，網(wǎng)絡(luò)圖論不斷開展，它在處理運(yùn)籌學(xué)，網(wǎng)絡(luò)實(shí)際，信息論，控制論，博奕論以及計(jì)實(shí)

5、際，信息論，控制論，博奕論以及計(jì)算機(jī)科學(xué)等各個(gè)領(lǐng)域的問題時(shí)，顯示出算機(jī)科學(xué)等各個(gè)領(lǐng)域的問題時(shí)，顯示出越來越大的作用越來越大的作用9第十四章圖的根本概念第十四章圖的根本概念 第一節(jié)：圖第一節(jié)：圖 第二節(jié)：通路、回路、圖的連通性第二節(jié)：通路、回路、圖的連通性第三節(jié)：圖的矩陣表示和運(yùn)算第三節(jié)：圖的矩陣表示和運(yùn)算 10第一節(jié)：圖第一節(jié)：圖q 無序積：設(shè)無序積：設(shè)A，B為恣意的兩個(gè)集合，稱為恣意的兩個(gè)集合，稱q a,b | aA且且bBq 為為A與與B的無序積，記做的無序積，記做A&Bq 無向圖：一個(gè)無向圖無向圖：一個(gè)無向圖G是一個(gè)二重組是一個(gè)二重組, 其其中中V(G)為有限非空結(jié)點(diǎn)或叫頂點(diǎn)集合

6、為有限非空結(jié)點(diǎn)或叫頂點(diǎn)集合, E(G)是邊是邊的集合，它是無序積的集合，它是無序積V&V的多重子集，其元素為無的多重子集，其元素為無向邊，簡稱邊。向邊，簡稱邊。q 有向圖：一個(gè)有向圖有向圖：一個(gè)有向圖G是一個(gè)二重組是一個(gè)二重組, 其其中中V(G)為有限非空結(jié)點(diǎn)或叫頂點(diǎn)集合為有限非空結(jié)點(diǎn)或叫頂點(diǎn)集合, E(G)是邊是邊的集合，它是笛卡兒乘積的集合，它是笛卡兒乘積VV的多重子集，其元素的多重子集，其元素為有向邊，簡稱邊。為有向邊，簡稱邊。q 11下面定義一些專門名詞：下面定義一些專門名詞：通常用通常用G G表示無向圖，表示無向圖，D D表示有向圖，但表示有向圖，但G G也可以泛也可以泛指圖

7、。指圖。V(G)V(G)，E(G)E(G)分別表示分別表示G G的頂點(diǎn)集和邊集。的頂點(diǎn)集和邊集。|V(G)|,|E(G)|V(G)|,|E(G)|分別表示分別表示G G的頂點(diǎn)數(shù)和邊數(shù)，的頂點(diǎn)數(shù)和邊數(shù)， 假設(shè)假設(shè)|V(G)|V(G)|n n，那么稱，那么稱G G為為n n階圖。階圖。假設(shè)假設(shè)|V(G)|,|E(G)|V(G)|,|E(G)|均為有限數(shù)，那么稱均為有限數(shù)，那么稱G G為有限為有限圖。圖。假設(shè)圖假設(shè)圖G G中，邊集為空，那么稱之為零圖，中，邊集為空，那么稱之為零圖， 假設(shè)假設(shè)G G為為n n階圖，那么稱之為階圖，那么稱之為n n階零圖，記為階零圖，記為NnNn， N1 N1稱為平凡圖

8、。稱為平凡圖。4 4頂點(diǎn)集為空的圖記為空圖。頂點(diǎn)集為空的圖記為空圖。第一節(jié)：圖第一節(jié)：圖12一些定義一些定義5稱頂點(diǎn)或邊用字母標(biāo)定的圖為標(biāo)定圖，否那么稱頂點(diǎn)或邊用字母標(biāo)定的圖為標(biāo)定圖，否那么成為非標(biāo)定圖。另外，將有向邊改為無向邊后的成為非標(biāo)定圖。另外，將有向邊改為無向邊后的圖稱為原圖的基圖。圖稱為原圖的基圖。6設(shè)設(shè)G=為無向圖，為無向圖，ek=(vi,vj)E,那么稱那么稱vi,vj為為ek的端點(diǎn)，的端點(diǎn)， ek與與vi或或ek與與vj是彼此關(guān)聯(lián)的。是彼此關(guān)聯(lián)的。 假設(shè)假設(shè)vivj，那么稱，那么稱ek與與vi或或ek與與vj的關(guān)聯(lián)次數(shù)為的關(guān)聯(lián)次數(shù)為1， 假設(shè)假設(shè)vi=vj，那么稱，那么稱ek與

9、與vi的關(guān)聯(lián)次數(shù)為的關(guān)聯(lián)次數(shù)為2，并稱為，并稱為環(huán)。恣意的環(huán)。恣意的vlV，假設(shè)，假設(shè)vlvi且且vlvj，那么稱，那么稱ek與與vl的關(guān)聯(lián)次數(shù)為的關(guān)聯(lián)次數(shù)為0。13一些定義一些定義7設(shè)無向圖設(shè)無向圖G=，vi,vjV， ek,elE。假。假設(shè)存在設(shè)存在etE，使得，使得et=(vi,vj)，那么稱，那么稱vi與與vj是相是相鄰的。假設(shè)鄰的。假設(shè)ek與與el至少有一個(gè)公共端點(diǎn)，那么稱至少有一個(gè)公共端點(diǎn)，那么稱ek與與el是相鄰的。是相鄰的。 有向圖有向圖D=，vi,vjV，ek,elE 。假設(shè)存。假設(shè)存在在etE，使得，使得et=，那么稱，那么稱vi為為et的始點(diǎn)，的始點(diǎn)，vj為為et的終點(diǎn)，

10、并稱的終點(diǎn)，并稱vi鄰接到鄰接到vj，vj鄰接于鄰接于vi，假，假設(shè)設(shè)ek的終點(diǎn)為的終點(diǎn)為el的始點(diǎn)，那么稱的始點(diǎn)，那么稱ek與與el相鄰。相鄰。14一些定義一些定義8設(shè)無向圖設(shè)無向圖G=，對一切的，對一切的vV稱稱為為v的鄰域，記為的鄰域，記為NG(v)，并稱并稱NG(v) v為為v的閉鄰域，記為的閉鄰域，記為 。稱稱 為為v的關(guān)聯(lián)集，記為的關(guān)聯(lián)集，記為IG(v) 。設(shè)有向圖設(shè)有向圖G=，對一切的，對一切的vV ，稱，稱為為v的后繼元素。稱的后繼元素。稱為為v的先驅(qū)元素。稱兩者之并為的先驅(qū)元素。稱兩者之并為v的鄰域，記為的鄰域，記為ND(v) 。稱稱ND(v) v，v的閉鄰域。的閉鄰域。 |

11、( , )u uVu vEuvGN (v) |e eEev 與 相關(guān)聯(lián) |V,uuv uEuv |,u uVu vEuv 15一些定義一些定義定義定義14.3 在無向圖中，關(guān)聯(lián)一對頂點(diǎn)的無向邊假設(shè)多在無向圖中，關(guān)聯(lián)一對頂點(diǎn)的無向邊假設(shè)多于一條，那么稱這些邊為平行邊，平行邊的條數(shù)稱于一條，那么稱這些邊為平行邊，平行邊的條數(shù)稱為重?cái)?shù)。為重?cái)?shù)。 在有向圖中，關(guān)聯(lián)一對頂點(diǎn)的有向邊假設(shè)多于一條，在有向圖中，關(guān)聯(lián)一對頂點(diǎn)的有向邊假設(shè)多于一條，并且這些邊的始點(diǎn)和終點(diǎn)一樣，那么稱這些邊為平并且這些邊的始點(diǎn)和終點(diǎn)一樣，那么稱這些邊為平行邊。行邊。 含平行邊的圖稱為多重圖，即不含平行邊也不含環(huán)含平行邊的圖稱為多重

12、圖，即不含平行邊也不含環(huán)的圖稱為簡單圖。的圖稱為簡單圖。16一些定義一些定義非多重圖稱為線圖。非多重圖稱為線圖。由定義可見，簡單圖是沒有環(huán)和平行邊的圖。由定義可見，簡單圖是沒有環(huán)和平行邊的圖。 17一些定義一些定義定義定義14.4：在無向圖中，恣意點(diǎn)其作為邊的端點(diǎn)次數(shù)：在無向圖中，恣意點(diǎn)其作為邊的端點(diǎn)次數(shù)之和稱為該點(diǎn)的度數(shù)，記為之和稱為該點(diǎn)的度數(shù)，記為dG(v). 在有向圖中，對于任何結(jié)點(diǎn)在有向圖中，對于任何結(jié)點(diǎn)v，以，以v為始點(diǎn)的邊的條為始點(diǎn)的邊的條數(shù)，稱為結(jié)點(diǎn)數(shù)，稱為結(jié)點(diǎn)v的引出次數(shù)的引出次數(shù)(或出度或出度)，記作，記作d+(v)；以以v點(diǎn)為終點(diǎn)的邊的條數(shù)稱為點(diǎn)為終點(diǎn)的邊的條數(shù)稱為v的引入

13、次數(shù)的引入次數(shù)(或入度或入度)，記作記作d(v)；結(jié)點(diǎn)的；結(jié)點(diǎn)的v的引入次數(shù)和引出次數(shù)之和稱的引入次數(shù)和引出次數(shù)之和稱為為v的次數(shù)度數(shù)，用的次數(shù)度數(shù)，用d (v)表示。表示。由定義可見由定義可見:度數(shù)度數(shù)d (v)d+(v)d(v)。定義：最大度，最小度，最大出度，最大入度，最小定義：最大度，最小度，最大出度，最大入度，最小入度，最小出度，懸掛點(diǎn)，懸掛邊入度，最小出度，懸掛點(diǎn)，懸掛邊18例例1例：例： d (a)(引入引入)+(引出引出)=5 db dc d1 d2 d3 以后為了表達(dá)方便，以后為了表達(dá)方便，我們將具有我們將具有n個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)和和m條邊的圖簡稱為條邊的圖簡稱為n,m圖圖19握手

14、定理握手定理定理定理14.114.1握手定理：設(shè)握手定理：設(shè)G G是是n, mn, m無向圖，它的頂無向圖，它的頂點(diǎn)集合點(diǎn)集合v1,v2,vnv1,v2,vn，于是有，于是有1()2niidvm111()2,()()nnniiiiiidvmdvdvm證明：證明：在無向圖中引入一條邊，總的次數(shù)增，在無向圖中引入一條邊，總的次數(shù)增，假設(shè)有假設(shè)有m m條邊，那么總次數(shù)為條邊，那么總次數(shù)為2m2m。此定理也可推行到有向圖和混合圖此定理也可推行到有向圖和混合圖定理定理14.1 14.1 在有向圖中，那么為：在有向圖中，那么為：20例例 2 d da a， d db b， d dc c， d dd d,

15、, m m，2m2mdd d d + + + + 21例例 3例：假設(shè)圖有例：假設(shè)圖有n n個(gè)頂點(diǎn)個(gè)頂點(diǎn), ,n+1n+1條邊，那么條邊，那么中至少有一個(gè)頂點(diǎn)的度數(shù)中至少有一個(gè)頂點(diǎn)的度數(shù)。證明：設(shè)中有證明：設(shè)中有n n個(gè)結(jié)點(diǎn)分別為個(gè)結(jié)點(diǎn)分別為v1,v2,vnv1,v2,vn，那么由握手定理：那么由握手定理： d dvivin+1n+1而頂點(diǎn)的平均度數(shù)為：而頂點(diǎn)的平均度數(shù)為： d dvivi(n+1)/n=2+1/n2 (n+1)/n=2+1/n2 頂點(diǎn)中至少有一個(gè)頂點(diǎn)的度數(shù)頂點(diǎn)中至少有一個(gè)頂點(diǎn)的度數(shù)22握手定理的推論握手定理的推論推論：在圖中，度數(shù)為奇數(shù)的頂點(diǎn)必定有偶數(shù)個(gè)。推論：在圖中，度數(shù)為

16、奇數(shù)的頂點(diǎn)必定有偶數(shù)個(gè)。 證 明 ： 設(shè) 度 數(shù) 為 偶 數(shù) 的 頂 點(diǎn) 有證 明 ： 設(shè) 度 數(shù) 為 偶 數(shù) 的 頂 點(diǎn) 有 n 1n 1 個(gè)個(gè) , , 記 為記 為vei(i=1,2,n1),vei(i=1,2,n1),度數(shù)為奇數(shù)的頂點(diǎn)有度數(shù)為奇數(shù)的頂點(diǎn)有n2n2個(gè)，記為個(gè)，記為voi(i=1,2,n2)voi(i=1,2,n2)。由上一定理得。由上一定理得由于度數(shù)為偶數(shù)的各頂點(diǎn)次數(shù)之和為偶數(shù)。所以前一由于度數(shù)為偶數(shù)的各頂點(diǎn)次數(shù)之和為偶數(shù)。所以前一項(xiàng)度數(shù)為偶數(shù)；假設(shè)項(xiàng)度數(shù)為偶數(shù)；假設(shè)n2n2為奇數(shù)，那么第二項(xiàng)為奇數(shù)，為奇數(shù)，那么第二項(xiàng)為奇數(shù)，兩項(xiàng)之和將為奇數(shù)，但這與上式矛盾。故兩項(xiàng)之和將為

17、奇數(shù)，但這與上式矛盾。故n2n2必為偶必為偶數(shù)。數(shù)。問題：能否在一個(gè)部門的問題：能否在一個(gè)部門的2525個(gè)人中間，由于意見不同，個(gè)人中間，由于意見不同，每個(gè)人恰好與每個(gè)人恰好與5 5個(gè)人意見一致？個(gè)人意見一致？121112()()()nnnieioiiiimd vd vd v23可圖化、可簡單圖化可圖化、可簡單圖化 設(shè)設(shè)G=為一個(gè)為一個(gè)n階無向圖，階無向圖，Vv1,v2,vn，稱稱d(v1),d(v2)d(vn) 為為G的度數(shù)列。對于頂點(diǎn)標(biāo)的度數(shù)列。對于頂點(diǎn)標(biāo)定的無向圖，它的度數(shù)列是獨(dú)一的。定的無向圖，它的度數(shù)列是獨(dú)一的。 反之，對于給定的非負(fù)整數(shù)列反之，對于給定的非負(fù)整數(shù)列d=(d1,d2,

18、dn),假假設(shè)存在以設(shè)存在以Vv1,v2,vn為頂點(diǎn)集的為頂點(diǎn)集的n階無向階無向圖圖G，使得，使得d(vi)=di，那么稱，那么稱d是可圖化的。是可圖化的。 特別的，假設(shè)所得圖是簡單圖，那么稱特別的，假設(shè)所得圖是簡單圖，那么稱d是可簡單是可簡單圖化的。圖化的。24可圖化的判別定理可圖化的判別定理定理定理14.3 14.3 設(shè)非負(fù)整數(shù)列設(shè)非負(fù)整數(shù)列d=(d1,d2,dn), d=(d1,d2,dn), 那么那么d d是可是可圖化的當(dāng)且僅當(dāng)圖化的當(dāng)且僅當(dāng) 證明：必要性顯然證明：必要性顯然 充分性：構(gòu)造性證明充分性：構(gòu)造性證明定理定理14.4 14.4 設(shè)設(shè)G G為恣意為恣意n n階無向簡單圖，那么

19、階無向簡單圖，那么(G) n-(G) n-1 110(mod 2)niid25可圖化可圖化q 例：判別以下各非負(fù)整數(shù)列哪些是可圖化的？哪些是可簡單圖化的？q (5,5,4,4,2,1)q (5,4,3,2,2)q (3,3,3,1)q (d1,d2,dn), d1d2dn1, 且 為偶數(shù)q (4,4,3,3,2,2)1niid26同構(gòu)的定義同構(gòu)的定義定義定義14.5：設(shè)，和：設(shè)，和，是兩是兩個(gè)圖，假設(shè)存在從到個(gè)圖，假設(shè)存在從到一雙射函數(shù)：一雙射函數(shù)：，使，使得對恣意的得對恣意的a,bV,a,b E當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)g(a),g(b) ，并且并且a,b和和g(a),g(b)有一樣的重?cái)?shù)，那么稱有一

20、樣的重?cái)?shù)，那么稱和同構(gòu)。和同構(gòu)。討論定義：討論定義：1和是同構(gòu)的和是同構(gòu)的,它們的頂點(diǎn)必需是一一對應(yīng)的；它們的頂點(diǎn)必需是一一對應(yīng)的；2且對無向圖而言，還要堅(jiān)持頂點(diǎn)之間的鄰接關(guān)系和邊且對無向圖而言，還要堅(jiān)持頂點(diǎn)之間的鄰接關(guān)系和邊的重?cái)?shù)；的重?cái)?shù)；3且對有向圖而言，不但要堅(jiān)持頂點(diǎn)之間的鄰接關(guān)系，且對有向圖而言，不但要堅(jiān)持頂點(diǎn)之間的鄰接關(guān)系，而且還應(yīng)堅(jiān)持邊的方向和邊的重?cái)?shù)。而且還應(yīng)堅(jiān)持邊的方向和邊的重?cái)?shù)。圖的同構(gòu)關(guān)系可以看作是全體圖集合上的二元關(guān)系，并且此圖的同構(gòu)關(guān)系可以看作是全體圖集合上的二元關(guān)系，并且此關(guān)系是等價(jià)關(guān)系。關(guān)系是等價(jià)關(guān)系。27例例4例：例： 存在一雙射函數(shù)存在一雙射函數(shù):1,2,3,4

21、a3,a4,a2,a1，其中：頂點(diǎn)的一一對應(yīng)：其中：頂點(diǎn)的一一對應(yīng)： g(1)= a3; g(2)= a4; g(3)= a2; g(4)= a1;邊的一一對應(yīng)：邊的一一對應(yīng)： g; g; g; g28例例 5例例:下面給出二個(gè)無向圖，試求出同構(gòu)函數(shù)下面給出二個(gè)無向圖，試求出同構(gòu)函數(shù)：1,2,3,4,5,6 a1,a2,a3,a4,a5,a6邊的對應(yīng)為：邊的對應(yīng)為：g(i,j)(g(i),g(j)ai,aj29同構(gòu)的性質(zhì)同構(gòu)的性質(zhì)兩圖同構(gòu)的必要條件：兩圖同構(gòu)的必要條件：1頂點(diǎn)數(shù)相等；頂點(diǎn)數(shù)相等；2邊數(shù)相等；邊數(shù)相等；3度數(shù)一樣的頂點(diǎn)數(shù)相等。度數(shù)一樣的頂點(diǎn)數(shù)相等。但這不是充分條件。如以下圖但這不

22、是充分條件。如以下圖30完全圖完全圖定義定義14.6：在個(gè)頂點(diǎn)的有向圖：在個(gè)頂點(diǎn)的有向圖G=中，假設(shè)每中，假設(shè)每個(gè)頂點(diǎn)都鄰接到其他的個(gè)頂點(diǎn)都鄰接到其他的n-1個(gè)頂點(diǎn)，又鄰接于其他個(gè)頂點(diǎn)，又鄰接于其他的的n-1個(gè)頂點(diǎn)，那么稱個(gè)頂點(diǎn)，那么稱G為有向完全圖；在個(gè)頂為有向完全圖；在個(gè)頂點(diǎn)的無向圖點(diǎn)的無向圖G=中，每二個(gè)頂點(diǎn)之間均有一中，每二個(gè)頂點(diǎn)之間均有一條邊銜接，那么稱條邊銜接，那么稱G為無向完全圖。為無向完全圖。31特殊圖特殊圖定義定義14.714.7：一切頂點(diǎn)均具有同樣度數(shù)的簡單無向圖：一切頂點(diǎn)均具有同樣度數(shù)的簡單無向圖為正那么圖，各頂點(diǎn)的度數(shù)均為為正那么圖，各頂點(diǎn)的度數(shù)均為k k時(shí)稱為時(shí)稱為k

23、 k正那正那么圖。么圖。32子圖的定義子圖的定義定義定義14.8:設(shè)設(shè)=,=是二個(gè)圖，是二個(gè)圖， (a)假設(shè)假設(shè)，那么稱，那么稱是的子是的子圖；圖； (b)假設(shè)假設(shè)，并且，并且，那么稱，那么稱是的真子圖；是的真子圖； (c)假設(shè)假設(shè)，,那么稱那么稱是的生成是的生成子圖支撐子圖。子圖支撐子圖。 (d)假設(shè)子圖假設(shè)子圖G中沒有孤立頂點(diǎn)，中沒有孤立頂點(diǎn)，G由由E獨(dú)一確獨(dú)一確定，那么稱定，那么稱G為由邊集為由邊集E導(dǎo)出的子圖。導(dǎo)出的子圖。 (e)假設(shè)在子圖假設(shè)在子圖G中，對中，對中的恣意二頂點(diǎn)中的恣意二頂點(diǎn)u,v，當(dāng)當(dāng)u,vE時(shí)有時(shí)有u,vE，那么，那么G由由獨(dú)一確獨(dú)一確定，此時(shí)稱定，此時(shí)稱G為由頂點(diǎn)

24、集為由頂點(diǎn)集導(dǎo)出的子圖。導(dǎo)出的子圖。33例例 6例：圖如下例：圖如下 的真子圖的真子圖 生成子圖：生成子圖： E=,導(dǎo)出的子圖由V=a,b,d,e導(dǎo)出的子圖34例例 7例例 畫出畫出4 4階階3 3邊的一切非同構(gòu)的無向簡單圖。邊的一切非同構(gòu)的無向簡單圖。解：由握手定理可知，該無向簡單圖各頂點(diǎn)度數(shù)之和解：由握手定理可知，該無向簡單圖各頂點(diǎn)度數(shù)之和為為6 6，最大度小于或等于，最大度小于或等于3 3。于是所求無向簡單圖的。于是所求無向簡單圖的度數(shù)列應(yīng)滿足的條件是，將度數(shù)列應(yīng)滿足的條件是，將6 6分成分成4 4個(gè)非負(fù)數(shù)，每個(gè)個(gè)非負(fù)數(shù)，每個(gè)整數(shù)均大于等于整數(shù)均大于等于0 0且小于等于且小于等于3 3，

25、并且奇數(shù)的個(gè)數(shù)為，并且奇數(shù)的個(gè)數(shù)為偶數(shù)。有三種情況偶數(shù)。有三種情況3 3，1 1，1 1，1 1；2 2，2 2，1 1，1 1；2 2，2 2，2 2，0 0將每種度數(shù)列一切非同構(gòu)的圖都畫出來即可得所要求將每種度數(shù)列一切非同構(gòu)的圖都畫出來即可得所要求的全部非同構(gòu)圖。的全部非同構(gòu)圖。35補(bǔ)圖補(bǔ)圖定義定義14.9:設(shè)無向簡單圖設(shè)無向簡單圖G= 有有n個(gè)頂點(diǎn)，無向個(gè)頂點(diǎn)，無向簡單圖簡單圖H= 也有同樣的頂點(diǎn)，而也有同樣的頂點(diǎn)，而E是是由由n個(gè)頂點(diǎn)的完全圖的邊刪去個(gè)頂點(diǎn)的完全圖的邊刪去E所得，那么圖所得，那么圖H稱為圖稱為圖G的補(bǔ)圖。的補(bǔ)圖。 自補(bǔ)圖：自補(bǔ)圖：H與與G同構(gòu)同構(gòu)36例例 8例：試畫出例

26、：試畫出5個(gè)頂點(diǎn)三條邊和個(gè)頂點(diǎn)三條邊和5個(gè)頂點(diǎn)七條邊的簡單個(gè)頂點(diǎn)七條邊的簡單無向圖。無向圖。解：解： 5個(gè)頂點(diǎn)三條邊的圖個(gè)頂點(diǎn)三條邊的圖5個(gè)頂點(diǎn)七條邊的圖為個(gè)頂點(diǎn)七條邊的圖為5頂點(diǎn)三條邊的補(bǔ)圖頂點(diǎn)三條邊的補(bǔ)圖37圖的操作圖的操作關(guān)于圖的四種操作：關(guān)于圖的四種操作：1刪去中的一條邊刪去中的一條邊e；2刪去中的一個(gè)頂點(diǎn)即是刪去頂點(diǎn)和與刪去中的一個(gè)頂點(diǎn)即是刪去頂點(diǎn)和與有關(guān)聯(lián)的一切邊。有關(guān)聯(lián)的一切邊。3設(shè)邊設(shè)邊e=(u,v)E，用，用Ge表示從表示從G中刪除中刪除e后，將后，將e的兩個(gè)端點(diǎn)的兩個(gè)端點(diǎn)u,v用一個(gè)新的頂點(diǎn)用一個(gè)新的頂點(diǎn)w替代，使替代，使w關(guān)聯(lián)關(guān)聯(lián)e以外以外u,v關(guān)聯(lián)的一切邊，稱為關(guān)聯(lián)的一

27、切邊，稱為e的收縮。的收縮。4設(shè)設(shè)u,vV，用，用G(u,v)表示在表示在u,v之間加一條邊之間加一條邊(u,v)，稱為新加邊。，稱為新加邊。38第十四章圖的根本概念第十四章圖的根本概念 第二節(jié)：通路、回路、圖的連通性第二節(jié)：通路、回路、圖的連通性 3914.2 通路和回路通路和回路定義定義14.11: 在有向圖中，從某一頂點(diǎn)出發(fā)經(jīng)過某些點(diǎn)在有向圖中，從某一頂點(diǎn)出發(fā)經(jīng)過某些點(diǎn)邊交替序列到達(dá)終點(diǎn)，此序列稱為通路。邊交替序列到達(dá)終點(diǎn)，此序列稱為通路。而經(jīng)過的各條邊之間沒有一樣的通路稱為簡單通路。而經(jīng)過的各條邊之間沒有一樣的通路稱為簡單通路。假設(shè)通路中頂點(diǎn)各不一樣且邊也各不一樣，那么稱假設(shè)通路中頂點(diǎn)

28、各不一樣且邊也各不一樣，那么稱為初級通路或途徑。為初級通路或途徑。假設(shè)通路的起點(diǎn)和終點(diǎn)重合，稱此通路為回路。沒假設(shè)通路的起點(diǎn)和終點(diǎn)重合，稱此通路為回路。沒有一樣邊的回路稱為簡單回路，沒有一樣邊也沒有一樣邊的回路稱為簡單回路，沒有一樣邊也沒有一樣點(diǎn)除起始點(diǎn)和終止點(diǎn)外的回路稱為圈。有一樣點(diǎn)除起始點(diǎn)和終止點(diǎn)外的回路稱為圈。4014.2 通路和回路通路和回路討論：討論：1從一個(gè)頂點(diǎn)到某一頂點(diǎn)的通路假設(shè)有的話從一個(gè)頂點(diǎn)到某一頂點(diǎn)的通路假設(shè)有的話不一定是獨(dú)一的；不一定是獨(dú)一的；2通路的表示方法：通路的表示方法：(a)邊點(diǎn)序列表示法：邊點(diǎn)序列表示法： 設(shè)，為一有向圖，設(shè)，為一有向圖，viV，那么通路可，那么

29、通路可以表示成：以表示成：v1,e1,v2,e2,v3,vk-1,en,vk(b)也可僅用邊的序列表示也可僅用邊的序列表示(c)頂點(diǎn)表示法頂點(diǎn)表示法(在簡單圖中在簡單圖中)： v1, v2 , vk (3)無向圖中的以上術(shù)語的定義完全類似，不再反復(fù)。無向圖中的以上術(shù)語的定義完全類似，不再反復(fù)。41例例 1例：給出有向圖例：給出有向圖,求起始于求起始于,終止于的通路。終止于的通路。 P1=(1,2,3)=(,) P2=(1,2,3,4,3) P3=(1,4,3) P4=(1,2,4,1,2,3) P5=(1,2,4,1,4,3) P6=(1,1,2,3),可見：可見：1從從1到到3有無限條通路，

30、有無限條通路，中間有回路；中間有回路；2上例中的上例中的P1 ，P2， P3， P5為簡單通路。為簡單通路。42通路的性質(zhì)通路的性質(zhì)定義定義:通路通路P中邊的條數(shù)稱為通路中邊的條數(shù)稱為通路P的長度路長。的長度路長。長度為長度為0的通路定義為一個(gè)單獨(dú)的頂點(diǎn)。的通路定義為一個(gè)單獨(dú)的頂點(diǎn)。定理定理14.5:設(shè)圖，是中的頂點(diǎn)數(shù)設(shè)圖，是中的頂點(diǎn)數(shù)即，假設(shè)從即，假設(shè)從v1到到v2(v1v2)有一條有一條通路，那么從通路，那么從v1到到v2有一條長度不大于有一條長度不大于n-1的通路。的通路。 推論推論:設(shè)圖，是中的頂點(diǎn)數(shù)設(shè)圖，是中的頂點(diǎn)數(shù)即，假設(shè)從即，假設(shè)從v1到到v2(v1v2)有一條有一條通路，那么從

31、通路，那么從v1到到v2有一條長度不大于有一條長度不大于n-1的初級的初級通路途徑。通路途徑。43通路和回路的性質(zhì)通路和回路的性質(zhì)定理定理14.6：在階圖中，從：在階圖中，從vi到到vi假設(shè)存在一條回路假設(shè)存在一條回路的話，那么從的話，那么從vi到到vi一定存在一條長度小于或等于一定存在一條長度小于或等于的回路。的回路。推論：在階圖中，從推論：在階圖中，從vi到到vi假設(shè)存在一條簡單回路假設(shè)存在一條簡單回路的話，那么從的話，那么從vi到到vi一定存在一條長度小于或等于一定存在一條長度小于或等于的初級回路。的初級回路。44通路和回路通路和回路q例：例：q 1. 無向完全圖無向完全圖Knn3中有幾

32、種非同構(gòu)中有幾種非同構(gòu)的圈？的圈？q 2. 無向完全圖無向完全圖K3的頂點(diǎn)依次標(biāo)定為的頂點(diǎn)依次標(biāo)定為a，b，c. 在定義意義下在定義意義下K3中有多少中有多少 不同的長度為不同的長度為3的圈的圈？q 4514.3 圖的連通性圖的連通性定義定義14.12：設(shè)無向圖：設(shè)無向圖=，且，且vi,vjV，假設(shè)，假設(shè)從從vi到到vj存在一條通路的話，那么稱存在一條通路的話，那么稱vi，vj是連通是連通的。普通以為的。普通以為vi到本身是連通的。到本身是連通的。由定義可見：連通的概念與由定義可見：連通的概念與vi到到vj之間的通路多少、之間的通路多少、通路長度、是什么樣的通路沒有任何關(guān)系。通路長度、是什么樣

33、的通路沒有任何關(guān)系。4614.3 圖的連通性圖的連通性連通性一定滿足：連通性一定滿足：自反性：自反性： vi到到vi一定是連通的。一定是連通的。可傳送性：可傳送性： vi到到vj連通，連通，vj到到vk連通，那么連通，那么vi到到vk連通。連通。對于有向圖而言，既不一定對稱，也不一定對于有向圖而言，既不一定對稱，也不一定反對稱。反對稱。 假設(shè)假設(shè)vi到到vj存在一條通路的話，那么存在一條通路的話，那么vj到到vi未必存未必存在一條通路。在一條通路。連通性對無向圖滿足自反、對稱和可傳送性連通性對無向圖滿足自反、對稱和可傳送性 47連通圖連通圖定義定義14.12：對于無向圖中的任何頂點(diǎn)來講，假設(shè)任

34、：對于無向圖中的任何頂點(diǎn)來講，假設(shè)任何二個(gè)頂點(diǎn)是相互連通的，那么稱此圖是連通的，何二個(gè)頂點(diǎn)是相互連通的，那么稱此圖是連通的，否那么稱為非連通圖或分別圖。否那么稱為非連通圖或分別圖。48連通分支連通分支定義定義14.13：設(shè)無向圖：設(shè)無向圖G=，V關(guān)于頂點(diǎn)之間的關(guān)于頂點(diǎn)之間的連通關(guān)系的商集連通關(guān)系的商集V/=V1,V2, Vk，Vi為等為等價(jià)類，稱導(dǎo)出子圖價(jià)類，稱導(dǎo)出子圖GVi(i=1,2,k)為為G的連通分的連通分支，連通分支數(shù)支，連通分支數(shù)k常記為常記為p(G)。一個(gè)無向圖或者是一個(gè)連通圖，或者是由假設(shè)干個(gè)一個(gè)無向圖或者是一個(gè)連通圖，或者是由假設(shè)干個(gè)連通分支組成連通分支組成49間隔間隔定義定

35、義14.14: 在無向圖在無向圖G=中，從頂點(diǎn)中，從頂點(diǎn)vi到到vj最短最短通路短程線的長度，叫做從通路短程線的長度，叫做從vi到到vj的間隔，記的間隔，記為為d(vi, vj) 。假設(shè)從。假設(shè)從vi到到vj不存在通路，那么不存在通路，那么d(vi, vj) =留意：在無向圖中，有以下性質(zhì)：留意：在無向圖中，有以下性質(zhì)：1) d(vi, vj) 0 2) d(vi, vi) = 03) d(vi, vj)=d(vj, vi) 4) d(vi, vj) +d(vj, vk) d(vi, vk) 50點(diǎn)割集、割點(diǎn)點(diǎn)割集、割點(diǎn)q定義定義14.15 設(shè)無向圖設(shè)無向圖 G= 。假設(shè)存在。假設(shè)存在 使得使

36、得p(G-V) p(G)，且有恣意的均有，且有恣意的均有p(G-V) =p(G)，那么稱，那么稱V為為G的點(diǎn)割集。假的點(diǎn)割集。假設(shè)是單個(gè)點(diǎn)，那么稱割點(diǎn)。設(shè)是單個(gè)點(diǎn)，那么稱割點(diǎn)。q定義定義14.16 設(shè)無向圖設(shè)無向圖 G= 。假設(shè)存在。假設(shè)存在 使得使得p(G-E) p(G)，且有恣意的均有，且有恣意的均有p(G-E) =p(G)，那么稱，那么稱E為為G的邊割集。假的邊割集。假設(shè)是單個(gè)邊，那么稱割邊或者橋。設(shè)是單個(gè)邊，那么稱割邊或者橋。q點(diǎn)連通度點(diǎn)連通度k-連通圖連通圖 q 留意：假設(shè)留意：假設(shè)G是是k-連通圖，那么在連通圖，那么在G中刪除任何中刪除任何k-1個(gè)頂點(diǎn)后，所得圖一定還是連通的個(gè)頂點(diǎn)

37、后，所得圖一定還是連通的q邊連通度邊連通度 r邊邊-連通圖連通圖VV VV EE EE 51點(diǎn)連通度、邊連通度的關(guān)系點(diǎn)連通度、邊連通度的關(guān)系q對于任何無向圖G，有)()()(GGG52間隔間隔定義定義14.19：設(shè)有向圖：設(shè)有向圖=，且，且vi,vjV，假設(shè)，假設(shè)從從vi到到vj存在一條通路的話，那么稱存在一條通路的話，那么稱vi可達(dá)可達(dá)vj。普。普通以為通以為vi到本身是可達(dá)的。假設(shè)到本身是可達(dá)的。假設(shè)vi可達(dá)可達(dá)vj并且并且vj可可達(dá)達(dá)vi，那么稱，那么稱vi,vj相互可達(dá)。相互可達(dá)。定義定義14.20: 在有向圖在有向圖G=中，從頂點(diǎn)中，從頂點(diǎn)vi到到vj最短最短通路短程線的長度，叫做從

38、通路短程線的長度，叫做從vi到到vj的間隔，記的間隔，記為為d(vi, vj) 。假設(shè)從。假設(shè)從vi到到vj不存在通路，那么不存在通路，那么d(vi, vj) =。53連通性連通性定義定義14.22：在有向圖中，它的基圖假設(shè)是連通的，那：在有向圖中，它的基圖假設(shè)是連通的，那么稱此有向圖為弱連通的；假設(shè)圖中任何頂點(diǎn)偶對么稱此有向圖為弱連通的；假設(shè)圖中任何頂點(diǎn)偶對中至少有一點(diǎn)到另一頂點(diǎn)是可達(dá)的，那么稱此圖是中至少有一點(diǎn)到另一頂點(diǎn)是可達(dá)的，那么稱此圖是單向連通的；假設(shè)任兩頂點(diǎn)均是相互可達(dá)的，那么單向連通的；假設(shè)任兩頂點(diǎn)均是相互可達(dá)的，那么稱是強(qiáng)連通的。稱是強(qiáng)連通的。討論定義：討論定義：1強(qiáng)連通的一定

39、是單向連通的和弱連通的；強(qiáng)連通的一定是單向連通的和弱連通的；2單向連通的一定是弱連通的；單向連通的一定是弱連通的；3弱連通的既能夠不是單向連通的，更能夠不是弱連通的既能夠不是單向連通的，更能夠不是強(qiáng)連通的。強(qiáng)連通的。54連通性連通性 強(qiáng)連通的強(qiáng)連通的 單向連通的弱連通的單向連通的弱連通的55圖的連通性圖的連通性定理定理14.8 設(shè)有向圖設(shè)有向圖D=，Vv1,v2,vn 。D是強(qiáng)連通圖當(dāng)且僅當(dāng)是強(qiáng)連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的回路。一次的回路。證明：充分性顯然證明：充分性顯然必要性構(gòu)造性證明必要性構(gòu)造性證明定理定理14.9 設(shè)設(shè)D是是n階有向圖。階有向圖。D是

40、單向連通圖當(dāng)且僅是單向連通圖當(dāng)且僅當(dāng)當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的通路。中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的通路。56二部圖二部圖定義定義14.23:14.23:假設(shè)無向圖的頂點(diǎn)集假設(shè)無向圖的頂點(diǎn)集V V分成兩個(gè)子集分成兩個(gè)子集X,Y,(X,Y,(即滿足即滿足XY=,XY=V),XY=,XY=V),使得使得G G中恣意一邊中恣意一邊的兩個(gè)端點(diǎn)分屬于的兩個(gè)端點(diǎn)分屬于X X和和Y,Y,那么稱那么稱G G為二部圖為二部圖,X,X和和Y Y稱稱為互補(bǔ)頂點(diǎn)子集為互補(bǔ)頂點(diǎn)子集, ,常記圖為常記圖為G=G=。 定義定義: :假設(shè)二部圖假設(shè)二部圖G=G=中中X X的每個(gè)頂點(diǎn)與的每個(gè)頂點(diǎn)與Y Y的每的每個(gè)頂點(diǎn)都有且只

41、需一條邊相關(guān)聯(lián)個(gè)頂點(diǎn)都有且只需一條邊相關(guān)聯(lián), ,稱稱G G為完全二部為完全二部圖圖, ,記為記為Km,n,Km,n,其中其中|X|=m,|Y|=n|X|=m,|Y|=n。57例例4 abxyza x y z b 子集子集X=a,b,Y=x,y,z,這是一個(gè)二部圖。這是一個(gè)二部圖。這是完全二部圖這是完全二部圖K2,3。58二部圖二部圖此兩圖均是此兩圖均是K3,3因此是同構(gòu)的因此是同構(gòu)的 定理定理14.10:無向圖無向圖G是二部圖的充要條件是是二部圖的充要條件是G的一切的一切回路的長度均為偶數(shù)。回路的長度均為偶數(shù)。59第十四章圖的根本概念第十四章圖的根本概念 第三節(jié)：圖的矩陣表示和運(yùn)算第三節(jié)：圖的

42、矩陣表示和運(yùn)算 60圖的矩陣表示圖的矩陣表示矩陣是研討圖的有關(guān)性質(zhì)的最有效的工具之一，矩陣是研討圖的有關(guān)性質(zhì)的最有效的工具之一，可運(yùn)用圖的矩陣運(yùn)算求出圖的通路、回路和其可運(yùn)用圖的矩陣運(yùn)算求出圖的通路、回路和其它一些性質(zhì)。它一些性質(zhì)。前面討論圖的圖解表示法的優(yōu)點(diǎn)是直觀，但缺陷前面討論圖的圖解表示法的優(yōu)點(diǎn)是直觀，但缺陷是：是：1在結(jié)點(diǎn)較多時(shí)，用圖表示非常繁雜，甚至沒在結(jié)點(diǎn)較多時(shí)，用圖表示非常繁雜，甚至沒法表示；法表示；2計(jì)算機(jī)中難以儲(chǔ)存。計(jì)算機(jī)中難以儲(chǔ)存。本節(jié)討論用矩陣表示圖能較好的抑制以上二大缺本節(jié)討論用矩陣表示圖能較好的抑制以上二大缺陷。陷。 61圖的矩陣表示圖的矩陣表示定義定義14.23 設(shè)

43、無向圖設(shè)無向圖G，V=v1,v2,vn，E=e1,e2,em，令，令mij為頂點(diǎn)為頂點(diǎn)vi與邊與邊ej的關(guān)聯(lián)的關(guān)聯(lián)次數(shù)，那么稱次數(shù)，那么稱(mij)nm為為G的關(guān)聯(lián)矩陣，記做的關(guān)聯(lián)矩陣，記做M(G)。1 M(G)每列元素之和均為每列元素之和均為2。2 M(G)第第i行元素之和為行元素之和為vi的度數(shù)。的度數(shù)。3各頂點(diǎn)的度數(shù)之和等于邊數(shù)的各頂點(diǎn)的度數(shù)之和等于邊數(shù)的2倍倍4第第j列與第列與第k列一樣當(dāng)且僅當(dāng)邊列一樣當(dāng)且僅當(dāng)邊ej和和ek是平行邊。是平行邊。5 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)vi是孤立點(diǎn)是孤立點(diǎn)10mijjm62圖的矩陣表示圖的矩陣表示定義定義14.24 設(shè)有向圖設(shè)有向圖D中無環(huán)，中無環(huán)，V=v1

44、,v2,vn，E=e1,e2,em，令令mij 1 vi為為ej的始點(diǎn)的始點(diǎn) 0 vi與與ej不關(guān)聯(lián)不關(guān)聯(lián) 1 vi為為ej的終點(diǎn)的終點(diǎn)那么稱那么稱(mij)nm為為G的關(guān)聯(lián)矩陣，記做的關(guān)聯(lián)矩陣，記做M(D)。1M(D)中一切元素之和為中一切元素之和為0。2M(D)中，中，-1的個(gè)數(shù)等于的個(gè)數(shù)等于+1的個(gè)數(shù)，都等于邊數(shù)的個(gè)數(shù)，都等于邊數(shù)m。3第第i行中，行中，+1的個(gè)數(shù)等于的個(gè)數(shù)等于d+(vi)，-1的個(gè)數(shù)等于的個(gè)數(shù)等于d-(vi)。4平行邊所對應(yīng)的列一樣。平行邊所對應(yīng)的列一樣。63圖的矩陣表示圖的矩陣表示定義定義14.25：設(shè)：設(shè)D，是有向圖，其中，是有向圖，其中V=v1,v2,vn，并假定

45、各結(jié)點(diǎn)曾經(jīng)有從，并假定各結(jié)點(diǎn)曾經(jīng)有從v1到到vn的陳列次序。定義一個(gè)的陳列次序。定義一個(gè)nn的矩陣的矩陣A，并把其中各，并把其中各元素元素aij表示成：表示成： aij = vi鄰接到鄰接到 vj 邊的條數(shù)邊的條數(shù)那么稱矩陣那么稱矩陣A為圖為圖G的鄰接矩陣。的鄰接矩陣。例：設(shè)圖例：設(shè)圖D，如以下圖所示，其中，如以下圖所示，其中 V=v1,v2, v3,v4 64圖的矩陣表示圖的矩陣表示討論定義：討論定義：1假設(shè)圖假設(shè)圖D的鄰接矩陣中的元素為的鄰接矩陣中的元素為0和和1，又稱為，又稱為布爾矩陣。布爾矩陣。2圖圖D的鄰接矩陣中的元素的次序是無關(guān)緊要的，的鄰接矩陣中的元素的次序是無關(guān)緊要的，只需進(jìn)展

46、行和行、列和列的交換，那么可得到一只需進(jìn)展行和行、列和列的交換，那么可得到一樣的矩陣。樣的矩陣。65圖的矩陣表示圖的矩陣表示3當(dāng)有向圖中的有向邊表示關(guān)系時(shí)，鄰接矩陣就當(dāng)有向圖中的有向邊表示關(guān)系時(shí)，鄰接矩陣就是關(guān)系矩陣；是關(guān)系矩陣；假設(shè)圖是自反的，那么主對角線的元素均為假設(shè)圖是自反的，那么主對角線的元素均為1；假設(shè)圖是對稱的，那么對于假設(shè)圖是對稱的，那么對于i和和j有有aij=aji，主對角線，主對角線的元素不論。的元素不論。66圖的矩陣表示圖的矩陣表示4零圖的鄰接矩陣稱為零矩陣，即矩陣中的一切零圖的鄰接矩陣稱為零矩陣，即矩陣中的一切元素均為元素均為0；5在有向圖的鄰接矩陣中：在有向圖的鄰接矩陣

47、中：行中行中1的個(gè)數(shù)就是行中相應(yīng)頂點(diǎn)的出度的個(gè)數(shù)就是行中相應(yīng)頂點(diǎn)的出度列中列中1的個(gè)數(shù)就是列中相應(yīng)頂點(diǎn)的入度的個(gè)數(shù)就是列中相應(yīng)頂點(diǎn)的入度d+(1)=1,d-(1)=2 d+(2)=2,d-(2)=2 d+(3)=3,d-(3)=1 d+(4)=1,d-(4)=267qA(D)中一切元素之和為中一切元素之和為D中長度為中長度為1的通路的的通路的條數(shù)條數(shù)q對角線元素之和為對角線元素之和為D中長度為中長度為1的回路的條數(shù)的回路的條數(shù)q思索：思索：A(D)的的n次冪表示什么？次冪表示什么？圖的矩陣表示圖的矩陣表示68圖的矩陣表示圖的矩陣表示*矩陣的計(jì)算有向圖中：矩陣的計(jì)算有向圖中： 設(shè)：設(shè)： ， A69令令nknjinjikjikijijaaaaaaccCAAA1112,其含義為：其含義為：假設(shè)假設(shè)ai1a1j1，那么表，那么表示有示有i1j長度為長度為2的通路；的通路；A2表示表示i和和j之間具有長度之間具有長度為為2的不同通路的條數(shù)，的不同通路的條數(shù)，A3表示表示i和和j之間具有長度為之間具有長度為3的不同通路的條數(shù)，的不同通路的條數(shù)，A4表示表示i和和j之間具有長度為之間具有長度為4的不同通路的條數(shù)。的不同通路的條數(shù)。70例例2A3A4