離散數(shù)學(xué)圖的概念與表示課件

第十六章圖的概念與表示16.1圖的基本概念16.2鏈(或路)與圈(或回路)16.4圖的矩陣表示退出16.1圖的基本概念什么是圖?可用一句話概括，即：圖是用點(diǎn)和線來刻劃離散事物集合中的每對事物間以某種方式相聯(lián)系的數(shù)學(xué)模型。因為它顯得太抽象，不便于理解，所以有必要給出另外的回答。下面便是把圖作為代數(shù)結(jié)構(gòu)的一個定義。定義16.1.1一個圖G定義為一個三元組<V，E，φ>，記作G=<V，E，φ>。其中V是個非空有限集合，它的元素稱為結(jié)點(diǎn)；E也是個有限集合，其元素稱為邊，而φ是從E到V中的有序?qū)驘o序?qū)Φ挠成?。若結(jié)點(diǎn)vi與vj由一條邊(或弧)e所聯(lián)結(jié)，則稱結(jié)點(diǎn)vi和vj是邊(或弧)e的端結(jié)點(diǎn)；同時也稱結(jié)點(diǎn)vi與vj是鄰接結(jié)點(diǎn)，記作vi

adjvj；否則為非鄰接結(jié)點(diǎn)，記作vinadjvj；也說邊(或弧)e關(guān)聯(lián)vi與vj或說結(jié)點(diǎn)vi與vj關(guān)聯(lián)邊(或弧)e。關(guān)聯(lián)同一個結(jié)點(diǎn)的兩條邊或弧稱為鄰接邊或弧。而聯(lián)結(jié)一結(jié)點(diǎn)與它自身的一條邊，稱為環(huán)。環(huán)的方向是無意義的。如果把圖G中的弧或邊總看作聯(lián)結(jié)兩個結(jié)點(diǎn)，則圖G可簡記為G=<V，E>，其中V是非空結(jié)點(diǎn)集，E是聯(lián)結(jié)結(jié)點(diǎn)的邊集或弧集。定義16.1.2在圖G=<V，E>中，如果每條邊都是弧，該圖稱為有向圖；若每條邊都是無向邊，該圖G稱為無向圖；如果有些邊是有向邊，另一些邊是無向邊，圖G稱為混合圖。定義16.1.3在圖G=<V，E>中，如果任何兩結(jié)點(diǎn)間不多于一條邊(對于有向圖中，任何兩結(jié)點(diǎn)間不多于一條同向弧)，并且任何結(jié)點(diǎn)無環(huán)，則圖G稱為簡單圖；若兩結(jié)點(diǎn)間多于一條邊(對于有向圖中，兩結(jié)點(diǎn)間多于一條同向弧)圖G稱為多重圖，并把聯(lián)結(jié)兩結(jié)點(diǎn)之間的多條邊或弧，稱為平行邊或弧，平行邊或弧的條數(shù)稱為重數(shù)。定義16.1.5在無向圖G=<V，E>中，如果V中的每個結(jié)點(diǎn)都與其余的所有結(jié)點(diǎn)鄰接，即(vi)(vj)(vi，vj∈V→〔vi，vj〕∈E)則該圖稱為無向完全圖，記作K|V|。若|V|=n，該圖記作Kn。在一個圖中，如果一個結(jié)點(diǎn)不與任何其他結(jié)點(diǎn)鄰接，則該結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)。僅有孤立結(jié)點(diǎn)的圖稱為零圖。顯然，在零圖中邊集為空集。若一個圖中只含一個孤立結(jié)點(diǎn)，該圖稱為平凡圖。定義16.1.6在有向圖G=<V，E>中，對任意結(jié)點(diǎn)v∈V，以v為始結(jié)點(diǎn)的弧的條數(shù)，稱為結(jié)點(diǎn)v的出度，記為d+(v)；以v為終結(jié)點(diǎn)的弧的條條數(shù)，稱為v的入度，記作d-(v)；結(jié)點(diǎn)v的出度與入度之和，稱為結(jié)點(diǎn)的度數(shù)，記為d(v)，顯然d(v)=d+(v)+d-(v)。對于無向圖G=<V，E>，結(jié)點(diǎn)v∈V的度數(shù)等于聯(lián)結(jié)它的邊數(shù)，也記為d(v)。若v點(diǎn)有環(huán)，規(guī)定該點(diǎn)度因環(huán)而增加2。定理16.1.1給定無向圖G=<V，E>，則定理16.1.2在任何無向圖中，奇度結(jié)點(diǎn)的數(shù)目為偶數(shù)。定義16.1.7在無向圖G=<V，E>中，如果每個結(jié)點(diǎn)的度是k，即(v)(v∈V→d(v)=k)，則圖G稱為k度正則圖。顯然，對于k度正則圖G，Δ(G)=δ(G)=k。定義16.1.8給定無向圖G1=<V1，E1>和G2=<V2，E2>，于是(1)如果V2V1和E2E1，則稱G2為G1的子圖，記為G2G1。(2)如果V2V1，E2E1且E2≠E1，則稱G2為G1的真子圖，記為G2G1。(3)如果V2=V1，E2E1，則稱G2為G1的生成子圖，記為G2G1。定義16.1.10設(shè)圖G1=<V1，E1>和圖G2=<V2，E2>是圖G=<V，E>的子圖。如果E2=E-E1且G2=<E2>，則稱圖G2是相對于圖G的子圖G1的補(bǔ)圖。定義16.1.11給定圖G=<V，E>，若存在圖G1=<V，E1>，并且E1∩E=和圖<V，E1∪E>是完全圖，則G1稱為相對于完全圖的G的補(bǔ)圖，簡稱G1是G的補(bǔ)圖，并記為G1=。顯然，G與 互為補(bǔ)圖。在圖的定義中，強(qiáng)調(diào)的是結(jié)點(diǎn)集、邊集以及邊與結(jié)點(diǎn)的關(guān)聯(lián)關(guān)系，既沒有涉及到聯(lián)結(jié)兩個結(jié)點(diǎn)的邊的長度、形狀和位置，也沒有給出結(jié)點(diǎn)的位置或者規(guī)定任何次序。因此，對于給定的兩個圖，在它們的圖形表示中，即在用小圓圈表示結(jié)點(diǎn)和用直線或曲線表示聯(lián)結(jié)兩個結(jié)點(diǎn)的邊的圖解中，看起來很不一樣，但實(shí)際上卻是表示同一個圖。因而，引入兩圖的同構(gòu)概念便是十分必要的了。一般說來，證明兩個圖是同構(gòu)的并非是輕而易舉的事情，往往需要花些氣力。請讀者證明圖16.1.13中兩個圖是同構(gòu)的。根據(jù)圖的同構(gòu)定義，可以給出圖同構(gòu)的必要條件如下：(1)結(jié)點(diǎn)數(shù)目相等；(2)邊數(shù)相等；(3)度數(shù)相同的結(jié)點(diǎn)數(shù)目相等。但這僅僅是必要條件而不是充分條件。 滿足上述三個條件，然而并不同構(gòu)。因此在(a)中度數(shù)為3的結(jié)點(diǎn)x與兩個度數(shù)為1的結(jié)點(diǎn)鄰接，而(b)中度數(shù)為3的結(jié)點(diǎn)y僅與一個度數(shù)為1的結(jié)點(diǎn)鄰接。尋找一種簡單有效的方法來判定圖的同構(gòu)，至今仍是圖論中懸而未決的重要課題。人民郵電出版社高等學(xué)校21世紀(jì)教材

例如圖10.1.14中(a)與(b)返回圖1.1.1416.2鏈(或路)與圈(或回路)在無向圖(或有向圖)的研究中，常?？紤]從一個結(jié)點(diǎn)出發(fā)，沿著一些邊(或弧)連續(xù)移動而達(dá)到另一個指定結(jié)點(diǎn)，這種依次由結(jié)點(diǎn)和邊(或弧)組成的序列，便形成了鏈(或路)的概念。定義16.2.3在一圈(或回路)中，若出現(xiàn)的每條邊(或弧)恰好一次，稱該圈(或回路)為簡單圈(或簡單回路)；若出現(xiàn)的每個結(jié)點(diǎn)恰好一次，稱該圈(或回路)為基本圈(或基本回路)?？梢钥闯?，對于簡單圖來說，鏈(或路)和圈(或回路)能夠僅用結(jié)點(diǎn)序列表示之。定理16.2.1在一個圖中，若從結(jié)點(diǎn)vi到結(jié)點(diǎn)vj存在一條鏈(或路)，則必有一條從vi到vj的基本鏈(或基本路)。定理16.2.2在一個具有n個結(jié)點(diǎn)的圖中，則(1)任何基本鏈(或路)的長度均不大于n-1。(2)任何基本圈(或路)的長度均不大于n。定義16.2.4在一個圖中，若從vi到vj存在任何一條鏈(或路)，則稱從vi到vj是可達(dá)的，或簡稱vi可達(dá)vj。為完全起見，規(guī)定每個結(jié)點(diǎn)到其自身是可達(dá)的。對于無向圖G來說，不難證明結(jié)點(diǎn)間的可達(dá)性是結(jié)點(diǎn)集合上的等價關(guān)系。因此它將結(jié)點(diǎn)集合給出一個劃分，并且劃分中的每個元素形成一個誘導(dǎo)子圖；兩結(jié)點(diǎn)之間是可達(dá)的當(dāng)且僅當(dāng)它們屬于同一個子圖，稱這種子圖為圖G的連通分圖，圖G的連通分圖的個數(shù)，記為ω(G)。定義16.2.5若圖G只有一個連通分圖，則稱G是連通圖；否則，稱圖G為非連通圖或分離圖。在圖的研究中，常常需要考慮刪去與增加結(jié)點(diǎn)、結(jié)點(diǎn)集、邊和邊集（或弧集）的問題。所謂從圖G=<V,E>中刪去結(jié)點(diǎn)集S，是指作V-S以及從E中刪去與S中的全部結(jié)點(diǎn)相聯(lián)結(jié)的邊而得到的子圖，記作G-S；特別當(dāng)S=|v|時，簡記為G-v；所謂從圖G=<V,E>中刪去邊集（或弧集）T，是指作E-T，且T中的全部邊所關(guān)聯(lián)的結(jié)點(diǎn)仍在V中而得到的子圖，記為G-T；特別當(dāng)T={e}時，簡記作G-e。所謂圖G=<V,E>增加結(jié)點(diǎn)集S，是指作V∪T以及向E中并入S中、S與V中所成的邊而得到的圖，記作G+S；特別當(dāng)S={v}時，簡記為G+v；圖G=<V,E>增加邊集（或弧集）T是指作E∪T所得到的圖，記作G+T，這里T中全部邊（或?。┑年P(guān)聯(lián)結(jié)點(diǎn)屬于V。定義16.2.6給定連通無向圖G=<V，E>，SV。若ω(G-S)＞ω(G)，但TS有(G-T)=(G)，則稱S是G的一個分離結(jié)點(diǎn)集。若圖G的分離結(jié)點(diǎn)集S={v}，則稱v是G的割點(diǎn)。類似地可定義圖G的分離邊集T；若圖G的分離邊集T={e}，則稱e是G的割邊或橋。對于連通的非平凡圖G，稱(G)={|S||S是G的分離結(jié)點(diǎn)集}為圖G的結(jié)點(diǎn)連通度，它表明產(chǎn)生不連通圖而需要刪去結(jié)點(diǎn)的最少數(shù)目。于是，對于分離圖G，(G)=0；對于存在割點(diǎn)的連通圖G，(G)=1。類似地定義邊連通度(G)={|T||T是G的分離邊集}，它表明產(chǎn)生不連通圖而需要刪去邊的最少數(shù)目?？梢?，對于分離圖G，(G)=0；對于完全圖G，(G)=0；對于圖K1，(K1)=0；對于存在割邊的連通圖G，(G)=1；對于完全圖Kn，(Kn)=n-1。下面是由惠特尼(H.Whitney)于1932年得到的關(guān)于結(jié)點(diǎn)連通度、邊連通度和最小度的不等式聯(lián)系的定理：定理16.2.3對于任何一個無向圖G，有(G)≤(G)≤δ(G)。定理16.2.4一個連通無向圖G中的結(jié)點(diǎn)v是割點(diǎn)存在兩個結(jié)點(diǎn)u和w，使得聯(lián)結(jié)u和w的每條鏈都經(jīng)過v。定理16.2.5一個連通無向圖G中的邊e是割邊存在兩個結(jié)點(diǎn)u和w，使得聯(lián)結(jié)u與w的每條鏈都經(jīng)過e。下面再給出一個判定一條邊是割邊的充要條件。定理16.2.6連通無向圖G中的一條邊e是割邊e不包含在圖的任何基本圈中。對于有向圖而言，結(jié)點(diǎn)間的可達(dá)性不再是等價關(guān)系，它僅僅是自反的和傳遞的。一般說來，不是對稱的。因此，有向圖的連通概念較之無向圖要復(fù)雜得多。對于給定的有向力G，要略去G中每條邊的方向便得到一個無向圖G1，稱G1是G的基礎(chǔ)圖。定義16.2.7在簡單有向圖G中，若G中任何兩個結(jié)點(diǎn)間都是可達(dá)的，則稱G是強(qiáng)連通的；若任何兩個結(jié)點(diǎn)間至少是從一個結(jié)點(diǎn)可達(dá)另一個結(jié)點(diǎn)，則稱G是單向連通的；若有向圖G不是單向連通的，但其基礎(chǔ)圖是連通的，則稱G是弱連通的。從上面定義可知，若圖G是強(qiáng)連通的，則它必是單向連通的，但反之未必真；若圖G是單向連通的，則它必是弱連通的，反之不真。定理16.2.7有向圖G是強(qiáng)連通的G中有一回路，它至少通過每個結(jié)點(diǎn)一次。令G是簡單有向圖，對于某種性質(zhì)而言，若G中再沒有其它包含子圖G1的真子圖具有這種性質(zhì)，則稱G1是G的關(guān)于該性質(zhì)的極大子圖。定義16.2.8在簡單有向圖中，具有強(qiáng)連通性質(zhì)的極大子圖，稱為強(qiáng)分圖；具有單向連通性質(zhì)的極大子圖，稱為單向分圖；具有弱連通性質(zhì)的極大子圖，稱為弱分圖。定理16.2.8簡單有向圖中的任一個結(jié)點(diǎn)恰位于一個強(qiáng)分圖中。注意，有向圖中的任意一弧未必恰位于一個強(qiáng)分圖中，例如，在圖10.2.6中，弧<v1,v2>位于結(jié)點(diǎn)集合{v1,v2,v3}的誘導(dǎo)子圖中，但弧<v3,v4>不位于任何強(qiáng)分圖之中。類似地可以證明下面兩個定理：定理16.2.9簡單有向圖中的每個結(jié)點(diǎn)和每條弧至少位于一個單向分圖中。定理16.2.10簡單有向圖中的每個結(jié)點(diǎn)和每條弧恰位于一個弱分圖中。如果結(jié)點(diǎn)u可達(dá)結(jié)點(diǎn)v，它們之間可能存在不止一條鏈(或路)。在所有這些鏈(或路)中，最短鏈(或路)的長度稱為結(jié)點(diǎn)u和v之間的距離或短程線或測地線，記作d<u，v>。距離滿足下列性質(zhì)：d<u，v>≥0d<u，u>=0d<u，v>+d<v，w>≥d<u，w>如果u不可達(dá)v，則d<u，v>=+∞。此外，要注意，即使u與v相互可達(dá)，d<u，v>未必等于d<v，u>。下面給出簡單有向圖的一個應(yīng)用——資源分配圖。在多道程序的計算機(jī)系統(tǒng)中，可以同時執(zhí)行多個程序。實(shí)際上，程序共享計算機(jī)系統(tǒng)中的資源，如磁帶機(jī)、磁盤設(shè)備、CPU、主存貯器和編譯程序等。操作系統(tǒng)對這些資源負(fù)責(zé)分配給各個程序。當(dāng)一個程序要求使用某種資源，它要發(fā)出請求，操作系統(tǒng)必須保證這一請求得到滿足。對資源的請求可能發(fā)生沖突。如程序A控制著資源r1，請求資源r2；但程序B控制著資源r2，請求資源r1。這種情況稱為處于死鎖狀態(tài)。然而沖突的請求必須解決，資源分配圖有助發(fā)現(xiàn)和糾正死鎖。假設(shè)某一程序?qū)σ恍┵Y源的請求，在該程序運(yùn)行完之前必須都得到滿足。在請求的時間里，被請求的資源是不能利用的，程序控制著可利用的資源，但對不可利用的資源則必須等待。令Pt={p1，p2，…，pm}表示計算機(jī)系統(tǒng)在時間t的程序集合，QtPt是運(yùn)行的程序集合，或者說在時刻t至少分配一部分所請求的資源的程序集合。Rt={r1，r2，…，rn}是系統(tǒng)在時刻t的資源集合。資源分配圖Gt=<Rt，E>是有向圖，它表示了時間t系統(tǒng)中資源分配狀態(tài)。把每個資源ri看作圖中一個結(jié)點(diǎn)，其中i=1，2，…，n。<ri，rj>表示有向邊，<ri，rj>∈E當(dāng)且僅當(dāng)程序pk∈Qt已分配到資源ri且等待資源rj。例如，令Rt={r1,r2,r3,r4}，Qt={p1,p2,p3,p4}。資源分配狀態(tài)是：p1占用資源r4且請求資源r1；p2占用資源r1且請求資源r2和r3；p3占用資源r2且請求資源r3；p4占用資源r3且請求資源r1和r4。于是，可得到資源分配圖Gt=<Rt,E>，如圖10.2.7所示。能夠證明，在時刻t計算機(jī)系統(tǒng)處于死鎖狀態(tài)資源分配圖Gt中包含強(qiáng)分圖。于是，對于圖10.2.7，Gt是強(qiáng)連通的，即處于死鎖狀態(tài)。圖10.2.716.4圖的矩陣表示為什么要用矩陣來表示圖？給定一個圖G=<V，E>，使用G=<V，E>這種表示法存在兩個缺陷：1、在圖比較復(fù)雜時不夠直觀；2、不方便計算。一個簡單圖G=<V，E>由V中每兩個結(jié)點(diǎn)間的鄰接關(guān)系唯一地確定，這種關(guān)系可以用一個矩陣給出，而矩陣形式與圖中結(jié)點(diǎn)的編序有密切關(guān)系，這是用矩陣表示圖值得注意的一點(diǎn)。定義16.4.1給定簡單圖G=<V，E>，V={v1，v2，…，vn}，V中的結(jié)點(diǎn)按下標(biāo)由小到大編序，則n階方陣A=(aij)稱為圖G的鄰接矩陣。其中

i，j=1，2，…，n。有時為強(qiáng)調(diào)鄰接矩陣依賴于圖G，把圖G的鄰接矩陣記為A(G)。v2v1v3v4v5v1v5v2v3v40111110100110101010110010A(G1)=0100110101010110010111110A(G2)=G1G2v2v1v3v4v5v1v5v2v3v40011110100000100000000010A(G3)=0100100100000000010001110A(G4)=G3G4今后將略去這種由于V中結(jié)點(diǎn)編序而引起鄰接矩陣的任意性，而取該圖的任一個鄰接矩陣作為該圖的矩陣表示。

有關(guān)圖同構(gòu)的判斷問題的討論可以參考以下網(wǎng)址：

鄰接矩陣可展示相應(yīng)圖的一些性質(zhì)：1、若鄰接矩陣的元素全為零，則其對應(yīng)的圖是零圖；2、若鄰接矩陣的元素除主對角線元素外全為1，則其對應(yīng)的圖是連通的且為簡單完全圖；3、當(dāng)給定的簡單圖是無向圖時，鄰接矩陣是對稱矩陣；問題1、當(dāng)給定的簡單圖是有向圖時，鄰接矩陣不是對稱矩陣；以上結(jié)論是否成立？2、當(dāng)給定的圖是多重圖時，如何用鄰接矩陣表示？4、在給定簡單有向圖的鄰接矩陣中，第i行元素是由結(jié)點(diǎn)vi出發(fā)的弧所確定，故第i行中值為1的元素數(shù)目等于結(jié)點(diǎn)vi的出度。同理，第j列中值為1的元素數(shù)目等于結(jié)點(diǎn)vj的入度。即d+(vi)= 和d-(vj)= 。v1v2v3010101010A=GA2=010101010010101010.=101020101A3=101020101010101010.=020202020v1v2v3020202020A3=GA4=020202020010101010.=202040202A5=040404040由給定簡單圖G的鄰接矩陣A可計算出矩陣A的l次冪，即Al。若第i行第j列上的元素alij便是G中從第i個結(jié)點(diǎn)vi到第j個結(jié)點(diǎn)vj長度為l的鏈（或路）的數(shù)目。為說明此事實(shí)，今給出下面定理。定理16.4.1設(shè)A為簡單圖G的鄰接矩陣，則Al中的i行j列元素alij等于G中聯(lián)結(jié)vi到vj的長度為l的鏈(或路)的數(shù)目。在一些實(shí)際問題中，有時要判定圖中結(jié)點(diǎn)vi到結(jié)點(diǎn)vj是否可達(dá)，或者說vi到vj是否存在一要鏈（或路）。如果要利用圖G的鄰接矩陣A，則應(yīng)計算A2，A3，···，An，···。當(dāng)發(fā)現(xiàn)其中某個Ar中≥1，就表明vi可達(dá)vj或vi到vj存在一條鏈（或路）。但這種計算繁瑣量大，又不知計算Ar到何時為止。根據(jù)定理16.2.2可知，對于有n個結(jié)點(diǎn)的圖，任何基本鏈（或路）的長度不大于n-1和任何基本圈（或回路）的長度不大于n。因此，只需考慮就可以了，其中1≤r≤n。即只要計算Bn=A+A2+A3+···+An。如果關(guān)心的是結(jié)點(diǎn)間可達(dá)性或結(jié)點(diǎn)間是否有鏈（或路），至于結(jié)點(diǎn)間的鏈存在多少條及長度是多少無關(guān)緊要，那么便可用下面的定義圖的可達(dá)矩陣來表示結(jié)點(diǎn)間可達(dá)性。定義16.4.2給定圖G=<V，E>，將其結(jié)點(diǎn)按下標(biāo)編序得V={v1，v2，…，vn}。定義一個n階方陣P=(pij)，其中1vi到vj可達(dá)Pij=0否則則稱矩陣P是圖G的可達(dá)矩陣。{可見，可達(dá)矩陣表明了圖中任意兩結(jié)點(diǎn)間是否至少存在一條鏈(或路)以及在結(jié)點(diǎn)處是否有圈(或回路)。從圖G的鄰接矩陣A可以得到可達(dá)矩陣P，即令Bn=A+A2+A3+…+An，再從Bn中非零元素改為1而零元素不變，這種變換后的矩陣即是可達(dá)矩陣P。假設(shè)矩陣中的元素是屬于布爾代數(shù)<B,,,ˉ,0,1>的B中元素，其中B={0,1}，則稱該矩陣為布爾矩陣。顯然鄰接矩陣是一個布爾矩陣，同樣可達(dá)矩陣也是布爾矩陣。下面定義兩個布爾矩陣B與C的運(yùn)算：令B和C的布爾和、布爾積分別記為BC和BoC，其定義為(BC)ij=bijcij(BC)ij=(bikckj)i,j=1,2,···,n。其中bij，cij分別是B和C的i行j列元素。特別地，對于鄰接矩陣A，記A

A=A(2)，對任何r=2,3,···,有A(r-1)

A=A(r)要注意的是Ar與A(r)的差別。Ar中表明從vi到vj長度為r的鏈（或路）的數(shù)目，而A(r)中是指出：若vi到vj至少存在一條鏈（或路）時， =1，否則，=0。由上說明，便得到可達(dá)矩陣P為：P=AA(2)A(3)···A(n)=A(k)對于簡單有向圖G=<V,E>，顯然有EVV。因此，弧集合E可解釋成B中的二元關(guān)系，而二元關(guān)系是可用矩陣表示的，通常稱這種矩陣為關(guān)系矩陣，其定義如下：設(shè)兩個有限集合X={x1,x2,···,xm}和Y={y1,y2,···,yn}，則關(guān)系RXY的關(guān)系矩陣MR=(rij)，其中 1,<xi,yi>Rrij= 0,否則i=1,2,···,m；j=1,2,···,n。{由定義可知，關(guān)系R與其關(guān)系矩陣MR是一一對應(yīng)的，即可以相互確定。根據(jù)集合論可知，對于域F(R)=V而|V|=n的關(guān)系R的傳遞閉包R+可計算如下：R+=R∪R2∪R3∪···∪Rk(k≤n)于是，關(guān)系R1和R2的關(guān)系矩陣分別為A1和A2，則關(guān)系R1∪R2的關(guān)系矩陣為A1A2。用歸納法可以證明R+的關(guān)系矩陣是=···對于G=<V,E>的鄰接矩陣A是關(guān)系E的關(guān)系矩陣，因為E2=EoE，即若存在一個結(jié)點(diǎn)vk，使得viEvk，和vkEvj，則必有viE2vj，亦即從vi到vj若至少存在一條長度為2的鏈（或路），那么E2的關(guān)系矩陣中的(i,j)元素值為1。這表明矩陣A(2)是關(guān)系E2的關(guān)系矩陣。以此類推，A(k)是Ek的關(guān)系矩陣，k=2,3,···,n。因此A+=AA(2)A(3)···A(n)亦即A+=AA(2)A(3)···A(n)=P可見，關(guān)系E的傳遞閉包