圖論與代數(shù)結(jié)構(gòu)

圖論主要內(nèi)容《圖論與代數(shù)結(jié)構(gòu)》第一章

基本概念 1.1,1.2(1,2,3,7)第二章

道路與回路 2.1,2.3,2.4第三章

樹 3.1,3.6,3.7實(shí)例城市街道如圖，市政府規(guī)定各街道只能單向行駛，問如何定向才能保證車輛能從一個地點(diǎn)到達(dá)任一個其他的地點(diǎn)。第一章基本概念

1.1圖的概念許多事物以及它們之間的聯(lián)系可以用圖形直觀地表示用結(jié)點(diǎn)表示事物

用邊表示它們之間的聯(lián)系圖論的研究對象

結(jié)點(diǎn)和邊構(gòu)成的圖形圖的概念定義1.1.1

二元組(V(G),E(G))稱為圖。其中， V(G)是非空集合，稱為結(jié)點(diǎn)集 E(G)是V(G)諸結(jié)點(diǎn)之間邊的集合

常用G=(V,E)表示圖只討論有限圖,即V和E都是有限集

給定某個圖G=(V,E),如果不加特殊說明,V={v1,v2,…,vn},E={e1,e2,…,em}即結(jié)點(diǎn)數(shù)|V|=n,邊數(shù)|E|=m邊和圖用結(jié)點(diǎn)表示邊 ek=(vi,vj)(稱vi和vj是相鄰結(jié)點(diǎn),或者ek分別與vi,vj相關(guān)聯(lián))有向邊(弧)，有向圖 vi是ek的始點(diǎn)，vj是ek的終點(diǎn)無向邊，無向圖 vi,vj是ek的端點(diǎn)自環(huán)(圈)

只有一個結(jié)點(diǎn)相關(guān)聯(lián)的邊重邊、多重圖

同一對結(jié)點(diǎn)之間存在多條邊有向圖與無向圖ABCD有向圖G1ABCDE無向圖G2G1=（V1,E1）

V1={A,B,C,D}E1={(A,B),(A,C),(C,D),(D,A)}G2=（V2,E2)V2={A,B,C,D,E}E2={(A,B),(A,C),(B,D),(B,E),(C,E),(D,E)}圖的概念定義1.1.2 G=(V,E)的某結(jié)點(diǎn)v所關(guān)聯(lián)的邊數(shù)稱為該結(jié)點(diǎn)的度，用d(v)表示。如果v帶有自環(huán)，則自環(huán)對d(v)的貢獻(xiàn)為2有向圖

出度(正度)d+(v):以結(jié)點(diǎn)v為始點(diǎn)的邊的數(shù)目

入度(負(fù)度)d-(v):以結(jié)點(diǎn)v為終點(diǎn)的邊的數(shù)目 d(v)=d+(v)+d-(v)圖的概念定義1.1.3

任意兩結(jié)點(diǎn)間最多只有一條邊，且不存在自環(huán)的無向圖稱為簡單圖沒有任何邊的簡單圖(V,?)叫空圖，用Nn表示.若此時恰有|V|=1,稱為平凡圖任何兩個結(jié)點(diǎn)間都有邊的簡單圖稱為完全圖，用Kn表示.Kn中每個結(jié)點(diǎn)的度都是n-1圖的概念性質(zhì)1.1.1

設(shè)G=(V,E)有n個結(jié)點(diǎn)，m條邊，則證明：由于每條邊e=(u,v)對結(jié)點(diǎn)u和v度的貢獻(xiàn)各為1，因此m條邊對全部結(jié)點(diǎn)的總貢獻(xiàn)率為2m圖的概念性質(zhì)1.1.2 G中度為奇數(shù)的結(jié)點(diǎn)必為偶數(shù)個．證明：G中任一結(jié)點(diǎn)的度或?yàn)榕紨?shù)或?yàn)槠鏀?shù)，設(shè)Ve是度為偶的結(jié)點(diǎn)集，Vo是度為奇的結(jié)點(diǎn)集，于是有因此上式左邊第二項(xiàng)也為偶數(shù)，也即度為奇數(shù)的結(jié)點(diǎn)必為偶數(shù)個圖的概念性質(zhì)1.1.3

有向圖G中正度之和等于負(fù)度之和．這是因?yàn)槊織l邊對結(jié)點(diǎn)的正、負(fù)度貢獻(xiàn)各為1性質(zhì)1.1.4 Kn的邊數(shù)是n(n-1)/2.證明:Kn中各結(jié)點(diǎn)的度都是(n-1),由性質(zhì)1.1.1就可以得到圖的概念性質(zhì)1.1.5

非空簡單圖G中一定存在度相同的結(jié)點(diǎn)．證明：設(shè)在G中不存在孤立結(jié)點(diǎn)，則對n個結(jié)點(diǎn)的簡單圖，每個結(jié)點(diǎn)度d(v)的取值范圍是1~(n-1)，由抽屜(鴿巢)原理，一定存在兩個度相同的結(jié)點(diǎn)．若存在一個孤立的結(jié)點(diǎn)，亦類似可證．圖的概念定義1.1.4

如果圖G=(V,E)的每條邊ek=(vi,vj)都賦以一個實(shí)數(shù)wk作為該邊的權(quán)，則稱G是賦權(quán)圖．特別地，如果這些權(quán)都是正實(shí)數(shù)，就稱G是正權(quán)圖權(quán)可以表示該邊的長度、時間、費(fèi)用或者容量等23.57.8圖的概念定義1.1.5

給定G=(V,E),如果存在另一個G’=(V’,E’),滿足V’V,E’

E,則稱G’是G的一個子圖

特別地，如果V’=V,就稱G’是G的支撐子圖或者生成子圖

如果V’V,且E’包含了G在結(jié)點(diǎn)子集V’之間的所有邊,則稱G’是G的導(dǎo)出子圖G自身既是支撐子圖，又是導(dǎo)出子圖；

空圖是G的支撐子圖； G自身和空圖稱為平凡子圖在如下圖中，給出了圖G以及它的真子圖G’和G’’，其中， G’是結(jié)點(diǎn)集為{v1，v2，v4，v5，v6}的導(dǎo)出子圖; G’’是支撐子圖(或生成子圖)。圖的概念定義1.1.6

給定兩個圖G1=(V1,E1),G2=(V2,E2).令 G1G2=(V,E),其中V=V1V2,E=E1E2; G1G2=(V,E),其中V=V1V2,E=E1E2; G1G2=(V,E),其中V=V1V2,E=E1E2;

分別稱為G1和G2的并，交和對稱差圖的增刪G-H

表示在G中刪去一個子圖H，即刪掉H中的各條邊(支撐子圖)

特別地，對于簡單圖G，稱Kn-G為G的補(bǔ)圖自補(bǔ)圖：G-v

表示從G中刪去結(jié)點(diǎn)v及其關(guān)聯(lián)的邊(導(dǎo)出子圖)G-e

表示從G中刪去邊e(支撐子圖)G+eij

表示在G中增加某條邊ek=(vi,vj)圖的概念無向圖的鄰點(diǎn)集

Γ(v)={u|(v,u)E}定義1.1.7

設(shè)v是有向圖G的一個結(jié)點(diǎn)，則

Γ+(v)={u|(v,u)E}

稱為v的直接后繼集或者外鄰集;相應(yīng)地

Γ-(v)={u|(u,v)E}

稱為v的直接前趨集或者內(nèi)鄰集圖的同構(gòu)如下四張圖所表示的圖形實(shí)際上都是一樣的圖的同構(gòu)定義1.1.8

兩個圖G1=(V1,E1),G2=(V2,E2),如果V1和V2之間存在雙射f,而且(u,v)E1,當(dāng)且僅當(dāng)(f(u),f(v))E2時,稱G1和G2同構(gòu)

記作G1?G2如何判斷兩個圖是否同構(gòu)呢？

答案：迄今為止還沒有有效的算法。假如G1?G2，則必須滿足：(1)|V(G1)|=|V(G2)|,|E(G1)|=|E(G2)|

(2)G1和G2結(jié)點(diǎn)度的非增序列相同(3)存在同構(gòu)的導(dǎo)出子圖(用來判斷不同構(gòu))上述是必要條件,但不是充分條件，只能用來判斷圖的不同構(gòu)。例如下面兩個圖是不同構(gòu)的。圖的同構(gòu)(d)≌(e)≌(f).(d)所示圖稱為彼德森圖1.2圖的代數(shù)表示鄰接矩陣權(quán)矩陣關(guān)聯(lián)矩陣鄰接表鄰接矩陣鄰接矩陣表示結(jié)點(diǎn)之間的鄰接關(guān)系無權(quán)值的有向圖的鄰接矩陣

設(shè)有向圖具有n個結(jié)點(diǎn)，則用n行n列的布爾矩陣A表示該有向圖；并且A[i,j]=1,如果i至j有一條有向邊；A[i,j]=0,如果i至j沒有一條有向邊 vi出度:i行之和;vj入度:j列之和

注:可以表示自環(huán)，但無法表示重邊ABCD表示成右圖矩陣0110000000011000鄰接矩陣無權(quán)值的無向圖的鄰接矩陣(對稱矩陣)

設(shè)無向圖具有n個結(jié)點(diǎn)，則用n行n列的布爾矩陣

A表示該無向圖；并且A[i,j]=1,如果i至j有一條無向邊；A[i,j]=0,如果i至j沒有一條無向邊 vi結(jié)點(diǎn)的度:i行或i列之和表示成右圖矩陣0110010011100010100101110ABCDE權(quán)矩陣用來表示賦權(quán)圖例如：有向圖的加權(quán)鄰接矩陣

設(shè)有向圖具有n個結(jié)點(diǎn)，則用n行n列的矩陣

A表示該有向圖；并且

A[i,j]=wij,如果i至j有一條有向邊且它的權(quán)值為wij;A[i,j]=0,如果i至j沒有一條有向邊ABCD表示成右圖矩陣0230000600073050253367關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣表示結(jié)點(diǎn)與邊之間的關(guān)聯(lián)關(guān)系設(shè)G=(V,E),|V|=n,|E|=m.則G的關(guān)聯(lián)矩陣B是n×m的矩陣有向圖的關(guān)聯(lián)矩陣

B[i,j]=1,如果vi是邊ej=(vi,vk)的始點(diǎn) B[i,j]=-1,如果vi是邊ej=(vk,vi)的終點(diǎn) B[i,j]=0,其他(vi既不是ej的始點(diǎn)亦非終點(diǎn))關(guān)聯(lián)矩陣有向圖關(guān)聯(lián)矩陣的性質(zhì)每列只有兩個非零元：1和-1第i行非零元的數(shù)目恰是結(jié)點(diǎn)vi的度，其中1元的數(shù)目是出度，-1元的數(shù)目是入度能夠表示重邊，但不能表示自環(huán)關(guān)聯(lián)矩陣無向圖的關(guān)聯(lián)矩陣

B[i,j]=1,如果vi是邊ej的端點(diǎn) B[i,j]=0,如果vi不是邊ej的端點(diǎn)矩陣表示的特點(diǎn)如果可以用鄰接矩陣/關(guān)聯(lián)矩陣表示某個圖G,則表示是唯一的鄰接矩陣不能表示重邊

關(guān)聯(lián)矩陣不能表示自環(huán)從數(shù)據(jù)結(jié)構(gòu)和算法的角度來看，矩陣表示法占據(jù)的存儲空間較大，可能增加計算復(fù)雜度鄰接表單鏈表表結(jié)點(diǎn)的結(jié)構(gòu)????鄰接點(diǎn)的編號邊權(quán)值下一個結(jié)點(diǎn)的地址指針123435346723?34?46?47?13?35?ABCD有向圖G1ABCDBCAD0123nullnullnullnulldataadjdestlink無向圖G2ABCDEABBC01234nulldataadjADAEBECDCDEEBnullnullnullnulldestlink鄰接表鄰接表特點(diǎn)便于增加和刪除邊可以表示重邊和自環(huán)可以唯一表示任意一個圖所需存儲空間較小圖的應(yīng)用三個量杯容量分別是8升，5升，3升，現(xiàn)8升的量杯裝滿了水，問怎樣才能把水分成2個4升的。初始狀態(tài)(8,0,0)，終止?fàn)顟B(tài)(4,4,0)狀態(tài)轉(zhuǎn)移圖：狀態(tài)看作點(diǎn)，狀態(tài)間的轉(zhuǎn)化看作邊答案:(8,0,0)→(5,0,3)→(5,3,0)→(2,3,3)→(2,5,1)→(7,0,1)→(7,1,0)→(4,1,3)→(4,4,0)圖的應(yīng)用人狼羊菜過河

有一個人帶著一只