數學建模圖論篇第1頁，共62頁，2023年，2月20日，星期六圖論原理一.圖的概念

一個圖G=<V(G),E(G)>,其中結點集V(G):是G的結點的非空集合.(V(G)≠Φ),簡記成V;邊集E(G):是G的邊的集合.有時簡記成E.結點:用表示,旁邊標上該結點的名稱.邊:有向邊:帶箭頭的弧線.從u到v的邊表示成(u,v)

無向邊:不帶箭頭的弧線.u和v間的邊表示成(u,v)rweV(G1)={r,e,w}E(G1)={<r,e>,<e,w>,<w,r>}ABCDe1e5e7e6e3e4e2G1:G2:V(G2)={A,B,C,D}E(G2)={e1,e2,e3,e4,e5,e6,e7}第2頁，共62頁，2023年，2月20日，星期六圖論原理在圖中,結點的相對位置不同,邊的曲直、長短無關緊要.鄰接點:與一邊關聯的兩個結點.

uvab

鄰接邊:關聯同一個結點的兩條邊.

環:只關聯一個結點的邊.

平行邊:在兩個結點之間關聯的多條邊.

二.有向圖與無向圖

有向圖:只有有向邊的圖.無向圖:只有無向邊的圖.e1ve2

第3頁，共62頁，2023年，2月20日，星期六圖論原理三.零圖與平凡圖

孤立結點:不與任何邊關聯的結點.u

零圖:僅由一些孤立結點構成的圖.a

即此圖的邊的集合E=Φbc

平凡圖:僅由一個孤立結點構成的圖.|V(G)|=1,|E(G)|=0四.簡單圖與多重圖

簡單圖:不含有環和平行邊的圖.

多重圖:含有平行邊的圖.

G:ABCDe1e5e7e6e3e4e2cba第4頁，共62頁，2023年，2月20日，星期六圖論原理五.無向圖結點v的度:

1.定義:G是個無向圖,v∈V(G),結點v所關聯邊數,稱之為結點v的度，或稱為v的次數.記作deg(v).(或d(v)).deg(a)=3,deg(b)=3,deg(c)=4,deg(d)=2,

一個環給結點的度是2.

2.無向圖的結點度序列:令G=<V,E>是無向圖,V={v1,v2,v3,…,vn},則稱:(deg(v1),deg(v2),der(v3),…,deg(vn))為圖G的結點度序列.例如上圖的結點度序列為:(3,5,4,2)cabd第5頁，共62頁，2023年，2月20日，星期六圖論原理3.圖的最大度Δ(G)與最小度δ(G)

:G=<V,E>是無向圖,

Δ(G)=max{deg(v)|v∈G}δ(G)=min{deg(v)|v∈G}上圖中Δ(G)=5δ(G)=2性質：每個無向圖所有結點度總和等于邊數的2倍.

即k-正則圖:一個無向簡單圖G中,如果Δ(G)=δ(G)=k則稱G為k-正則圖.∑deg(v)=2|E|v∈V第6頁，共62頁，2023年，2月20日，星期六圖論原理六.完全圖1.無向完全圖

定義:G是個簡單圖,如果每對不同結點之間都有邊相連則稱G是個無向完全圖.如果G有n個結點,則記作Kn.性質：無向完全圖Kn,有邊數n(n-1)/2證明:因為Kn中每個結點都與其余n-1個結點關聯,即每個結點的度均為n-1,所以Kn所有結點度數總和為n(n-1),設邊數為|E|,于是n(n-1)=2|E|所以|E|=n(n-1)/2K2K3K4K5第7頁，共62頁，2023年，2月20日，星期六圖論原理2.有向圖的完全圖

1).有向簡單完全圖:G是個有向簡單圖,如果任何兩個不同結點之間都有相互可達的邊,則稱它是有向簡單完全圖.例如:

性質:有n個結點的有向簡單完全圖有邊數為n(n-1).證明:顯然它的邊數是Kn邊數的2倍.所以是n(n-1).第8頁，共62頁，2023年，2月20日，星期六圖論原理2).有向完全圖(有向全圖)(它與完全關系圖一致)G是個有向圖如果任何兩個結點之間都有相互可達的邊,則稱它是有向完全圖.

其圖形如下:所以有n個結點的有向完全圖,有邊數n2.第9頁，共62頁，2023年，2月20日，星期六圖論原理七.子圖和生成子圖1.子圖:設G=<V,E>是圖,如果G’=<V’,E’>且V’V,V’≠Φ,E’E,則稱G’是G的子圖.可見G1,G2,G3都是K5的子圖.bcdeabcabcdeG1G2G3K5abcde第10頁，共62頁，2023年，2月20日，星期六圖論原理2.生成子圖設G=<V,E>是圖,G’=<V’,E’>,G’是G的子圖,如果V’=V,則稱G’是G的生成子圖.上例中,G1是K5的生成子圖.八.補圖由G的所有結點和為使G變成完全圖,所需要添加的那些邊組成的圖,稱之為G相對完全圖的補圖,簡稱G的補圖,記作

。GK5GG第11頁，共62頁，2023年，2月20日，星期六圖論原理圖的同構設G=<V,E>和G’=<V’,E’>是圖,如果存在雙射f:VV’

且任何vi,vj∈V,若邊(vi,vj)∈E,當且僅當邊(f(vi),f(vj))∈E’,(則稱G與G’同構,記作G≌G’.(同構圖要保持邊的“關聯”關系)例如:右邊所示的兩個圖:G=<V,E>G’=<V’,E’>構造映射f:VV’abcd1432a1b2c3d4a1b2c3d4第12頁，共62頁，2023年，2月20日，星期六圖論原理兩個圖同構的必要條件:1.結點個數相等.2.邊數相等.3.度數相同的結點數相等.4.對應的結點的度數相等.下面是同構的圖:abecd13452afbecd351624第13頁，共62頁，2023年，2月20日，星期六圖論原理判斷下列圖是否同構？和和和312abc第14頁，共62頁，2023年，2月20日，星期六圖論原理如果一個結點對可對應若干條邊，這種邊成為多重邊，包含多重邊的圖成為多重圖。帶權圖(賦權圖)

定義:設G=<V,E,W>,是個圖,如果G的每條邊e上都標有實數c(e)(c(e)∈W),稱這個數為邊e的權,而此邊為有權邊稱此圖為帶權圖.而無有權邊的圖則成為無權圖。例如右圖中v1v2v3v6的路長為12.v6v5v4v1v3v2365112336第15頁，共62頁，2023年，2月20日，星期六圖論原理通路與回路1.通路的定義:給定圖G=<V,E>,v0,v1,v2,,…,vn∈V,e1,e2,,…,en∈E，其中ei是關聯vi－1,vi的邊,則稱結點和邊的交叉序列為圖的通路。如v0e1v1e2v2…envn是連接v0到vn的路.v0是此路的起點,vn是此路的終點.路中含有的邊數n稱之為路的長度.如果其中每條邊的終點總是下一條邊的起點，則邊的序列可以簡寫成（v0,v1,v2,…,vn)例如右圖中:

v0e2v3e6v2是一條長度為2的路.v3v2v1v0e1e2e3e4e5e6第16頁，共62頁，2023年，2月20日，星期六圖論原理回路:如果一條路的起點和終點是一個結點,則稱此路是一個回路.如果一條路中所有邊都不同,則稱此路為跡或簡單通路.如果一條回路中所有邊都不同,則稱此回路為閉跡或簡單回路.如果一條路中所有結點都不同,則稱此路為基本通路.如果一條回路中所有結點都不同,則稱此路為基本回路.一條基本通路一定是簡單通路，但是一條簡單通路不一定是基本通路第17頁，共62頁，2023年，2月20日，星期六圖論原理性質：一個有向(n,m)圖中任何基本通路長度都小于或者等于n-1，任何基本回路長度都小于或者等于n。定義：從一有向圖的結點a到另一結點b間如果存在一條通路，則稱從a到b是可達的。無向圖的連通性定義：一個無向圖G，如果它的任何兩個結點間均是可達的，這稱圖G為連通圖；否則，稱為非連通圖。定義：一個有向圖G，如果忽略其邊的方向得到的無向圖是連通的，這稱為有向的連通圖。第18頁，共62頁，2023年，2月20日，星期六圖論原理對于有向的連通圖，還可以進一步將其分為三類：在簡單有向圖G中,如果任何兩個結點間相互可達,則稱G是強連通.如果任何一對結點間,至少有一個結點到另一個結點可達,則稱G是單向連通.如果將G看成無向圖后(即把有向邊看成無向邊)是連通的,則稱G是弱連通.(a)有回路adbca,強連通.(b)a到d,d到a,都不可達是弱連通.(c)單向連通.dcabdcabdcab(a)(b)(c)第19頁，共62頁，2023年，2月20日，星期六圖論原理歐拉圖:

1.歐拉通路:在無孤立結點的圖G中,如果存在一條路,它經過圖中每條邊一次且僅一次,稱此路為歐拉通路.

2.歐拉回路:在無孤立結點的圖G中,若存在一條回路,它經過圖中每條邊一次且僅一次,稱此回路為歐拉回路.

稱此圖為歐拉圖。在G1中:有歐拉路:

acbefgdcfh在G2中:有歐拉回路:v1v2v3v4v5v2v4v6v5v3v1agebdhcfG2G1v1v5v4v2v3v6第20頁，共62頁，2023年，2月20日，星期六圖論原理歐拉通路的判定方法：定理：無向連通圖G中結點a和b間存在歐拉通路的充分必要條件是a與b的次數均為奇數而其他結點的次數均為偶數。如果G有兩個奇數度結點:就從一個奇數度結點出發,每當到達一個偶數度結點,必然可以再經過另一條邊離開此結點,如此重復下去,經過所有邊后到達另一個奇數度結點如果G無奇數度結點,則可以從任何一個結點出發,去構造一條歐拉路.abcd1243第21頁，共62頁，2023年，2月20日，星期六圖論原理推論:無向圖G具有歐拉回路,當且僅當G是連通的,且所有結點的度都是偶數.從此推論得知,七橋問題的圖不是歐拉圖.歐拉路與歐拉回路問題,也稱一筆畫問題.ABCDe1e5e7e6e3e4e2第22頁，共62頁，2023年，2月20日，星期六圖論原理漢密爾頓圖(H圖)(Hamilton圖)Hamilton是英國數學家,在1959年,他提出Hamilton回路.H圖起源于一種游戲,這個游戲就是所謂周游世界問題.

例如,某個城市的街道如圖所示:該城市的所有交叉路口都有形象各異的精美的雕塑,吸引著許多游客,人人都想找到這樣的路徑:游遍各個景點再回到出發點----H回路.第23頁，共62頁，2023年，2月20日，星期六圖論原理1.定義:設G=<V,E>是個無向有限圖,

漢密爾頓路:通過G中每個結點恰好一次的路.

漢密爾頓回路(H回路):通過G中每個結點恰好一次的回路.

漢密爾頓圖(H圖):具有漢密爾頓回路(H回路)的圖.例如右圖中,就是H圖,因為它有H回路:1234561162534第24頁，共62頁，2023年，2月20日，星期六圖論原理2.漢密爾頓圖的判定:

到目前為止并沒有判定H圖的充分必要條件.定理1

(充分條件):G是完全圖,則G是H圖.定理2(充分條件)設G是有n(n>2)個結點的簡單圖,若對G中每對結點度數之和大于等于n,則G有一條H路(H回路)。K2K3K4K5第25頁，共62頁，2023年，2月20日，星期六圖論原理在圖G1中,滿足充分條件Δ(G)=4δ(G)=2任意兩個結點度數之和大于等于5,所以是H圖.注意:上述條件只是充分條件,而不是必要條件,即不滿足這個條件的,也可能有H路.例如:在圖G2中,并不滿足任意兩個結點度數之和大于等于3,但是卻有H路.15243dcabG2G1第26頁，共62頁，2023年，2月20日，星期六圖論原理定理3:(必要條件)若圖G=<V,E>有H回路,則對V的任何非空子有限集S,均有W(G-S)≤|S|,其中W(G-S)是從G中刪去S中所有結點及與這些結點關聯的邊所得到的子圖的連通分支數.用此定理可以判斷一個圖不是H圖.如右圖G,取S={c}不滿足W(G-S)≤|S|.cebad第27頁，共62頁，2023年，2月20日，星期六圖論原理圖的矩陣表示法圖的矩陣表示不僅是給出圖的一種表示方法,還可以通過這些矩陣討論有關圖的若干性質,更重要的是可以用矩陣形式將圖存入計算機中,在計算機中對圖作處理.這里主要討論圖的三種矩陣.一.鄰接矩陣

這是以結點與結點之間的鄰接關系確定的矩陣.第28頁，共62頁，2023年，2月20日，星期六圖論原理1.定義:設G=<V,E>是個簡單圖,V={v1,v2,v3,…,vn},一個n×n階矩陣A=(aij)稱為G的鄰接矩陣.其中:例如,給定無向圖G1和有向圖G2如圖所示:aij

={1vi與vj鄰接,即(vi,vj)∈E或<vj,vi>∈E0否則v1v5v4v2v3G1第29頁，共62頁，2023年，2月20日，星期六圖論原理v3v2v4v5v1G2第30頁，共62頁，2023年，2月20日，星期六圖論原理2.從鄰接矩陣看圖的性質:

無向圖:

每行1的個數=每列1的個數=對應結點的度

有向圖:

每行1的個數=對應結點的出度（P133）

每列1的個數=對應結點的入度第31頁，共62頁，2023年，2月20日，星期六圖論原理3.鄰接矩陣的乘積在(A(G1))2中a342

=2表示從v3到v4有長度為2的路有2條:v1v5v4v2v3G1v3v2v4,

v3v5v4第32頁，共62頁，2023年，2月20日，星期六圖論原理在(A(G1))3中a233=6表示從v2到v3有長度為3的路有6條:v2v1v2v3,v2v4v2v3,v2v3v2v3,v2v3v1v3,v2v3v5v3,v2v4v5v3第33頁，共62頁，2023年，2月20日，星期六圖論原理性質：設G=<V,E>是簡單圖,令V={v1,v2,v3,…,vn},G的鄰接矩陣(A(G))k中的第i行第j列元素aijk=m,表示在圖G中從vi到vj長度為k的路有m條.例子見教材P134

在實際應用中,有時只關心從一個結點到另一個結點是否有路,而不關心路有多長,比如電話網絡.這就促使我們定義可達矩陣.第34頁，共62頁，2023年，2月20日，星期六圖論原理二.可達性矩陣1.定義:設G=<V,E>是個簡單圖,V={v1,v2,v3,…,vn},一個n×n階矩陣P=(pij)稱為G的可達性矩陣.其中:可以根據鄰接矩陣A求可達矩陣.設|V(G)|=n

令A(k)是將Ak中的非0元素都寫成1,而得到的只含有0和1的0-1矩陣.于是可達矩陣P為:P=A＋A(2)＋A(3)＋...＋A(n)pij

={1vi到vj可達,(至少有一條路)0否則第35頁，共62頁，2023年，2月20日，星期六圖論原理按照矩陣相乘分別求出A(k)(k≥2),然后再＋即可得到可達性矩陣P。例如,G2如圖所示,求它的可達矩陣P.v3v2v4v5v1G2第36頁，共62頁，2023年，2月20日，星期六圖論原理P=A＋A(2)＋A(3)＋A(4)＋A(5)

所以0010000010100100100100010A=1001001011011010001001001A(2)=0110101011100100100000010A(3)=1001001011011010001001001A(4)==A(2)A(5)=A(3)1111101011111110101101011P=第37頁，共62頁，2023年，2月20日，星期六圖論原理無向圖的矩陣表示法：由于無向圖中的無向邊用兩條相反的有向邊替代，使無向圖轉換為有向圖，所以有向圖中的鄰接矩陣、可達性矩陣等均可適用于無向圖。性質：無向圖的鄰接矩陣都是對稱矩陣。多重圖及有權圖的矩陣表示法：多重圖G對應的矩陣A=(aij)中元素為aij

={k若vi與vj有k條有向邊相連0若從vi與vj無有向邊相連第38頁，共62頁，2023年，2月20日，星期六圖論原理有權圖G對應的矩陣A=(aij)中元素為矩陣與圖的連通性一無向圖為連通圖的充分必要條件是此圖的可達性矩陣除對角線元素外均為1。有向圖的強連通相當于無向連通圖。aij

={k若vi與vj有邊相連且此邊權為k0若從vi與vj無邊相連第39頁，共62頁，2023年，2月20日，星期六圖論原理

有向圖的單向連通的充分必要條件是可達性矩陣P及其轉置所組成的矩陣P’=P+PT除對角線元素外均為1。有向圖的弱連通的充分必要條件是其鄰接矩陣A及其轉置矩陣組成的矩陣A’=A+AT的可達性矩陣中除對角線元素外均為1。例8.12,見教材P138。第40頁，共62頁，2023年，2月20日，星期六常用圖樹與生成樹樹是一種特殊的圖,它是圖論中重要的概念之一,它有著廣泛的應用.在計算機科學中有如判定樹、語法樹、分類樹、搜索樹、目錄樹等等.一.樹(Tree)1.樹的定義:一個連通無回路的

無向圖T,稱之為樹.如(a)(a)第41頁，共62頁，2023年，2月20日，星期六常用圖2.葉結點:度數為1的結點,稱為葉結點.3.分支結點(內結點):度數大于1的結點.4.森林:一個無向圖的每個連通分支都是樹.如(b)(b)第42頁，共62頁，2023年，2月20日，星期六常用圖5.與樹定義等價的幾個命題定理:給定圖T,以下關于樹的定義是等價的.⑴無回路的連通圖.⑵無回路且m=n-1其中m是T的邊數,n是T的結點數.⑶連通的且m=n-1.⑷無回路但添加一條新邊則得到一條僅有的回路.⑸連通的,但刪去任一條邊,T便不連通.⑹每對結點之間有一條且僅有一條路.第43頁，共62頁，2023年，2月20日，星期六常用圖有向樹:在有向圖中如果不考慮邊的方向而構成樹，則稱此有向圖為有向樹。外向樹：如果一棵有向樹,恰有一個結點的入度為0,其余所有結點的入度均為1,則稱此樹為外向樹.

1.樹根:入度為0的結點.2.葉:出度為0的結點.3.分支結點(內結點):出度不為0的結點.外向樹結點的級:從根結點到某個結點的通路的長度,稱為該結點的級.第44頁，共62頁，2023年，2月20日，星期六常用圖外向樹可以表示親屬關系：父結點與子結點:如果<vi,vj>是根樹中的一條邊,則稱vi是vj的父結點,vj是vi的子結點.

祖先結點與后裔結點:在根樹中,如果從vi到vj有路,則稱vi是vj的祖先結點,vj是vi的后裔結點.內向樹：內向樹和外向樹的定義類似，它是出度為0的結點為根，其他結點出度都為1的樹。內向樹也類似的有分支結點、級等概念(P147)第45頁，共62頁，2023年，2月20日，星期六常用圖三.舉例:a)語法樹b)算術表達式樹((a+b)÷c)×(d－e)句子

動詞冠詞主語謂語短語形容詞名詞賓語The

little

boysaw

appleThe冠詞名詞×－÷+abced第46頁，共62頁，2023年，2月20日，星期六常用圖m元樹:在根樹中,如果每個結點的出度最大是m,則稱此樹是m元樹.m元完全樹:在根樹中（除葉外）,如果每個結點的出度都是m,則稱此樹是m元完全樹.m＝2時則稱為二元樹和二元完全樹。二叉樹便于在計算機內存貯,設有算術表達式：(3－(2×x))+((x-2)÷(3+x)×－÷+32xx2+－x3第47頁，共62頁，2023年，2月20日，星期六常用圖m元有序樹轉化成二元樹因為二叉樹便于存貯,也便于處理,所以通常可以將多叉樹化成二叉樹，方法是:1.每個結點保留左兒子結點,剪掉右邊其它分支.被剪掉的結點如下處理.2.同一個層次的結點,從左到右依次畫出.r

ecabdgfhijklrabcdhefgijkl第48頁，共62頁，2023年，2月20日，星期六常用圖生成樹在圖論的應用中,找出一個連通圖的所有不同的生成樹,以及找出最小生成樹是很有意義的.定義:如果圖G的生成子圖是樹,則稱此樹為G的生成樹.性質：

連通圖至少有一棵生成樹.賦權圖的最小生成樹定義:一棵生成樹中的所有邊的權之和稱為該生成樹的權.具有最小權的生成樹,稱為最小生成樹.第49頁，共62頁，2023年，2月20日，星期六常用圖最小生成樹很有實際應用價值.例如結點是城市名,邊的權表示兩個城市間的距離,從一個城市出發走遍各個城市,如何選擇長度最短的旅行路線.又如城市間的通信網絡問題,如何布線,使得總的線路長度最短.求最小生成樹算法---Kruskal算法:(避圈法)v1v5v4v2v3v8v6v712213772486653443第50頁，共62頁，2023年，2月20日，星期六常用圖Kruskal算法:設G是有n個結點,m條邊(m≥n-1)的連通圖.|S|=n-1,說明是樹最后S={a1,a2,a3,…,an}S=Φi=0j=1將所有邊按照權升序排序:e1,e2,e3,…,em|S|=n-1取ej使得S∪{ej}有回路?j=j+1i=i+1ai=ejS=S∪{ai}j=j+1輸出S停YNYN第51頁，共62頁，2023年，2月20日，星期六邊權邊權e28e34e23e38e17e24e45e57e16e78e56e35e46e67e58e12e1811222333444566778v1v5v4v2v3v8v6v712213772486653443v1v5v4v2v3v8v6v71212433第52頁，共62頁，2023年，2月20日，星期六常用圖

在實際應用中,如高速公路設計、印刷電路設計,都要求線路不交叉,這就是平面圖,一個圖能否畫在一個平面上,且任何邊都不交叉,這就是圖的平面化問題.這個問題在近些年來,特別是大規模集成電路的發展進一步促進了對平面圖的研究.1.定義

設G是無向圖,如果能將G的所有結點和邊都畫在一個平面上,且使得任何兩條邊除了端點外沒有其它交點,則稱G是個平面圖.一個圖表面上是個非平面圖,如果通過改變邊的位置就變成平面圖,稱此圖是可平面化的.第53頁，共62頁，2023年，2月20日，星期六例如右圖.就是可平面化的圖.

下面是兩個重要的非平面圖:K5和K3,3v1v5v4v2v3v1v5v4v2v3v1v5v4v2v3v1v5v4v2v3351624afbecdafbecd常用圖第54頁，共62頁，2023年，2月20日，星期六2.平面圖的面、邊界及面的次數

設G是個平面圖,圖中邊圍成的區域,其內部不含有結點,也不含有邊,稱這樣區域為G的一個面.

面的邊界:圍成一個面r的所有邊構成的回路,稱之為這個r面的邊界.此回路中的邊數,稱之為r面的次數,記作deg(r).

有限面與無限面:面的面積有限稱為有限面,反之稱為無限面.所有平面圖的外側都有一個無限面.例如,上圖中r1:邊界:ABCDFDAdeg(r1)=6r2:邊界:ABCAdeg(r2)=3r3:邊界:ACDAdeg(r3)=3r4:邊界:ADAdeg(r4)=2ADFBCr1r2r3r4常用圖第55頁，共62頁，2023年，2月20日，星期六常用圖3.歐拉公式性質1：G是個連通的平面圖,設n、m、r分別表示G中結點數、邊數、面數,則有

n-m+r=2稱此式為歐拉公式.性質2：(必要條件)設G是有n個結點、m條邊的連通簡單平面圖,若n≥3,則