數(shù)學(xué)建模圖論篇

數(shù)學(xué)建模圖論篇第1頁，課件共62頁，創(chuàng)作于2023年2月圖論原理一.圖的概念

一個圖G=<V(G),E(G)>,其中結(jié)點集V(G):是G的結(jié)點的非空集合.(V(G)≠Φ),簡記成V;邊集E(G):是G的邊的集合.有時簡記成E.結(jié)點:用表示,旁邊標(biāo)上該結(jié)點的名稱.邊:有向邊:帶箭頭的弧線.從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頁，創(chuàng)作于2023年2月圖論原理在圖中,結(jié)點的相對位置不同,邊的曲直、長短無關(guān)緊要.鄰接點:與一邊關(guān)聯(lián)的兩個結(jié)點.

uvab

鄰接邊:關(guān)聯(lián)同一個結(jié)點的兩條邊.

環(huán):只關(guān)聯(lián)一個結(jié)點的邊.

平行邊:在兩個結(jié)點之間關(guān)聯(lián)的多條邊.

二.有向圖與無向圖

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

第3頁，課件共62頁，創(chuàng)作于2023年2月圖論原理三.零圖與平凡圖

孤立結(jié)點:不與任何邊關(guān)聯(lián)的結(jié)點.u

零圖:僅由一些孤立結(jié)點構(gòu)成的圖.a

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

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

簡單圖:不含有環(huán)和平行邊的圖.

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

G:ABCDe1e5e7e6e3e4e2cba第4頁，課件共62頁，創(chuàng)作于2023年2月圖論原理五.無向圖結(jié)點v的度:

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

一個環(huán)給結(jié)點的度是2.

2.無向圖的結(jié)點度序列:令G=<V,E>是無向圖,V={v1,v2,v3,…,vn},則稱:(deg(v1),deg(v2),der(v3),…,deg(vn))為圖G的結(jié)點度序列.例如上圖的結(jié)點度序列為:(3,5,4,2)cabd第5頁，課件共62頁，創(chuàng)作于2023年2月圖論原理3.圖的最大度Δ(G)與最小度δ(G)

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

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

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

定義:G是個簡單圖,如果每對不同結(jié)點之間都有邊相連則稱G是個無向完全圖.如果G有n個結(jié)點,則記作Kn.性質(zhì)：無向完全圖Kn,有邊數(shù)n(n-1)/2證明:因為Kn中每個結(jié)點都與其余n-1個結(jié)點關(guān)聯(lián),即每個結(jié)點的度均為n-1,所以Kn所有結(jié)點度數(shù)總和為n(n-1),設(shè)邊數(shù)為|E|,于是n(n-1)=2|E|所以|E|=n(n-1)/2K2K3K4K5第7頁，課件共62頁，創(chuàng)作于2023年2月圖論原理2.有向圖的完全圖

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

性質(zhì):有n個結(jié)點的有向簡單完全圖有邊數(shù)為n(n-1).證明:顯然它的邊數(shù)是Kn邊數(shù)的2倍.所以是n(n-1).第8頁，課件共62頁，創(chuàng)作于2023年2月圖論原理2).有向完全圖(有向全圖)(它與完全關(guān)系圖一致)G是個有向圖如果任何兩個結(jié)點之間都有相互可達(dá)的邊,則稱它是有向完全圖.

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

。GK5GG第11頁，課件共62頁，創(chuàng)作于2023年2月圖論原理圖的同構(gòu)設(shè)G=<V,E>和G’=<V’,E’>是圖,如果存在雙射f:VV’

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

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

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

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

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

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

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

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

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

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

漢密爾頓圖(H圖):具有漢密爾頓回路(H回路)的圖.例如右圖中,就是H圖,因為它有H回路:1234561162534第24頁，課件共62頁，創(chuàng)作于2023年2月圖論原理2.漢密爾頓圖的判定:

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

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

這是以結(jié)點與結(jié)點之間的鄰接關(guān)系確定的矩陣.第28頁，課件共62頁，創(chuàng)作于2023年2月圖論原理1.定義:設(shè)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頁，創(chuàng)作于2023年2月圖論原理v3v2v4v5v1G2第30頁，課件共62頁，創(chuàng)作于2023年2月圖論原理2.從鄰接矩陣看圖的性質(zhì):

無向圖:

每行1的個數(shù)=每列1的個數(shù)=對應(yīng)結(jié)點的度

有向圖:

每行1的個數(shù)=對應(yīng)結(jié)點的出度（P133）

每列1的個數(shù)=對應(yīng)結(jié)點的入度第31頁，課件共62頁，創(chuàng)作于2023年2月圖論原理3.鄰接矩陣的乘積在(A(G1))2中a342

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

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

在實際應(yīng)用中,有時只關(guān)心從一個結(jié)點到另一個結(jié)點是否有路,而不關(guān)心路有多長,比如電話網(wǎng)絡(luò).這就促使我們定義可達(dá)矩陣.第34頁，課件共62頁，創(chuàng)作于2023年2月圖論原理二.可達(dá)性矩陣1.定義:設(shè)G=<V,E>是個簡單圖,V={v1,v2,v3,…,vn},一個n×n階矩陣P=(pij)稱為G的可達(dá)性矩陣.其中:可以根據(jù)鄰接矩陣A求可達(dá)矩陣.設(shè)|V(G)|=n

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

={1vi到vj可達(dá),(至少有一條路)0否則第35頁，課件共62頁，創(chuàng)作于2023年2月圖論原理按照矩陣相乘分別求出A(k)(k≥2),然后再＋即可得到可達(dá)性矩陣P。例如,G2如圖所示,求它的可達(dá)矩陣P.v3v2v4v5v1G2第36頁，課件共62頁，創(chuàng)作于2023年2月圖論原理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頁，創(chuàng)作于2023年2月圖論原理無向圖的矩陣表示法：由于無向圖中的無向邊用兩條相反的有向邊替代，使無向圖轉(zhuǎn)換為有向圖，所以有向圖中的鄰接矩陣、可達(dá)性矩陣等均可適用于無向圖。性質(zhì)：無向圖的鄰接矩陣都是對稱矩陣。多重圖及有權(quán)圖的矩陣表示法：多重圖G對應(yīng)的矩陣A=(aij)中元素為aij

={k若vi與vj有k條有向邊相連0若從vi與vj無有向邊相連第38頁，課件共62頁，創(chuàng)作于2023年2月圖論原理有權(quán)圖G對應(yīng)的矩陣A=(aij)中元素為矩陣與圖的連通性一無向圖為連通圖的充分必要條件是此圖的可達(dá)性矩陣除對角線元素外均為1。有向圖的強連通相當(dāng)于無向連通圖。aij

={k若vi與vj有邊相連且此邊權(quán)為k0若從vi與vj無邊相連第39頁，課件共62頁，創(chuàng)作于2023年2月圖論原理

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

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

1.樹根:入度為0的結(jié)點.2.葉:出度為0的結(jié)點.3.分支結(jié)點(內(nèi)結(jié)點):出度不為0的結(jié)點.外向樹結(jié)點的級:從根結(jié)點到某個結(jié)點的通路的長度,稱為該結(jié)點的級.第44頁，課件共62頁，創(chuàng)作于2023年2月常用圖外向樹可以表示親屬關(guān)系：父結(jié)點與子結(jié)點:如果<vi,vj>是根樹中的一條邊,則稱vi是vj的父結(jié)點,vj是vi的子結(jié)點.

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

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

little

boysaw

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

ecabdgfhijklrabcdhefgijkl第48頁，課件共62頁，創(chuàng)作于2023年2月常用圖生成樹在圖論的應(yīng)用中,找出一個連通圖的所有不同的生成樹,以及找出最小生成樹是很有意義的.定義:如果圖G的生成子圖是樹,則稱此樹為G的生成樹.性質(zhì)：

連通圖至少有一棵生成樹.賦權(quán)圖的最小生成樹定義:一棵生成樹中的所有邊的權(quán)之和稱為該生成樹的權(quán).具有最小權(quán)的生成樹,稱為最小生成樹.第49頁，課件共62頁，創(chuàng)作于2023年2月常用圖最小生成樹很有實際應(yīng)用價值.例如結(jié)點是城市名,邊的權(quán)表示兩個城市間的距離,從一個城市出發(fā)走遍各個城市,如何選擇長度最短的旅行路線.又如城市間的通信網(wǎng)絡(luò)問題,如何布線,使得總的線路長度最短.求最小生成樹算法---Kruskal算法:(避圈法)v1v5v4v2v3v8v6v712213772486653443第50頁，課件共62頁，創(chuàng)作于2023年2月常用圖Kruskal算法:設(shè)G是有n個結(jié)點,m條邊(m≥n-1)的連通圖.|S|=n-1,說明是樹最后S={a1,a2,a3,…,an}S=Φi=0j=1將所有邊按照權(quán)升序排序: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頁，創(chuàng)作于2023年2月邊權(quán)邊權(quán)e28e34e23e38e17e24e45e57e16e78e56e35e46e67e58e12e1811222333444566778v1v5v4v2v3v8v6v712213772486653443v1v5v4v2v3v8v6v71212433第52頁，課件共62頁，創(chuàng)作于2023年2月常用圖

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

設(shè)G是無向圖,如果能將G的所有結(jié)點和邊都畫在一個平面上,且使得任何兩條邊除了端點外沒有其它交點,則稱G是個平面圖.一個圖表面上是個非平面圖,如果通過改變邊的位置就變成平面圖,稱此圖是可平面化的.第53頁，課件共62頁，創(chuàng)作于2023年2月例如右圖.就是可平面化的圖.

下面是兩個重要的非平面圖:K5和K3,3v1v5v4v2v3v1v5v4v2v3v1v5v4v2v3v1v5v4v2v3351624afbecdafbecd常用圖第54頁，課件共62頁，創(chuàng)作于2023年2月2.平面圖的面、邊界及面的次數(shù)

設(shè)G是個平面圖,圖中邊圍成的區(qū)域,其內(nèi)部不含有結(jié)點,也不含有邊,稱這樣區(qū)域為G的一個面.

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

有限面與無限面:面的面積有限稱為有限面,反之稱為無限面.所有平面圖的外側(cè)都有一個無限面.例如,上圖中r1:邊界:ABCDFDAdeg(r1)=6r2:邊界:ABCAdeg(r2)=3r3:邊界:ACDAdeg(r3)=3r4:邊界:ADAdeg(r4)=2ADFBCr1r2r3r4常用圖第55頁，課件共62頁，創(chuàng)作于2023年2月常用圖3.歐拉公式性質(zhì)1：G是個連通的平面圖,設(shè)n、m、r分別表示G中結(jié)點數(shù)、邊數(shù)、面數(shù),則有

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