離散數(shù)學圖論基礎知識剖析

11十月2023圖論基礎知識講解該材料用于圖論第1講課圖論基礎知識講解環(huán)節(jié)第一頁第二頁，共63頁。圖論圖論是組合和離散數(shù)學最重要的分支之一,也是計算機基礎理論科學的重要部分。它以圖為研究對象。在理論計算機科學、運籌學、系統(tǒng)科學和數(shù)學中都有重要的地位。而信息科學和生物科學已成為當今科學和經濟發(fā)展的核心和主要動力,也因此大大推動了以研究離散和組合問題為主要對象的圖論的發(fā)展第二頁第三頁，共63頁。圖論一個圖就是一個離散的拓撲結構,經常用于描述和研究許多領域中的各種問題。隨著計算機科學的飛速發(fā)展,圖論組合和算法的研究在近代也成為計算機科學和數(shù)學中發(fā)展最快的基礎學科之一,也受到國際上的學術界和高新技術企業(yè)方面特別重視。第三頁第四頁，共63頁。圖論理論計算機科學中的算法理論經典問題(圖中點對之間最短路,貨郎擔問題,圖重抅問題,HAMILTON問題,P-NP問題等)，通信網絡通訊(網絡設計,通訊速度和容量,網絡可靠性和容錯性等)；在基礎理論方面的著名四色定理和各種染色問題,極值理論及樹、路和圈問題，HAMILTON理論等)；網絡流、組合最優(yōu)化等運籌學問題；任務人員安排等管理科學和系統(tǒng)科學的問題以及在物理,化學,社會學,語言學,生物學等領域的大量應用問題。第四頁第五頁，共63頁。圖論圖論中的圖是由若干給定的點及連接兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關系，用點代表事物，用連接兩點的線表示相應兩個事物間具有這種關系。圖論本身是應用數(shù)學的一部份，因此，歷史上圖論曾經被好多位數(shù)學家各自獨立地建立過。關于圖論的文字記載最早出現(xiàn)在歐拉1736年的論著中，他所考慮的原始問題有很強的實際背景第五頁第六頁，共63頁。圖論圖論起源于著名的哥尼斯堡七橋問題。歐拉證明了這個問題沒有解，并且推廣了這個問題，給出了對于一個給定的圖可以某種方式走遍的判定法則。這項工作使歐拉成為圖論〔及拓撲學〕的創(chuàng)始人。第六頁第七頁，共63頁。圖論1859年，英國數(shù)學家哈米爾頓發(fā)明了一種游戲：用一個規(guī)則的實心十二面體，它的20個頂點標出世界著名的20個城市，要求游戲者找一條沿著各邊通過每個頂點剛好一次的閉回路，即「繞行世界」。用圖論的語言來說，游戲的目的是在十二面體的圖中找出一個生成圈。這個問題后來就叫做哈密頓問題。由于運籌學、計算機科學和編碼理論中的很多問題都可以化為哈密頓問題，從而引起廣泛的注意和研究。第七頁第八頁，共63頁。圖論在圖論的歷史中，還有一個最著名的問題——四色猜想。這個猜想說，在一個平面或球面上的任何地圖能夠只用四種顏色來著色，使得沒有兩個相鄰的國家有相同的顏色。每個國家必須由一個單連通域構成，而兩個國家相鄰是指它們有一段公共的邊界，而不僅僅只有一個公共點。四色猜想有一段有趣的歷史。第八頁第九頁，共63頁。圖論每個地圖可以導出一個圖，其中國家都是點，當相應的兩個國家相鄰時這兩個點用一條線來連接。所以四色猜想是圖論中的一個問題。它對圖的著色理論、平面圖理論、代數(shù)拓撲圖論等分支的發(fā)展起到推動作用。四色猜想的提出來自英國。1852年，畢業(yè)于倫敦大學的弗南西斯.格思里來到一家科研單位搞地圖著色工作時，發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來，每幅地圖都可以用四種顏色著色，使得有共同邊界的國家都被著上不同的顏色。第九頁第十頁，共63頁。圖論1872年，英國當時最著名的數(shù)學家凱利正式向倫敦數(shù)學學會提出了這個問題，于是四色猜想成了世界數(shù)學界關注的問題。世界上許多一流的數(shù)學家都紛紛參加了四色猜想的大會戰(zhàn)。1878～1880年兩年間，著名律師兼數(shù)學家肯普和泰勒兩人分別提交了證明四色猜想的論文，宣布證明了四色定理。但后來數(shù)學家赫伍德以自己的精確計算指出肯普的證明是錯誤的。不久，泰勒的證明也被人們否定了。于是，人們開始認識到，這個貌似容易的題目，其實是一個可與費馬猜想相媲美的難題。第十頁第十一頁，共63頁。圖論進入20世紀以來，科學家們對四色猜想的證明基本上是按照肯普的想法在進行。電子計算機問世以后，由于演算速度迅速提高，加之人機對話的出現(xiàn)，大大加快了對四色猜想證明的進程。1976年，美國數(shù)學家阿佩爾與哈肯在美國伊利諾斯大學的兩臺不同的電子計算機上，用了1200個小時，作了100億判斷，終于完成了四色定理的證明。不過不少數(shù)學家并不滿足于計算機取得的成就，他們認為應該有一種簡捷明快的書面證明方法。第十一頁第十二頁，共63頁。圖論對于網絡的研究，最早是從數(shù)學家開始的，其基本的理論就是圖論，它也是目前組合數(shù)學領域最活躍的分支。我們在復雜網絡的研究中將要遇到的各種類型的網絡，無向的、有向的、加權的……這些都可以用圖論的語言和符號精確簡潔地描述。圖論不僅為物理學家提供了描述網絡的語言和研究的平臺，而且其結論和技巧已經被廣泛地移植到復雜網絡的研究中。圖論，尤其是隨機圖論已經與統(tǒng)計物理并駕齊驅地成為研究復雜網絡的兩大解析方法之一。第十二頁第十三頁，共63頁。圖8.1圖的基本概念A、B、C、D四個班進行足球比賽，為了表示四個班之間比賽的情況，我們作出如右上圖的圖形。在該圖中的4個小圓圈分別表示這四個班，稱之為結點。如果兩個班進行了比賽，則在兩個結點之間用一條線連接起來，稱之為邊。這樣，利用圖形使得各班之間的比賽情況一目了然。第十三頁第十四頁，共63頁。定義8.1

一個圖是一個序偶<V,E>，記為圖的定義G＝<V,E>，其中：V＝{v1,v2,v3,…,vn}是一個有限的非空集合，vi(i＝1,2,3,…,n)稱為結點,簡稱點，V為結點集；E＝{e1,e2,e3,…,em}是一個有限的集合，ei(i＝1,2,3,…,m)稱為邊，E為邊集，E中的每個元素都有V中的結點對與之對應。即對任意e∈E，都有e與<u,v>∈V

V或者(u,v)∈V&V相對應。第十四頁第十五頁，共63頁。在一個圖中，關聯(lián)結點vi和vj的邊e，無論是有向的還是無向的，均稱邊e與結點vI和vj相關聯(lián)，而vi和vj稱為鄰接點，否則稱為不鄰接的；幾個概念關聯(lián)于同一個結點的兩條邊稱為鄰接邊；圖中關聯(lián)同一個結點的邊稱為環(huán)(或自回路)；圖中不與任何結點相鄰接的結點稱為孤立結點；僅由孤立結點組成的圖稱為零圖；僅含一個結點的零圖稱為平凡圖；含有n個結點、m條邊的圖稱為(n，m)圖；第十五頁第十六頁，共63頁。若邊e與無序結點對(u，v)相對應，則稱邊e為無向邊,記為e＝(u，v)，這時稱u，v是邊e的兩個端點；若邊e與有序結點對<u，v>相對應，則稱邊e為有向邊(或弧)，記為e＝<u，v>，這時稱u是邊e的始點(或弧尾).v是邊e的終點(或弧頭)，統(tǒng)稱為e的端點；每條邊都是無向邊的圖稱為無向圖；每條邊都是有向邊的圖稱為有向圖；有些邊是無向邊，而另一些是有向邊的圖稱為混合圖。圖的分類－按邊的方向用小圓圈表示V中的結點，用由u指向v的有向線段表示<u,v>，無向線段表示(u,v)。第十六頁第十七頁，共63頁。圖的分類－按邊的方向上圖所示的三個圖分別表示為：G1＝<V1,E1>＝<{v1,v2,v3,v4}，{(v1,v2),(v2,v3), (v1,v3),(v2,v4),(v1,v4),(v3,v4)}>G2＝<V2,E2>＝<{a,b,c,d,e},{<a,b>,<c,b>, <c,a>,<d,e>}>G3＝<V3,E3>＝<{1,2,3,4,5},{<1,2>,(1,4),<4,3>, <3,5>,<4,5>}>G1是無向圖，G2是有向圖，G3是混合圖。第十七頁第十八頁，共63頁。圖的分類－按邊的方向設圖G＝<V,E>如右圖所示。這里V＝{v1,v2,v3,v4,v5}，E＝{e1,e2,e3,e4,e5,e6}，其中e1＝(v1,v2)，e2＝<v1,v3>，e3＝(v1,v4)，e4＝(v2,v3)，e5＝<v3,v2>，e6＝(v3,v3)。圖中的e1、e3、e4是無向邊，e2、e5是有向邊。這是一個混合圖。第十八頁第十九頁，共63頁。在有向圖中，兩個結點間(包括結點自身間)若有同始點和同終點的幾條邊，則這幾條邊稱為平行邊，在無向圖中，兩個結點間(包括結點自身間)若有幾條邊，則這幾條邊稱為平行邊；兩結點vi，vj間相互平行的邊的條數(shù)稱為邊(vi，vj)或<vi，vj>的重數(shù)；含有平行邊的圖稱為多重圖；非多重圖稱為線圖；無自回路的線圖稱為簡單圖。圖的分類－按邊的重數(shù)G1、G2是多重圖，G3,G4是線圖，G4是簡單圖。第十九頁第二十頁，共63頁。

賦權圖G是一個三重組<V,E,g>或四重組<V,E,f,g>，其中V是結點集合，E是邊的集合，f是從V到非負實數(shù)集合的函數(shù)，g是從E到非負實數(shù)集合的函數(shù)。非賦權圖稱為無權圖。圖的分類－按權第二十頁第二十一頁，共63頁。在無向圖G＝<V，E>中，與結點v(v

V)關聯(lián)的邊的條數(shù)（有環(huán)時計算兩次），稱為該結點的度數(shù)，記為deg(v)；結點的度數(shù)（次數(shù)）在有向圖G＝<V，E>中，以結點v為始點引出的邊的條數(shù)，稱為該結點的出度,記為deg+(v)；以結點v為終點引入的邊的條數(shù)，稱為該結點的入度,記為deg-(v)；而結點的引出度數(shù)和引入度數(shù)之和稱為該結點的度數(shù)，記為deg(v)，即deg(v)＝deg+(v)+deg-(v)；第二十一頁第二十二頁，共63頁。對于圖G＝<V，E>，度數(shù)為1的結點稱為懸掛結點，它所關聯(lián)的邊稱為懸掛邊。在圖G＝<V，E>中，稱度數(shù)為奇數(shù)的結點為奇度數(shù)結點，度數(shù)為偶數(shù)的結點為偶度數(shù)結點。結點的度數(shù)（次數(shù)）v5是懸掛結點，<v1，v5>為懸掛邊。第二十二頁第二十三頁，共63頁。子圖定義8.7

設有圖G＝<V,E>和圖G'＝<V',E'>。若V'

V，E'

E，則稱G'是G的子圖，記為G'

G。若G'

G，且G'≠G（即V'

V或E'

E），則稱G'是G的真子圖，記為G'

G。若V'=V，E'

E，則稱G'是G的生成子圖。設V"

V且V"≠

，以V"為結點集，以兩個端點均在V"中的邊的全體為邊集的G的子圖稱為V"導出的G的子圖，簡稱V"的導出子圖。第二十三頁第二十四頁，共63頁。

在如圖中，給出了圖G以及它的真子圖G'和生成子圖G"。G'是結點集{v1，v2，v3，v4，v5}的導出子圖。顯然，每個圖都是它自身的子圖。子圖第二十四頁第二十五頁，共63頁。完全圖設G＝<V,E>為一個具有n個結點的無向簡單圖，如果G中任一個結點都與其余n-1個結點相鄰接，則稱G為無向完全圖，簡稱G為完全圖，記為Kn。設G＝<V,E>為一個具有n個結點的有向簡單圖，若對于任意u,v

V(u

v)，既有有向邊<u,v>，又有有向邊<v,u>，則稱G為有向完全圖，在不發(fā)生誤解的情況下，也記為Kn。第二十五頁第二十六頁，共63頁。完全圖無向的簡單完全圖K3，K4，K5和有向的簡單完全圖K3。無向完全圖Kn的邊數(shù)為=

n(n-1)，有向完全圖Kn的邊數(shù)為=n(n-1)。第二十六頁第二十七頁，共63頁。圖的同構圖的同構：設兩個圖G=<V,E>和G'=<V',E'>，如果存在雙射函數(shù)g：V→V'，使得對于任意的e=(vi,vj)（或者<vi,vj>）∈E當且僅當e'=(g(vi),g(vj))（或者<g(vi),g(vj)>）∈E'，并且e與e'的重數(shù)相同，則稱G與G'同構，記為G≌G'。第二十七頁第二十八頁，共63頁。圖的同構

容易驗證：G1≌G2，結點之間的對應關系為：a→v1，b→v2，c→v3，d→v4，e→v5；G3≌G4；G5≌G6；但G7與G8不同構。圖G5稱為彼得森圖。第二十八頁第二十九頁，共63頁。圖的操作定義

設圖G＝<V,E>。設e∈E，用G-e表示從G中去掉邊e得到的圖，稱為刪除e。又設E

E，用G-E

表示從G中刪除E

中所有邊得到的圖，稱為刪除E

。設v∈V，用G-v表示從G中去掉結點v及v關聯(lián)的所有邊得到的圖，稱為刪除結點v。又設V

V，用G-V

表示從G中刪除V

中所有結點及關聯(lián)的所有邊得到的圖，稱為刪除V

。設e＝(u,v)∈E，用G\e表示從G中刪除e，將e的兩個端點u,v用一個新的結點w代替，使w關聯(lián)除e外的u和v關聯(lián)的一切邊，稱為邊e的收縮。一個圖G可以收縮為圖H，是指H可以從G經過若干次邊的收縮而得到。設u,v∈V（u,v可能相鄰，也可能不相鄰），用G∪(u,v)表示在u,v之間加一條邊(u,v)，稱為加新邊。第二十九頁第三十頁，共63頁。路徑與回路圖G＝<V,E>中結點和邊相繼交錯出現(xiàn)的序列Γ=v0e1v1e2v2…ekvk，若Γ中邊ei的兩端點是vi-1和vi（G是有向圖時要求vi-1與vi分別是ei的始點和終點），則稱Γ為結點v0到結點vk的路徑。v0和vk分別稱為此路徑的始點和終點，統(tǒng)稱為路徑的端點。路徑中邊的數(shù)目k稱為此路徑的長度。當v0＝vR時，此路徑稱為回路。第三十頁第三十一頁，共63頁。若路徑中的所有邊e1，e2，…，ek互不相同，則稱此路徑為簡單路徑或一條跡；若回路中的所有邊e1，e2，…，ek互不相同，則稱此回路為簡單回路或一條閉跡；若路徑中的所有結點v0，v1，…，vk互不相同（從而所有邊互不相同），則稱此路徑為基本路徑或者初級路徑、路徑；若回路中除v0＝vk外的所有結點v0，v1，…，vk-1互不相同（從而所有邊互不相同），則稱此回路為基本回路或者初級回路、圈?；韭窂?或基本回路)一定是簡單路徑(或簡單回路)，但反之則不一定。簡單路徑與基本路徑第三十一頁第三十二頁，共63頁。注意：在不會引起誤解的情況下，一條路徑v0e1v1e2v2…envn也可以用邊的序列e1e2…en來表示，這種表示方法對于有向圖來說較為方便。在簡單圖中，一條路徑v0e1v1e2v2…envn也可以用結點的序列v0v1v2…vn來表示。在路徑與回路的定義中，我們將回路定義為路徑的特殊情況。因而，我們說某條路徑，它可能是回路。但當我們說一基本路徑時，一般是指它不是基本回路的情況。第三十二頁第三十三頁，共63頁。在圖G＝<V，E>中，對

vi，vj

V，如果從短程線、距離vi到vj存在路徑，則稱長度最短的路徑為從vi到vj的短程線，從vi到vj的短程線的長度稱為從vi到vj的距離，記為d(vi,vj)。d(vi，vj)滿足下列性質：

d(vi,vj)≥0；

d(vi,vi)＝0；

d(vi,vk)+d(vk，vj)≥d(vi，vj)；(三角不等式) d(vi,vj)＝

(當vi到vj不存在路徑時)。第三十三頁第三十四頁，共63頁。在(a)中有： d(v2,v1)＝1， d(v3,v1)＝2， d(v1,v4)＝3，

d(v1,v2)＝2， d(v1,v3)＝4， d(v4,v1)＝3；在(b)中有：

d(v1,v3)＝2， d(v3,v7)＝3， d(v1,v7)＝4。短程線、距離第三十四頁第三十五頁，共63頁。可達定義設u,v為圖G＝<V,E>中的兩個結點，若存在從結點u到結點v的路徑，則稱從結點u到結點v是可達的，記為u→v。對任意結點u，規(guī)定u→u。定理

無向圖中結點之間的連通關系是等價關系。證明 1）自反性：……

2）對稱性：……

3）傳遞性：……由1）、2）、3）知，結點之間的連通關系是等價關系。第三十五頁第三十六頁，共63頁。有向圖結點之間的可達關系具有自反性和傳遞性，但一般說來，可達關系沒有對稱性。例如右圖中v3到v2可達，但v2到v3不可達。因此，可達關系不是等價關系?？蛇_第三十六頁第三十七頁，共63頁。定義若無向圖G＝<V，E>中任意兩個結點都是連通的，則稱G是連通圖，否則則稱G是非連通圖(或分離圖)。無向完全圖Kn（n≥1）都是連通圖，而多于一個結點的零圖都是非連通圖。定義無向圖G中的每個連通的劃分塊稱為G的一個連通分支，用p(G)表示G中的連通分支個數(shù)。無向圖G＝<V，E>是連通圖當且僅當p(G)＝1。無向圖的連通圖第三十七頁第三十八頁，共63頁。有向圖的連通性定義

設G＝<V,E>是一個有向圖，略去G中所有有向邊的方向得無向圖G'，如果無向圖G'是連通圖，則稱有向圖G是連通圖或稱為弱連通圖。否則稱G是非連通圖。G1、G2、G3是連通的有向圖G4是非連通的有向圖第三十八頁第三十九頁，共63頁。定義

設有向圖G＝<V,E>是連通圖，若G中任何一對結點之間至少有一個結點到另一個結點是可達的，則稱G是單向連通圖；若G中任何一對結點之間都是相互可達的，則稱G是強連通圖。有向圖的連通性若有向圖G是強連通圖，則它必是單向連通圖；若有向圖G是單向連通圖，則它必是（弱）連通圖。但是上述二命題的逆均不成立。第三十九頁第四十頁，共63頁。有向圖的連通性G3是強連通圖（當然它也是單向連通圖和弱連通圖）；G2是單向連通圖（當然它也是弱連通圖）；G1是弱連通圖。第四十頁第四十一頁，共63頁。定義

在有向圖G＝<V,E>中，設G'是G的弱分圖、單向分圖、強分圖子圖，如果

1）G'是強連通的（單向連通的、弱連通的）；

2）對任意G“

G，若G‘

G”，則G“不是強連通

的（單向連通的、弱連通的）。那么稱G'為G的強連通分支（單向連通分支、弱連通分支），或稱為強分圖（單向分圖、弱分圖）。顯然，如果不考慮邊的方向，弱連通分支對應相應的無向圖的連通分支。第四十一頁第四十二頁，共63頁。在圖G1中，弱分圖、單向分圖、強分圖由{v2}，{v6}和{v1,v3,v4,v5,v7}導出的子圖都是強連通分支；由{v1,v2,v3,v4,v5,v7}和{v1,v3,v4,v5,v6,v7}導出的子圖都是單向連通分支；G1本身為弱連通分支。在圖G2中，由{v1}，{v2}，{v3}，{v4}和{v5,v6,v7}導出的子圖都是強連通分支；由{v1,v2,v4}，{v1,v3,v4}和{v5,v6,v7}導出的子圖都是單向連通分支；由{v1,v2,v3,v4}和{v5,v6,v7}導出的子圖都是弱連通分支。第四十二頁第四十三頁，共63頁。在圖(a)中，結點v1，v2，v3，v4-僅位于強分圖{v1，v2，v3，v4}弱分圖、單向分圖、強分圖中，結點v5-僅位于強分圖{v5}中，但邊<v4，v5>、<v3，v5>都不位于強分圖中；結點v1，v2，v3，v4，v5-僅位于單向分圖{v1，v2，v3，v4，v5}，所有的邊也都僅位于單向分圖中；結點v1，v2，v3，v4，v5-僅位于弱分圖{v1，v2，v3，v4，v5}；所有的邊也都僅位于弱分圖中。在圖(b)中，結點v2，v3-和邊<v2，v3>同時位于兩個單向分圖{v1，v2，v3}和{v2，v3，v4}中。第四十三頁第四十四頁，共63頁。一個等價關系若在有向圖G＝<V,E>的結點集V上定義二元關系R為：<vi,vj>∈R當且僅當vi和vj在同一強（弱）連通分支中，

vi,vj∈V。顯然，R是一個等價關系。因為每一個結點vi和自身總在在同一強（弱）連通分支中，所以R是自反的；若結點vi和vj在同一強（弱）連通分支中，顯然vj和vi也在同一強（弱）連通分支中，所以R是對稱的；又若結點vi和vj在同一強（弱）連通分支中，結點vj和vk在同一強（弱）連通分支中，則vi和vj相互可達，vj和vk相互可達，因而vi和vk相互可達，故vi和vk在同一強（弱）連通分支中，所以R是傳遞的。第四十四頁第四十五頁，共63頁。圖的矩陣表示定義

設G＝<V,E>是一個線圖，V＝{v1,v2,…,vn}，E＝{e1,e2,…,en}，則n階方陣A＝(aij)n

n稱為G的鄰接矩陣。其中：鄰接矩陣是一個布爾矩陣無向線圖的鄰接矩陣是對稱的而有向線圖的鄰接矩陣不一定對稱第四十五頁第四十六頁，共63頁。鄰接矩陣：圖的矩陣表示第四十六頁第四十七頁，共63頁。鄰接矩陣的性質設G＝<V，E>是一個線圖，則有：當有向線圖代表關系時，其鄰接矩陣就是前面講過的關系矩陣。零圖的鄰接矩陣的元素全為零，并稱它為零矩陣。圖的每一結點都有自回路而再無其他邊時，則該圖的鄰接矩陣是單位矩陣。簡單圖的鄰接矩陣主對角元全為零。第四十七頁第四十八頁，共63頁。鄰接矩陣的性質設無向圖G＝<V,E>，V＝{v1,v2,…,vn}的鄰接矩陣A＝(aij)n×n，則第四十八頁第四十九頁，共63頁。鄰接矩陣的性質設有向圖G＝<V,E>，V＝{v1,v2,…,vn}的鄰接矩陣A＝(aij)n×n，則第四十九頁第五十頁，共63頁。鄰接矩陣的性質設圖G＝<V,E>，V＝{v1,v2,…,vn}的鄰接矩陣A＝(aij)n×n， 則aij表示從結點vi到結點vj長度為1的路徑數(shù)目，而A中所有元素之和為A中長度為1的路徑（包括回路）數(shù)目（若G是有向圖，它也是邊的數(shù)目； 若G是無向圖，它是邊的數(shù)目的二倍減去G中自回路的數(shù)目，因為當aii=1時，一條邊(vi,vj)即是一條從vi到vj的長度為1的路徑，也是一條從vj到vi的長度為1的路徑，而(vi,vi)只是一條長度為1的路徑，而不能再看作兩條）。第五十頁第五十一頁，共63頁。鄰接矩陣的性質令B＝(bij)＝A2＝A×A＝(aij(2))n

n，則有：此時，bij表示從vi到vj長度為2的路徑數(shù)目，如bij＝0，則無長度為2的路徑，而bii表示經過vi的長度為2的回路數(shù)目；為G中長度為2的路徑（含回路）總數(shù)，主對角線上元素之和 為G中長度為2的回路總數(shù)。第五十一頁第五十二頁，共63頁。鄰接矩陣的性質10)令C＝(cij)＝Am＝A×A×…×A＝(aij(m))n

n，則有：此時，cij表示從vi到vj長度為m的路徑數(shù)目，如cij＝0，則無長度為m的路徑，而cii給出了經過vi的長度為m的回路數(shù)目。

為G中長度為m的路徑（含回路）總數(shù)，主對角線上元素之和 為G中長度為m的回路總數(shù)。第五十二頁第五十三頁，共63頁。例G1中長度為2的路徑（含回路）總數(shù)為21，其中9條為回路。G1中長度為3的路徑（含回路）總數(shù)為48，其中10條為回路。第五十三頁第五十四頁，共63頁。例G2中長度為2的路徑（含回