離散數(shù)學(xué)圖論基礎(chǔ)知識(shí)剖析

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

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

V或者(u,v)∈V&V相對(duì)應(yīng)。第十四頁(yè)第十五頁(yè)，共63頁(yè)。在一個(gè)圖中，關(guān)聯(lián)結(jié)點(diǎn)vi和vj的邊e，無(wú)論是有向的還是無(wú)向的，均稱(chēng)邊e與結(jié)點(diǎn)vI和vj相關(guān)聯(lián)，而vi和vj稱(chēng)為鄰接點(diǎn)，否則稱(chēng)為不鄰接的；幾個(gè)概念關(guān)聯(lián)于同一個(gè)結(jié)點(diǎn)的兩條邊稱(chēng)為鄰接邊；圖中關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的邊稱(chēng)為環(huán)(或自回路)；圖中不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)稱(chēng)為孤立結(jié)點(diǎn)；僅由孤立結(jié)點(diǎn)組成的圖稱(chēng)為零圖；僅含一個(gè)結(jié)點(diǎn)的零圖稱(chēng)為平凡圖；含有n個(gè)結(jié)點(diǎn)、m條邊的圖稱(chēng)為(n，m)圖；第十五頁(yè)第十六頁(yè)，共63頁(yè)。若邊e與無(wú)序結(jié)點(diǎn)對(duì)(u，v)相對(duì)應(yīng)，則稱(chēng)邊e為無(wú)向邊,記為e＝(u，v)，這時(shí)稱(chēng)u，v是邊e的兩個(gè)端點(diǎn)；若邊e與有序結(jié)點(diǎn)對(duì)<u，v>相對(duì)應(yīng)，則稱(chēng)邊e為有向邊(或弧)，記為e＝<u，v>，這時(shí)稱(chēng)u是邊e的始點(diǎn)(或弧尾).v是邊e的終點(diǎn)(或弧頭)，統(tǒng)稱(chēng)為e的端點(diǎn)；每條邊都是無(wú)向邊的圖稱(chēng)為無(wú)向圖；每條邊都是有向邊的圖稱(chēng)為有向圖；有些邊是無(wú)向邊，而另一些是有向邊的圖稱(chēng)為混合圖。圖的分類(lèi)－按邊的方向用小圓圈表示V中的結(jié)點(diǎn)，用由u指向v的有向線段表示<u,v>，無(wú)向線段表示(u,v)。第十六頁(yè)第十七頁(yè)，共63頁(yè)。圖的分類(lèi)－按邊的方向上圖所示的三個(gè)圖分別表示為：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是無(wú)向圖，G2是有向圖，G3是混合圖。第十七頁(yè)第十八頁(yè)，共63頁(yè)。圖的分類(lèi)－按邊的方向設(shè)圖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是無(wú)向邊，e2、e5是有向邊。這是一個(gè)混合圖。第十八頁(yè)第十九頁(yè)，共63頁(yè)。在有向圖中，兩個(gè)結(jié)點(diǎn)間(包括結(jié)點(diǎn)自身間)若有同始點(diǎn)和同終點(diǎn)的幾條邊，則這幾條邊稱(chēng)為平行邊，在無(wú)向圖中，兩個(gè)結(jié)點(diǎn)間(包括結(jié)點(diǎn)自身間)若有幾條邊，則這幾條邊稱(chēng)為平行邊；兩結(jié)點(diǎn)vi，vj間相互平行的邊的條數(shù)稱(chēng)為邊(vi，vj)或<vi，vj>的重?cái)?shù)；含有平行邊的圖稱(chēng)為多重圖；非多重圖稱(chēng)為線圖；無(wú)自回路的線圖稱(chēng)為簡(jiǎn)單圖。圖的分類(lèi)－按邊的重?cái)?shù)G1、G2是多重圖，G3,G4是線圖，G4是簡(jiǎn)單圖。第十九頁(yè)第二十頁(yè)，共63頁(yè)。

賦權(quán)圖G是一個(gè)三重組<V,E,g>或四重組<V,E,f,g>，其中V是結(jié)點(diǎn)集合，E是邊的集合，f是從V到非負(fù)實(shí)數(shù)集合的函數(shù)，g是從E到非負(fù)實(shí)數(shù)集合的函數(shù)。非賦權(quán)圖稱(chēng)為無(wú)權(quán)圖。圖的分類(lèi)－按權(quán)第二十頁(yè)第二十一頁(yè)，共63頁(yè)。在無(wú)向圖G＝<V，E>中，與結(jié)點(diǎn)v(v

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

設(shè)有圖G＝<V,E>和圖G'＝<V',E'>。若V'

V，E'

E，則稱(chēng)G'是G的子圖，記為G'

G。若G'

G，且G'≠G（即V'

V或E'

E），則稱(chēng)G'是G的真子圖，記為G'

G。若V'=V，E'

E，則稱(chēng)G'是G的生成子圖。設(shè)V"

V且V"≠

，以V"為結(jié)點(diǎn)集，以兩個(gè)端點(diǎn)均在V"中的邊的全體為邊集的G的子圖稱(chēng)為V"導(dǎo)出的G的子圖，簡(jiǎn)稱(chēng)V"的導(dǎo)出子圖。第二十三頁(yè)第二十四頁(yè)，共63頁(yè)。

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

V(u

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

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

容易驗(yàn)證：G1≌G2，結(jié)點(diǎn)之間的對(duì)應(yīng)關(guān)系為：a→v1，b→v2，c→v3，d→v4，e→v5；G3≌G4；G5≌G6；但G7與G8不同構(gòu)。圖G5稱(chēng)為彼得森圖。第二十八頁(yè)第二十九頁(yè)，共63頁(yè)。圖的操作定義

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

E，用G-E

表示從G中刪除E

中所有邊得到的圖，稱(chēng)為刪除E

。設(shè)v∈V，用G-v表示從G中去掉結(jié)點(diǎn)v及v關(guān)聯(lián)的所有邊得到的圖，稱(chēng)為刪除結(jié)點(diǎn)v。又設(shè)V

V，用G-V

表示從G中刪除V

中所有結(jié)點(diǎn)及關(guān)聯(lián)的所有邊得到的圖，稱(chēng)為刪除V

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

vi，vj

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

d(vi,vj)≥0；

d(vi,vi)＝0；

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

(當(dāng)vi到vj不存在路徑時(shí))。第三十三頁(yè)第三十四頁(yè)，共63頁(yè)。在(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。短程線、距離第三十四頁(yè)第三十五頁(yè)，共63頁(yè)。可達(dá)定義設(shè)u,v為圖G＝<V,E>中的兩個(gè)結(jié)點(diǎn)，若存在從結(jié)點(diǎn)u到結(jié)點(diǎn)v的路徑，則稱(chēng)從結(jié)點(diǎn)u到結(jié)點(diǎn)v是可達(dá)的，記為u→v。對(duì)任意結(jié)點(diǎn)u，規(guī)定u→u。定理

無(wú)向圖中結(jié)點(diǎn)之間的連通關(guān)系是等價(jià)關(guān)系。證明 1）自反性：……

2）對(duì)稱(chēng)性：……

3）傳遞性：……由1）、2）、3）知，結(jié)點(diǎn)之間的連通關(guān)系是等價(jià)關(guān)系。第三十五頁(yè)第三十六頁(yè)，共63頁(yè)。有向圖結(jié)點(diǎn)之間的可達(dá)關(guān)系具有自反性和傳遞性，但一般說(shuō)來(lái)，可達(dá)關(guān)系沒(méi)有對(duì)稱(chēng)性。例如右圖中v3到v2可達(dá)，但v2到v3不可達(dá)。因此，可達(dá)關(guān)系不是等價(jià)關(guān)系。可達(dá)第三十六頁(yè)第三十七頁(yè)，共63頁(yè)。定義若無(wú)向圖G＝<V，E>中任意兩個(gè)結(jié)點(diǎn)都是連通的，則稱(chēng)G是連通圖，否則則稱(chēng)G是非連通圖(或分離圖)。無(wú)向完全圖Kn（n≥1）都是連通圖，而多于一個(gè)結(jié)點(diǎn)的零圖都是非連通圖。定義無(wú)向圖G中的每個(gè)連通的劃分塊稱(chēng)為G的一個(gè)連通分支，用p(G)表示G中的連通分支個(gè)數(shù)。無(wú)向圖G＝<V，E>是連通圖當(dāng)且僅當(dāng)p(G)＝1。無(wú)向圖的連通圖第三十七頁(yè)第三十八頁(yè)，共63頁(yè)。有向圖的連通性定義

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

設(shè)有向圖G＝<V,E>是連通圖，若G中任何一對(duì)結(jié)點(diǎn)之間至少有一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是可達(dá)的，則稱(chēng)G是單向連通圖；若G中任何一對(duì)結(jié)點(diǎn)之間都是相互可達(dá)的，則稱(chēng)G是強(qiáng)連通圖。有向圖的連通性若有向圖G是強(qiáng)連通圖，則它必是單向連通圖；若有向圖G是單向連通圖，則它必是（弱）連通圖。但是上述二命題的逆均不成立。第三十九頁(yè)第四十頁(yè)，共63頁(yè)。有向圖的連通性G3是強(qiáng)連通圖（當(dāng)然它也是單向連通圖和弱連通圖）；G2是單向連通圖（當(dāng)然它也是弱連通圖）；G1是弱連通圖。第四十頁(yè)第四十一頁(yè)，共63頁(yè)。定義

在有向圖G＝<V,E>中，設(shè)G'是G的弱分圖、單向分圖、強(qiáng)分圖子圖，如果

1）G'是強(qiáng)連通的（單向連通的、弱連通的）；

2）對(duì)任意G“

G，若G‘

G”，則G“不是強(qiáng)連通

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

vi,vj∈V。顯然，R是一個(gè)等價(jià)關(guān)系。因?yàn)槊恳粋€(gè)結(jié)點(diǎn)vi和自身總在在同一強(qiáng)（弱）連通分支中，所以R是自反的；若結(jié)點(diǎn)vi和vj在同一強(qiáng)（弱）連通分支中，顯然vj和vi也在同一強(qiáng)（弱）連通分支中，所以R是對(duì)稱(chēng)的；又若結(jié)點(diǎn)vi和vj在同一強(qiáng)（弱）連通分支中，結(jié)點(diǎn)vj和vk在同一強(qiáng)（弱）連通分支中，則vi和vj相互可達(dá)，vj和vk相互可達(dá)，因而vi和vk相互可達(dá)，故vi和vk在同一強(qiáng)（弱）連通分支中，所以R是傳遞的。第四十四頁(yè)第四十五頁(yè)，共63頁(yè)。圖的矩陣表示定義

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

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

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

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

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