圖論主要內容《圖論與代數結構》第一章

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

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

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

1.1圖的概念許多事物以及它們之間的聯系可以用圖形直觀地表示用結點表示事物

用邊表示它們之間的聯系圖論的研究對象

結點和邊構成的圖形圖的概念定義1.1.1

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

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

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

只有一個結點相關聯的邊重邊、多重圖

同一對結點之間存在多條邊有向圖與無向圖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)的某結點v所關聯的邊數稱為該結點的度，用d(v)表示。如果v帶有自環，則自環對d(v)的貢獻為2有向圖

出度(正度)d+(v):以結點v為始點的邊的數目

入度(負度)d-(v):以結點v為終點的邊的數目 d(v)=d+(v)+d-(v)圖的概念定義1.1.3

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

設G=(V,E)有n個結點，m條邊，則證明：由于每條邊e=(u,v)對結點u和v度的貢獻各為1，因此m條邊對全部結點的總貢獻率為2m圖的概念性質1.1.2 G中度為奇數的結點必為偶數個．證明：G中任一結點的度或為偶數或為奇數，設Ve是度為偶的結點集，Vo是度為奇的結點集，于是有因此上式左邊第二項也為偶數，也即度為奇數的結點必為偶數個圖的概念性質1.1.3

有向圖G中正度之和等于負度之和．這是因為每條邊對結點的正、負度貢獻各為1性質1.1.4 Kn的邊數是n(n-1)/2.證明:Kn中各結點的度都是(n-1),由性質1.1.1就可以得到圖的概念性質1.1.5

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

如果圖G=(V,E)的每條邊ek=(vi,vj)都賦以一個實數wk作為該邊的權，則稱G是賦權圖．特別地，如果這些權都是正實數，就稱G是正權圖權可以表示該邊的長度、時間、費用或者容量等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在結點子集V’之間的所有邊,則稱G’是G的導出子圖G自身既是支撐子圖，又是導出子圖；

空圖是G的支撐子圖； G自身和空圖稱為平凡子圖在如下圖中，給出了圖G以及它的真子圖G’和G’’，其中， G’是結點集為{v1，v2，v4，v5，v6}的導出子圖; 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的補圖自補圖：G-v

表示從G中刪去結點v及其關聯的邊(導出子圖)G-e

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

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

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

設v是有向圖G的一個結點，則

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

稱為v的直接后繼集或者外鄰集;相應地

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

稱為v的直接前趨集或者內鄰集圖的同構如下四張圖所表示的圖形實際上都是一樣的圖的同構定義1.1.8

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

記作G1?G2如何判斷兩個圖是否同構呢？

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

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

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

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

設無向圖具有n個結點，則用n行n列的布爾矩陣

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

設有向圖具有n個結點，則用n行n列的矩陣

A表示該有向圖；并且

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

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

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

關聯矩陣不能表示自環從數據結構和算法的角度來看，矩陣表示法占據的存儲空間較大，可能增加計算復雜度鄰接表單鏈表表結點的結構????鄰接點的編號邊權值下一個結點的地址指針123435346723?34?46?47?13?35?ABCD有向圖G1ABCDBCAD0123nullnullnullnulldataadjdestlink無向圖G2ABCDEABBC01234nulldataadjADAEBECDCDEEBnullnullnullnulldestlink鄰接表鄰接表特點便于增加和刪除邊可以表示重邊和自環可以唯一表示任意一個圖所需存儲空間較小圖的應用三個量杯容量分別是8升，5升，3升，現8升的量杯裝滿了水，問怎樣才能把水分成2個4升的。初始狀態(8,0,0)，終止狀態(4,4,0)狀態轉移圖：狀態看作點，狀態間的轉化看作邊答案:(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)圖的應用人狼羊菜過河

有一個人帶著一只