圖論及其算法數(shù)模

圖論及其算法數(shù)模第1頁，共117頁，2023年，2月20日，星期六七橋問題的分析

七橋問題看起來不難，很多人都想試一試，但沒有人找到答案.后來有人寫信告訴了當(dāng)時的著名數(shù)學(xué)家歐拉.千百人的失敗使歐拉猜想,也許那樣的走法根本不可能.1876年,他證明了自己的猜想.Euler把南北兩岸和兩個島抽象成四個點,將連接這些陸地的橋用連接相應(yīng)兩點的一條線來表示,就得到如下一個簡圖:SNAB第2頁，共117頁，2023年，2月20日，星期六歐拉的結(jié)論歐拉指出:一個線圖中存在通過每邊一次僅一次回到出發(fā)點的路線的充要條件是:1)圖是連通的,即任意兩點可由圖中的一些邊連接起來;2)與圖中每一頂點相連的邊必須是偶數(shù).由此得出結(jié)論:七橋問題無解.

歐拉由七橋問題所引發(fā)的研究論文是圖論的開篇之作,因此稱歐拉為圖論之父.第3頁，共117頁，2023年，2月20日，星期六4.圖的作用

圖是一種表示工具.改變問題的描述方式,往往是創(chuàng)造性的啟發(fā)式解決問題的手段.一種描述方式就好比我們站在一個位置和角度觀察目標(biāo),有的東西被遮擋住了,但如果換一個位置和角度,原來隱藏著的東西就可能被發(fā)現(xiàn).采用一種新的描述方式,可能會產(chǎn)生新思想.圖論中的圖提供了一種直觀,清晰表達已知信息的方式.它有時就像小學(xué)數(shù)學(xué)應(yīng)用題中的線段圖一樣,能使我們用語言描述時未顯示的或不易觀察到的特征、關(guān)系,直觀地呈現(xiàn)在我們面前,幫助我們分析和思考問題,激發(fā)我們的靈感.第4頁，共117頁，2023年，2月20日，星期六5.圖的廣泛應(yīng)用圖的應(yīng)用是非常廣泛的,在工農(nóng)業(yè)生產(chǎn)、交通運輸、通訊和電力領(lǐng)域經(jīng)常都能看到許多網(wǎng)絡(luò),如河道網(wǎng)、灌溉網(wǎng)、管道網(wǎng)、公路網(wǎng)、鐵路網(wǎng)、電話線網(wǎng)、計算機通訊網(wǎng)、輸電線網(wǎng)等等.還有許多看不見的網(wǎng)絡(luò),如各種關(guān)系網(wǎng),像狀態(tài)轉(zhuǎn)移關(guān)系、事物的相互沖突關(guān)系、工序的時間先后次序關(guān)系等等,這些網(wǎng)絡(luò)都可以歸結(jié)為圖論的研究對象----圖.其中存在大量的網(wǎng)絡(luò)優(yōu)化問題需要我們解決.還有象生產(chǎn)計劃、投資計劃、設(shè)備更新等問題也可以轉(zhuǎn)化為網(wǎng)絡(luò)優(yōu)化的問題.第5頁，共117頁，2023年，2月20日，星期六6.基本的網(wǎng)絡(luò)優(yōu)化問題基本的網(wǎng)絡(luò)優(yōu)化問題有:最短路徑問題、最小生成樹問題、最大流問題和最小費用問題.圖論作為數(shù)學(xué)的一個分支,已經(jīng)有有效的算法來解決這些問題.當(dāng)然這當(dāng)中的有些問題也可以建立線性規(guī)劃的模型,但有時若變量特別多,約束也特別多,用線性規(guī)劃的方法求解效率不高甚至不能在可忍受的時間內(nèi)解決.而根據(jù)這些問題的特點,采用網(wǎng)絡(luò)分析的方法去求解可能會非常有效.第6頁，共117頁，2023年，2月20日，星期六例如,在1978年,美國財政部的稅務(wù)分析部門在對卡特爾稅制改革做評估的過程中,就有一個100,000個約束以上,25,000,000個變量的問題,若用普通的線性規(guī)劃求解,預(yù)計要花7個月的時間.他們利用網(wǎng)絡(luò)分析的方法,將其分解成6個子問題,利用特殊的網(wǎng)絡(luò)計算機程序,花了大約7個小時問題就得到了解決.

第7頁，共117頁，2023年，2月20日，星期六圖的基本概念(1)定義1圖G是一個三元組,記作其中(1)V(G)={v1,v2,…,vn}=Φ,稱為圖G的結(jié)點集.(2)E(G)={e1,e2,…,em}是G的邊集合,其中ei為{vj,vt}或<vj,vt>.若ei為{vj,vt},稱ei為vj和vt為端點的無向邊;若ei為<vj,vt>,稱ei為vj為起點,vt為終點的有向邊;(3)稱為關(guān)聯(lián)函數(shù).第8頁，共117頁，2023年，2月20日，星期六圖的基本概念(2)定義2.鄰接結(jié)點:關(guān)聯(lián)于同一條邊的兩個結(jié)點.孤立結(jié)點:不與任何結(jié)點相連接的結(jié)點.鄰接邊:關(guān)聯(lián)于同一頂點的兩條邊.環(huán):兩端點相同的邊稱為環(huán)或自回路.平行邊:兩個結(jié)點間方向相同的若干條邊稱為平行邊或重邊對稱邊:兩端點相同但方向相反的兩條有向邊.第9頁，共117頁，2023年，2月20日，星期六圖的基本概念(3)定義3

無向圖:每條邊都是無向邊的圖.有向圖:每條邊都是有向邊的圖.混合圖:圖中不全是有向邊,也不全是無向邊的圖.平凡圖:只有一個孤立結(jié)點的圖.定義4

多重圖:含有平行邊的圖.簡單圖:無環(huán)且無平行邊的圖.完全圖:任何不同結(jié)點之間都有邊相連的簡單無向圖.第10頁，共117頁，2023年，2月20日，星期六圖的基本概念(4)說明:(1)在簡單圖中,以x為起點y為終點的邊至多有一條,因此,圖中的邊可直接用頂點對表示,而關(guān)聯(lián)函數(shù)就可以直接表示在其邊集中,故可簡記為G=<V(G),E(G)>.(2)對無向圖G,將G中的每條邊用兩條與e有相同端點對稱邊e和e’來代替后得到一個有向圖D,這樣得到的有向圖D稱為G的對稱有向圖.由此可見,無向圖可視為特殊的有向圖.第11頁，共117頁，2023年，2月20日，星期六(3)n個結(jié)點的完全圖記為Kn,完全圖Kn有條邊.完全圖的對稱有向圖稱為完全有向圖,記作.(4)圖G的頂點個數(shù)稱為圖G的階.(5)對于有向圖D,去掉邊上的方向得到的無向圖G稱為D的基礎(chǔ)圖.反之,任一個無向圖G,將G的邊指定一個方向得到一個有向圖D,稱D為G的一個定向圖.第12頁，共117頁，2023年，2月20日，星期六例證明:在任意六個人的聚會上,要么三個曾相識,要么三個不曾相識.證明:用A,B,C,D,E,F代表這六個人,若兩人曾相識,則在代表該兩人的頂點間連一條紅邊;否則連一條藍邊.于是,原問題等價于證明所得圖中必含有同色三角形.考察某一頂點,設(shè)為F.與F關(guān)聯(lián)的邊中必有三條同色,不妨設(shè)它們是三條紅邊FA,FB,FC.再看三角形ABC.若它有一條紅邊,設(shè)為AB,則FAB是紅邊三角形;若三角形ABC沒有紅邊,則其本身就是藍邊三角形.第13頁，共117頁，2023年，2月20日，星期六圖的運算(一）定義1

設(shè)與是任何兩個圖.若且是在上的限制,則稱是G的子圖,記作,稱G為G1的母圖.

若且V1=V,則稱是G的生成子圖或支撐子圖.

設(shè),以V1為頂點,以兩端點均在V1中的全體邊為邊集的G的子圖,稱為V1的導(dǎo)出子圖,記作G[V1].設(shè),以E1為邊集,以E1中的邊關(guān)聯(lián)的全部頂點集的G的子圖,稱為E1的導(dǎo)出子圖,記作G[E1].

第14頁，共117頁，2023年，2月20日，星期六特別,若,則以G-V1表示從G中刪去V1內(nèi)的所有點以及與這些頂點關(guān)聯(lián)的邊所得到的子圖,

若V1={v},常把G-{v}簡記為G-v,,類似地,設(shè),G-E1表示在G中刪去E1中所有邊所得的子圖,同樣G-{e}簡記為G-e.第15頁，共117頁，2023年，2月20日，星期六圖的運算(二）定義2

設(shè)G＝<V，E>是n階無向簡單圖,以V為頂點集,以所有能使G成為完全圖Kn的添加邊組成的集合為邊集的圖,稱為G相對于完全圖Kn補圖,簡稱G的補圖,記作.定義3

設(shè)G1和G2都是圖G的子圖.G1和G2的并G1∪G2:僅由G1和G2中所有邊組成的圖.G1和G2的交

G1∩G2

:僅由G1和G2的公共邊組成的圖.G1和G2的差G1-G2:僅由G1中去掉G2中的邊組成的圖.G1和G2的環(huán)和G1⊕G2:在G1和G2的并中去掉G1和G2的交所得到的圖.第16頁，共117頁，2023年，2月20日，星期六路與連通圖(一)定義1

設(shè)u和v是任意圖G的頂點,圖G的一條u-v是有限的頂點和邊交替序列u0e1u1e2…un-1enun(u=u0,v=un),其中與邊ei(1in)相鄰的兩頂點ui-1和ui正好是ei的兩個端點.數(shù)n(鏈中出現(xiàn)的邊數(shù))稱為鏈的長度.u(u0)和v(un)稱為鏈的端點,其余的頂點稱為鏈的內(nèi)部點.一條u-v鏈,當(dāng)uv時,稱它為開的,否則稱為閉的.邊互不相同的鏈稱為跡,內(nèi)部點互不相同的鏈稱為路.第17頁，共117頁，2023年，2月20日，星期六注釋1.(1)在一條鏈中,頂點和邊可以重復(fù).(2)若G是簡單圖,G中的鏈u0e1u1e2…un-1enun還可用結(jié)點序列u0u1…un-1un表示.(3)不含邊的鏈(即長度為0)稱為平凡鏈.(4)設(shè)W是有向圖D中u-v鏈(跡,路),指定W的方向從u到v.若W中所有邊的方向與此方向一致,則稱W為D中從u到V的有向鏈(跡,路).第18頁，共117頁，2023年，2月20日，星期六路與連通圖(二)定義2.兩端點相同的跡(即閉集)稱為回.兩端點相同的路(即閉路)稱為圈或回路.長度為K,奇數(shù),偶數(shù)的回(圈)分別稱為K,奇,偶回(圈).有向閉跡(閉路)稱為有向回(有向圈).第19頁，共117頁，2023年，2月20日，星期六定理1.若簡單圖G中每個頂點的度數(shù)至少是k(k2),則G中必含有一個長度至少是k+1的圈.定理2.設(shè)簡單圖G中每個頂點的度數(shù)至少是3,則G中含有偶圈.定義3.給定無向圖G=<V(G),E(G),(G)>,x,y∈V(G),若圖中存在連接x和y的路,稱節(jié)點x和y是連通的.規(guī)定x到自身總是連通的.第20頁，共117頁，2023年，2月20日，星期六路與連通圖(四)1.說明:容易驗證,結(jié)點集V(G)上的頂點間的連通關(guān)系是V(G)上的一個等價關(guān)系,該等價關(guān)系確定V(G)的一個劃分{V1,V2,…,Vm},使得當(dāng)且僅當(dāng)兩個頂點x和y屬于同一子集Vi時,x和y才是連通的.Vi在G中的導(dǎo)出子圖G[V1],G[V2],…,G[Vm]稱為G的連通分支或分支,m稱為G的連通分支數(shù),記作W(G)=m.如下圖有4個連通分支.

定義4.如果無向圖G中每一對不同的頂點x和y都有一條路,即W(G)=1,則稱G是連通圖,反之稱為非連通圖.第21頁，共117頁，2023年，2月20日，星期六路與連通圖(五)引理1非平凡圖G是連通圖當(dāng)且僅當(dāng)對V(G)的每一個非空真子集S,定理3設(shè)G是P階連通圖,則懸掛點:度數(shù)為1頂點.定理4設(shè)連通圖G至少有兩個頂點,其邊數(shù)小于頂點數(shù),則此圖至少有一個懸掛點.第22頁，共117頁，2023年，2月20日，星期六路與連通圖(七)定義5設(shè)是有向圖,,若圖D中存在x到y(tǒng)的有向路,稱結(jié)點x可達結(jié)點y.

規(guī)定x到自身總是可達的.

第23頁，共117頁，2023年，2月20日，星期六定義6

設(shè)G是有向圖,任何結(jié)點間,至少有一個結(jié)點可達另一個結(jié)點,則稱該有向圖是單側(cè)連通的.如果有向圖D的任何一對結(jié)點間是相互可達的,則稱該有向圖是強連通的.若有向圖G的基礎(chǔ)圖是連通的,則稱該有向圖D是弱連通的.定義7

設(shè)G是有向圖,,G中所有從x到y(tǒng)的有向路的最小長度稱為從x到y(tǒng)的距離.稱為圖G的直徑.

第24頁，共117頁，2023年，2月20日，星期六連通圖和二分圖(1)定義1如果在圖G中刪去一個結(jié)點x后,圖G連通分支數(shù)增加,即W(G-x)>W(G),則稱結(jié)點x為G的割點.如果在圖G中刪去一條邊e后,圖G的連通分支數(shù)增加,即W(G-e)>W(G),則稱邊e為G的割邊.定義2沒有割點的非平凡連通圖稱為塊.G中不含割點的極大連通子圖稱為圖G的塊.第25頁，共117頁，2023年，2月20日，星期六定義3如果G的頂點集的一個真子集T滿足G-T不連通或是平凡圖,則稱T為G的一個點割.如果圖G的邊集的一個真子集S滿足G-S不連通或是平凡圖,則稱S為G的一個邊割.定義4設(shè)G是連通圖,稱是G的點割}為G的點連通度或連通度;稱是G的邊割}為G的邊連通度.定理1對一個圖G,有是圖G的最小頂點度.

第26頁，共117頁，2023年，2月20日，星期六連通圖和二分圖(3)定義5如果無向圖G的連通度稱圖G是n連通的或G為n連通圖.若稱圖G是n邊連通的或G為n邊連通圖.定理2設(shè)圖G是n連通的,則對定理3設(shè)G是2邊連通圖,則G有強連通的定向圖.第27頁，共117頁，2023年，2月20日，星期六連通圖和二分圖(4)定義6把簡單圖G的頂點集合分成兩個不相交的非空集合V1,V2,使得圖G中的每一條邊,與其關(guān)聯(lián)的兩個結(jié)點分別在V1和V2中,則G稱為偶圖或二分圖,記作G=<V1,V2,E>,其中V1和V2叫做G的二劃分.

對于二分圖G=<V1,V2,E>,若,V1中的任意一點與V2中的所有點相鄰且V2中的任意一點與V1中的所有點相鄰,則稱該圖為結(jié)點m和n的完全偶圖或完全二分圖,記作Km,n.定理4非平凡圖G是二分圖當(dāng)且僅當(dāng)G中不含有長為奇數(shù)的圈.第28頁，共117頁，2023年，2月20日，星期六圖的矩陣表示(1)1.鄰接矩陣:設(shè)是任意圖,其中V={x1,x2,…,xn},E={e1,e2,…,em},則n階方陣A=(aij)稱為G的鄰接矩陣.其中aij為圖G中以xi為起點且以xj為終點的邊的數(shù)目.說明1:由定義易知,無向圖的鄰接矩陣是對稱矩陣,而有向圖的鄰接矩陣未必是對稱矩陣.第29頁，共117頁，2023年，2月20日，星期六定理1已知有向圖,其中V={x1,x2,…,xn},且A=(aij)nn為G的鄰接矩陣,則Ak中的i和j列元素aij(k)是圖G中從xi到xj且長度為k的有向鏈的數(shù)目.說明2:該定理同樣適合無向圖,且定理中的鏈不能改為跡或路.推論1若G是P階簡單圖,且G的鄰接矩陣為A=(aij),則對G的每一個頂點vi,i=1,2,…,p,有d(vi)=aii(2),其中A2=(aii(2)).定理2已知P(P3)階圖G的鄰接矩陣為A,作P階方陣R=A+A2+…+Ap-1,則圖G連通的充分必要條件為R中的每個元素都不為零.第30頁，共117頁，2023年，2月20日，星期六2.關(guān)聯(lián)矩陣:設(shè)是有向圖,且V=,稱階矩陣M=(mij)為有向圖D的關(guān)聯(lián)矩陣,其中第31頁，共117頁，2023年，2月20日，星期六設(shè)是無向圖,且V=,稱階矩陣M=(mij)為無向圖D的關(guān)聯(lián)矩陣,其中說明3:從關(guān)聯(lián)矩陣可得無向圖的一些性質(zhì):(1)關(guān)聯(lián)矩陣的每一列只有兩個1(每條邊只關(guān)聯(lián)兩個頂點);(2)關(guān)聯(lián)矩陣的每一行元素之和為對應(yīng)頂點的度;(3)若某行中元素全為零,則相應(yīng)頂點為孤立點;(4)重邊所對應(yīng)的列完全相同.第32頁，共117頁，2023年，2月20日，星期六3.可達矩陣:設(shè)G=<V,E>是無重邊有向圖,其中V=,稱階矩陣P=(Pij)為G的可達矩陣.其中第33頁，共117頁，2023年，2月20日，星期六圖的矩陣表示(2)定理2

已知P(P3)階圖G的鄰接矩陣為A,作P階方陣R=A+A2+…+Ap-1,則圖G連通的充分必要條件為R中的每個元素都不為零.2.關(guān)聯(lián)矩陣:

設(shè)是有向圖,且V=,稱階矩陣M=(mij)為有向圖D的關(guān)聯(lián)矩陣,其中第34頁，共117頁，2023年，2月20日，星期六圖的矩陣表示(3)設(shè)是無向圖,且V=,稱階矩陣M=(mij)為無向圖D的關(guān)聯(lián)矩陣,其中說明3:從關(guān)聯(lián)矩陣可得無向圖的一些性質(zhì):(1)關(guān)聯(lián)矩陣的每一列只有兩個1(每條邊只關(guān)聯(lián)兩個頂點);(2)關(guān)聯(lián)矩陣的每一行元素之和為對應(yīng)頂點的度;(3)若某行中元素全為零,則相應(yīng)頂點為孤立點;(4)重邊所對應(yīng)的列完全相同.第35頁，共117頁，2023年，2月20日，星期六歐拉圖(1)定義1

給定無孤立結(jié)點的無向圖G,經(jīng)過圖G的每邊一次且僅一次的跡為一條歐拉路.經(jīng)過圖G的每邊一次且僅一次的回為一條歐拉回路.說明:(1)由定義,含有歐拉路(回)的圖顯然是連通的;(2)歐拉路是跡(邊互不重復(fù)),但不是嚴(yán)格意義上的路.定理1連通圖G具有歐拉回路當(dāng)且僅當(dāng)其每個頂點的度數(shù)為偶數(shù).第36頁，共117頁，2023年，2月20日，星期六歐拉圖與哈密頓圖(2)定理2連通圖G具有歐拉路而無歐拉回路,當(dāng)且僅當(dāng)G恰有兩個奇數(shù)度頂點.定義2給定有向圖D,經(jīng)過D中每邊一次且僅一次的有向跡稱為D的有向歐拉路.經(jīng)過D中每邊一次且僅一次的有向閉跡(回),稱為有向歐拉回路.第37頁，共117頁，2023年，2月20日，星期六歐拉圖與哈密頓圖(3)定理3具有弱連通性的有向圖G具有有向歐拉回路,當(dāng)且僅當(dāng)G的每個結(jié)點的入度等于出度.

具有弱連通性的有向圖G具有有向歐拉路,當(dāng)且僅當(dāng)在G中,一個結(jié)點的入度比出度大1,另一個結(jié)點的入度比出度小1,而其余每個結(jié)點的入度等于出度.定義3含有歐拉回路的無向連通圖與含有向歐拉回路的弱連通有向圖,統(tǒng)稱為歐拉圖.第38頁，共117頁，2023年，2月20日，星期六求Euler圖的Euler回路的Fleury算法.(1)任意選取一個頂點v0,置W0=v0;(2)假定跡(若是有向圖,則是有跡)Wi=v0e1v1…eivi已經(jīng)選出,則用下列方法從E(G)-{e1,e2,…,ei}中取ei+1;(a)ei+1與vi關(guān)聯(lián)(若是有向圖,ei+1以vi為起點)(b)除非沒有別的邊可選擇,ei+1不是Gi=G-{e1,e2,…,ei}的割邊.(3)當(dāng)(2)不能執(zhí)行時,停止.否則讓i+1→i,轉(zhuǎn)(2).(以p46為例)第39頁，共117頁，2023年，2月20日，星期六定理4若G是Euler圖,則Fleury算法終止時得到的跡是Euler回路。定義1給定無向圖G,若存在一條路經(jīng)過圖G的每個結(jié)點一次且僅一次,這條路稱為哈密頓路.若存在一條閉路經(jīng)過圖G的每個結(jié)點一次且僅一次,這條閉路稱為哈密頓回路.定義2給定有向圖D,若存在一條路經(jīng)過圖G的每個結(jié)點一次且僅一次,這條路稱為哈密頓有向路.若存在一條閉路經(jīng)過圖G的每個結(jié)點一次且僅一次,這條有向閉路稱為哈密頓有向回路.哈密頓圖(1)第40頁，共117頁，2023年，2月20日，星期六哈密頓圖(1)定義3具有哈密頓回路的無向圖與具有哈密頓有向回路的有向圖,統(tǒng)稱為哈密頓圖.例1對于完全圖Kn(n3),由于Kn中任意兩個頂點之間都有邊,從Kn的某一頂點開始,總可以遍歷其余節(jié)點后,再回到該結(jié)點,因而Kn(n3)是哈密頓圖.說明:判斷一個給定的圖是否為哈密頓圖,是圖論中尚未解決的難題之一,下面介紹若干必要條件和充分條件.第41頁，共117頁，2023年，2月20日，星期六哈密頓圖(3)定理1

設(shè)任意n(n3)階圖G,對所有不同非鄰接頂點x和y,若deg(x)+deg(y)n,則G是哈密頓圖.定理2

設(shè)u和v是n階圖G的不同非鄰接點,且deg(u)+deg(v)n,則G+邊{u,v}是哈密頓圖當(dāng)且僅當(dāng)哈密頓圖.定義4

給定n階圖G,若將圖G度數(shù)之和至少是n的非鄰接點用一條邊連接起來得圖G’,對圖G’重復(fù)上述過程,直到不再有這樣的結(jié)點對存在為止,所得到的圖,稱為是原圖G的閉包,記作C(G).第42頁，共117頁，2023年，2月20日，星期六定理3

一個圖是哈密頓圖當(dāng)且僅當(dāng)它的閉包是哈密頓圖.定理4設(shè)G是階至少為3的圖,如果G的閉包是完全圖,則G是哈密頓圖.定理5如果G是一個n階(n3)任意圖,且對G的每個頂點x,都有deg(x)n/2,則G是哈密頓圖.說明:由哈密頓圖的定義可知,哈密頓圖有向圖必是強連通的,哈密頓無向圖必?zé)o割點.第43頁，共117頁，2023年，2月20日，星期六8.哈密頓圖(4)定理5若G是一個哈密頓圖,則對于V(G)的每個非空真子集S,其中W(G-S)為G-S的分支數(shù).

第44頁，共117頁，2023年，2月20日，星期六9.哈密頓圖(5)說明:定理6只是一個必要條件,如下的皮特森圖,盡管有但它不是哈密頓圖.

第45頁，共117頁，2023年，2月20日，星期六10.哈密頓圖(6)應(yīng)用定理5若G是一個n(n3)階任意圖,且對G的每個頂點x,都有deg(x)n/2,則G是哈密頓圖.例1.11個學(xué)生要共進晚餐,他們將坐成一個圓桌,計劃要求每次晚餐上,每個學(xué)生有完全不同的鄰座.這樣能共進晚餐幾次.分析:如何將該問題轉(zhuǎn)化成圖論中的相關(guān)問題.實際上,可以這樣來構(gòu)造一個圖,即以每個學(xué)生看作圖的頂點,以學(xué)生的鄰座關(guān)系作為圖的邊,第46頁，共117頁，2023年，2月20日，星期六11.哈密頓圖(7)這樣學(xué)生每次進餐的就坐方式就對應(yīng)一個哈密頓回路.兩次進餐中,每個學(xué)生有完全不同的鄰座對應(yīng)著兩個沒有公共邊的哈密頓回路.因為每個學(xué)生都可以與其余學(xué)生鄰座,故問題轉(zhuǎn)化為在圖K11中找出所有沒有公共邊的哈密頓回路的個數(shù).K11中共有條邊,而K11中每條哈密頓回路的長度為11,因此K11中最多有55/11=5條沒有公共邊的哈密頓回路,構(gòu)造方法為:設(shè)第一條哈密頓回路為(1,2,3,…,11,1),將1固定在圓心,其余固定在圓周上,如圖(1)所示,然后將圖的頂點旋轉(zhuǎn)i×3600/10(i=1,2,3,4),從而就得到另外4個哈密頓回路.第47頁，共117頁，2023年，2月20日，星期六12.哈密頓圖(8)

1

(3,2,4,6)57(5,3,2,4)

(2,4,6,8)39(7,5,3,2)

(4,6,8,10)211(9,7,5,3)

(6,8,10,11)410(11,9,7,5)(8,10,11,9)68(10,11,9,7)圖1

1第48頁，共117頁，2023年，2月20日，星期六第五節(jié)最短路路問題1.加權(quán)圖:邊上有數(shù)的圖稱為加權(quán)圖;該數(shù)稱為邊的權(quán)。2.最短路問題:如何求兩個結(jié)點之間的最短路.3.迪克斯曲拉算法:這是荷蘭計算機科學(xué)教授EdsgerW.Dijkstra(1930-)在1959年發(fā)現(xiàn)的一個算法.他在1972年獲得計算機協(xié)會授予的圖靈獎,這是計算機科學(xué)中最具聲望的獎項.迪克斯曲拉算法是求出一個連通加權(quán)簡單圖中從結(jié)點a到結(jié)點z的最短路.邊{i,j}的權(quán)(i,j)>0,且結(jié)點x的標(biāo)號為L(x),結(jié)束時,L(z)是從x到z的最短路的長度.第49頁，共117頁，2023年，2月20日，星期六4.迪克斯曲拉算法流程ProcedureDijkstra(G:所有權(quán)為正的加權(quán)連通簡單圖){G帶有頂點a=v0,v1,…,vn=z和權(quán)w(vi,vj),若{vi,vj}不是G中的邊,則w(vi,vj)=)Fori:=1tonL(vi):=L(a):=0S:={初始化標(biāo)記,a的標(biāo)記為0,其余結(jié)點標(biāo)記為,S是空集}WhilezSbeginu:=不屬于S的L(u)最小的一個頂點S:=S{u}For所有不屬于S的頂點vIfL(u)+w(u,v)<L(v)thenL(v):=L(u)+w(u,v){這樣就給S中添加帶最小標(biāo)記的頂點并且更新不在S中的頂點的標(biāo)記}End{L(z)=從a到z的最短路的長度}.第50頁，共117頁，2023年，2月20日，星期六例1.用迪克斯曲拉算法求下圖所示的加權(quán)圖中頂點a與z之間最短路的長度.（見65頁）a4b5d2110c8e263z第51頁，共117頁，2023年，2月20日，星期六定理1迪克斯曲拉算法求出連通簡單無向圖的中兩點之間的最短路的長度。定理2迪克斯曲拉算法使用O(n2)次運算（加法和比較）來求出n階連通簡單無向加權(quán)圖中兩個頂點之間的最短路的長度。迪克斯曲拉算法可以推廣到求加權(quán)有向圖的最短路。定理3

設(shè)有向圖G中不含長度非正的有向圈，并且從點1到其余各點都有有限長的有向路，那么式（2）有唯一有限解。.第52頁，共117頁，2023年，2月20日，星期六Floyd算法

Dijkstra算法只求出一個特定頂點到其他各頂點的最短路.但在許多實際問題中,需求出任意兩點之間的最短路,如全國各城市之間最短的航線,選址問題等.Floyd算法可以比較好地解決這一問題.

為介紹Floyd算法,先定義矩陣的兩種運算.定義1已知矩陣A=(aij)ml,B=(bij)ln,規(guī)定C=AB=(cij)mn,其中cij=min(ai1+b1j,ai2+b2j,…,ail+blj).第53頁，共117頁，2023年，2月20日，星期六定義2已知矩陣A=(aij)mn,B=(bij)mn,規(guī)定D=A?B=(dij)mn,其中dij=min(aij,bij).

可以利用上面定義的運算求任意兩點間的最短距離.

已知n階加權(quán)簡單圖G,設(shè)D=(dij)nn是圖G的邊權(quán)矩陣即dij=w(i,j)(若G是有向圖,則dij=w<i,j>),

若結(jié)點i到結(jié)點j無邊相連時,則取dij=.

然后依次計算出矩陣D[2],D[3],…,D[n]及S,其中第54頁，共117頁，2023年，2月20日，星期六D[2]=DD=(dij[2])nnD[3]=D[2]D=(dij[3])nn,……,D[n]=D[n-1]D=(dij[n])nnS=D?D[2]?D[3]?…D[n]=(Sij)nn

由定義可知,dij[k]表示從結(jié)點i到結(jié)點j經(jīng)k邊的路(在有向圖中即為有向路)中的長度最短者.這就是Floyd算法.Floyd算法的時間復(fù)雜度為O(n4).第55頁，共117頁，2023年，2月20日，星期六v121v27v6v41332v6例2.利用Floyd算法求下圖中任意兩點間最短有向路的長度.(p71-73)第56頁，共117頁，2023年，2月20日，星期六Warshall算法D=(dij)為圖G的邊權(quán)矩陣(1)輸入D(2)k：=1；(3)i：=1；(4)dij:=min(dij,dik+dkj),j=1,2,…,n(5)i：=i+1,若i≤n,轉(zhuǎn)(4);(6)k：=k+1,若k≤n,轉(zhuǎn)(3);否則停止。實質(zhì)上是考慮經(jīng)過n次結(jié)點轉(zhuǎn)換每一次保留最短路的長度。舉例見P74.第57頁，共117頁，2023年，2月20日，星期六旅行推銷員問題和中國投遞員問題（NPC問題）

一、旅行推銷員問題

第58頁，共117頁，2023年，2月20日，星期六（最鄰近算法給出旅行推銷員問題的近似解）步驟如下（1）由任意選擇的結(jié)點開始，找出于該結(jié)點鄰近的點，形成一條有邊的初始路。（2）以表示最新加到這條路上的結(jié)點，從不在路上的所有結(jié)點中選一個和最靠近的結(jié)點，把連接與這一結(jié)點的邊加到這條路上，重復(fù)這一步驟直到這條路包含圖中所有結(jié)點。第59頁，共117頁，2023年，2月20日，星期六例1用“最鄰近算法”給出下面加權(quán)圖中有充分小權(quán)的哈密頓路P76.AFBECD16697151312183513182119第60頁，共117頁，2023年，2月20日，星期六說明:“最鄰近插入方法”是“最鄰近法”的一種改進方法.該方法是在每次迭代中都構(gòu)成一個閉的旅行路線.求解時,在已經(jīng)建立旅程以外的頂點中,尋找最臨近于旅程中某個頂點的頂點,然后將其插入該旅程中,并使增加的距離盡可能小,當(dāng)全部頂點收入這個旅程后,就找到了所求的最短哈密頓回路的近似解.例2用“最鄰近插入方法”找出上圖中具有充分小權(quán)的哈密頓回路.第61頁，共117頁，2023年，2月20日，星期六定理1設(shè)P是加權(quán)連通圖G中一條包含G的所有邊至少一次的閉鏈，則P最優(yōu)的充要條件（具有最小長度）是：（1）P中無二重以上的邊；（2）在G的每個圈中C中，重復(fù)邊集E的長度之和不超過這個圈的長度的一半，即W(E)1/2W(C).二.中國郵路問題第62頁，共117頁，2023年，2月20日，星期六奇偶點作業(yè)法（1）把G中所有奇度頂點配成對，將每對奇度頂點之間的一條路上的每邊改為二重邊，得到一個新圖G1，新圖G1中無奇度頂點，即G1為多重歐拉圖.（2）若G1中某對結(jié)點間有多于兩條邊連接，則去掉其中偶數(shù)條邊，留下一條或兩條邊連接這兩個結(jié)點，直到每對相鄰結(jié)點至多由2條邊連接。得到圖G2.第63頁，共117頁，2023年，2月20日，星期六（3）檢查G2的每個圈C，若某個圈C上重復(fù)邊集E的權(quán)和超過這個圈的權(quán)和的一半，則將C按定理1必要性證明中的方法進行調(diào)整，直到對G2所有的圈其重復(fù)邊的權(quán)和不超過此圈權(quán)和的一半，得到圖G3.（4）用Fleury算法求G的Euler回路.第64頁，共117頁，2023年，2月20日，星期六例3求下圖G的最優(yōu)環(huán)游p81.v1v2v3v4v5v6v7v8v9v10v11v122455364

6465447938A第65頁，共117頁，2023年，2月20日，星期六V12v104v95v8V26v114v126v7554477V39

v43

v58

v6B第66頁，共117頁，2023年，2月20日，星期六4455447799

8864636C第67頁，共117頁，2023年，2月20日，星期六446466654444793836D第68頁，共117頁，2023年，2月20日，星期六44

4

33

45536466664第69頁，共117頁，2023年，2月20日，星期六2第70頁，共117頁，2023年，2月20日，星期六樹的基本概念定義1樹是無圈連通無向圖.樹中度數(shù)為1的結(jié)點稱為樹的葉.樹中度數(shù)大于1的結(jié)點稱為樹的分枝點或內(nèi)點.不相交的若干樹稱為森林,即森林的每個連通分枝是樹.第71頁，共117頁，2023年，2月20日，星期六定義2設(shè)T是有向圖,若T的基礎(chǔ)圖是樹,稱T是有向樹.定義3僅一個結(jié)點的入度為0,其余所有結(jié)點的入度都為1的有向樹稱為根樹.入度為0的結(jié)點稱為根.出度為0的結(jié)點(度數(shù)為1的結(jié)點)仍稱為葉;出度不為0的結(jié)點稱為分枝點或內(nèi)點.由根到某一頂點v的有向路的長度,稱為v的層數(shù).根樹的高度就是頂點層數(shù)的最大值.第72頁，共117頁，2023年，2月20日，星期六支撐樹定義1若T是G的一個生成子圖且又是一棵樹,則稱T是圖G的一棵生成樹或支撐樹.生成樹T中的邊稱為T的樹枝,不在生成樹T中的G的邊,稱為樹T的弦.定理1圖G有生成樹G為連通圖.第73頁，共117頁，2023年，2月20日，星期六求連通簡單圖的生成樹

深度優(yōu)先搜索和廣度優(yōu)先搜索深度優(yōu)先搜索:任意選擇圖G的一個頂點為根,通過不斷地增加邊來形成以頂點v0為起點的路,直到這條路經(jīng)過圖G的每個頂點,此時得到的這條路就是該圖的生成樹.其中每條新邊都與路上的一個頂點以及不在路上的一個頂點關(guān)聯(lián).如果這條路不經(jīng)過圖G的所有頂點,則返回倒數(shù)第二個頂點,繼續(xù)重復(fù)上面過程,直到不能添加更多的邊為止.又圖G是有有限邊數(shù)的連通圖,故最后總能產(chǎn)生一棵生成樹.第74頁，共117頁，2023年，2月20日，星期六例1用深度搜索來找出下圖G的生成樹abcdefghijk第75頁，共117頁，2023年，2月20日，星期六廣度優(yōu)先搜索基本思想:從圖的頂點中任意地選擇一個根,然后添加與該頂點相關(guān)聯(lián)的所有邊,在這個階段添加的新頂點成為生成樹里1層上的頂點,任意地排序它們.下一步,按順序訪問1層上的每一個頂點,只要不產(chǎn)生回路,就添加與這個頂點相關(guān)聯(lián)的每條邊,這樣就產(chǎn)生了樹里2層上的頂點.遵循這樣的原則繼續(xù)下去,經(jīng)有限步驟后(因為圖中只有有限條邊)就產(chǎn)生了生成樹.例2.用廣度優(yōu)先搜索找出例1中圖G的生成樹.P106第76頁，共117頁，2023年，2月20日，星期六最小支撐樹定義1:連通加權(quán)圖里權(quán)和最小的支撐樹稱為最小支撐樹.

最小支撐樹的實際應(yīng)用背景:在某一國家或地區(qū),需建造一鐵路網(wǎng)/公路網(wǎng)把一些城市連接起來,需要總長度最短或造價最低.

尋找最小支撐樹的貪心算法原理:通過添加還沒使用過的具有規(guī)定性質(zhì)且權(quán)最小的邊來進行的,其實質(zhì)就是在每步上進行最優(yōu)選擇,即“局部最優(yōu)化”.

第77頁，共117頁，2023年，2月20日，星期六普林算法算法的基本思想:首先選擇帶最小權(quán)的邊,把它放進支撐樹里.相繼向樹里添加帶最小權(quán)的邊,這些邊與已在樹里的頂點相關(guān)聯(lián),并且不與已在樹里的邊形成圈,直到添加了n-1條邊止.算法描述如下:算法1普林算法Procedureprim(G:帶n個頂點的連通無向圖)T:=權(quán)最小的邊Fori:=1ton-2begine:=與T里頂點相關(guān)聯(lián)的權(quán)最小的邊,并且若添加到T里則不形成圈T:=添加e之后的Tend{T是G的最小支撐樹}第78頁，共117頁，2023年，2月20日，星期六例1用普林算法求下圖所示的最小支撐樹定理1普林算法是正確的,即在算法結(jié)束時,得到一棵最小支撐樹.(證略)1745102616158abcgfde第79頁，共117頁，2023年，2月20日，星期六克魯斯卡爾(Kruskal)算法算法的基本思想:選擇圖中最小的一條邊,相繼添加不與已經(jīng)選擇的邊形成圈的權(quán)最小的邊,直到挑選n-1(n為結(jié)點的個數(shù))條邊為止.第80頁，共117頁，2023年，2月20日，星期六該算法的偽代碼如下:ProcedureKruskal(G:n個頂點的連通加權(quán)無向圖)T:=空圖.Fori:=1ton-1beginE:=當(dāng)添加到T里時不形成圈的G里權(quán)最小的邊T:=添加e之后的TEnd{T是G的最小支撐樹}定理2由Kruskal算法構(gòu)作的任何生成樹T=G[e1,e2,…,en-1]都是G的最小生成樹,n為G的結(jié)點數(shù).第81頁，共117頁，2023年，2月20日，星期六基于破圈法的最小生成樹的生成方法該方法是由管梅谷教授給出的,其基本思想為:設(shè)G是連通加權(quán)簡單圖,若G不是樹,則G中必含有回路,刪去G中含于某回路內(nèi)權(quán)最大的一條邊,所得的圖記為G1,G1是G的連通生成子圖.下一步,若G1不是樹,又從G1某個回路內(nèi)刪去權(quán)最大的一條邊,如此下去,最后不能按上述方式刪邊時,得到的圖T便是G的一棵生成樹.定理3由破圈法最后得到的圖T為G的一棵最小生成樹.第82頁，共117頁，2023年，2月20日，星期六平面圖的著色定義1設(shè)G是無孤立結(jié)點的連通的平面圖，且G有K個面F1，F(xiàn)2，…Fk(包括外部面).則按下列過程作G的對偶圖G.（1）在G的每個面內(nèi)設(shè)置一個結(jié)點vi(1ik)。（2）過Fi與Fj的每一條公共邊ek作一條僅作一條邊{vi,vj}與ek相交。（3）當(dāng)且僅當(dāng)ek只是Fi的邊界時，vi恰有一自回路與ek相交。這樣所得的圖G*稱為圖G的對偶圖.若G*與G同構(gòu),稱G是自對偶的.如下圖G的對偶圖為圖中虛線.第83頁，共117頁，2023年，2月20日，星期六12341324第84頁，共117頁，2023年，2月20日，星期六定義2圖的著色是對該圖的每個頂點都指定一種顏色，使沒有兩個相鄰的頂點指定為相同的顏色。如果這些頂點選自于一個有k種顏色的集合，而不管k種顏色是否都用到，這樣的著色稱為k著色。定義3圖G的色數(shù)是著色這個圖G所需要的最少顏色數(shù)。記作(G)。圖G的色素也稱為圖G的點色素.從定義可知,對于G的任何子圖H,均有x(H)x(G).若G是n階完全圖,若G是n階完全圖,則x(G)=n;若G是至少有一邊的二分圖,則x(G)=2;若G是長為奇數(shù)的圈,則x(G)=3.當(dāng)x(G)3時,G的特征至今尚未清楚,在下一節(jié),將給出G的色素x(G)的一個上界.第85頁，共117頁，2023年，2月20日，星期六定理1設(shè)u和v是圖G中兩個不相鄰的頂點,則(G)=min{(G+{u,v}),(G?{u,v})},其中G?{u,v}是把G中結(jié)點u與v重合成一個新結(jié)點，且G中分別與u與v關(guān)聯(lián)的邊都與該新結(jié)點關(guān)聯(lián)。四色問題:連通簡單平面圖的色素不超過4.

四色問題是蓋思里于1852年提出,后經(jīng)眾多數(shù)學(xué)家嘗試證明,均以失敗告終.1976年,美國數(shù)學(xué)家阿佩爾和黑肯宣布借助用計算機證明,但時間超過了1000小時,其可靠性仍在置疑之中.第86頁，共117頁，2023年，2月20日，星期六例1求下圖G和H的色數(shù)acfgbedGHa:紅,b:藍,c:綠,d:紅,e:綠，f:藍,g:紅(3色)定理2（五色定理）連通簡單平面圖G的色數(shù)為不超過5.第87頁，共117頁，2023年，2月20日，星期六例2.由n(n3)個頂點v1,v2,…,vn以及邊{v1,v2},{v2,v3},…,{vn-1,vn}{vn,v1}組成的圖稱為圈圖,記作Cn,試問圈圖的Cn的色數(shù)是多少。（分n為奇數(shù)，或偶數(shù)）例3.Kn和Km,n的色數(shù)分別是多少？解:由于Kn的每兩個頂點都相鄰,而當(dāng)兩個相鄰的頂點必指定不同的顏色,故Kn的色素為n.Km,n的色數(shù)為2.用一種顏色著色m個頂點,用另一種顏色著色n個頂點.第88頁，共117頁，2023年，2月20日，星期六第五節(jié)圖著色的應(yīng)用貯藏問題:某工廠生產(chǎn)n種化學(xué)制品c1,c2,…,cn,其中某些制品是互不相容.若它們相互接觸,則會發(fā)生化學(xué)反應(yīng)甚至引起爆炸,為安全起見,該工廠必須把倉庫分成若干隔間,以便把不相容的化學(xué)制品儲藏在不同的隔間,試問該倉庫至少應(yīng)分成幾個隔間?解:構(gòu)建簡單圖G=<V,E>,其中V(G)={c1,c2,…,cn}

邊{ci,cj}E(G)化學(xué)制品ci與cj互不相容.

易知,倉庫的最少隔間數(shù)等于圖G的色素x(G).第89頁，共117頁，2023年，2月20日，星期六電視頻道分配問題某地區(qū)內(nèi)有n家電視發(fā)射臺T1,T2,…,Tn.主管部門為每家電視發(fā)射臺分配一個頻道.為排除干擾,使用同一頻道的電視臺之間的距離必須大于指定的正數(shù)d,試問該地區(qū)至少需要多少頻道?

構(gòu)建簡單圖G=<V,E>,其中V(G)={T1,T2,…,Tn}

邊{Ti,Tj}E(G)Ti與Tj之間距離d.

易知,需要的最少頻道等于圖G的色素x(G).第90頁，共117頁，2023年，2月20日，星期六考試安排問題某高校有n門選修課程v1,v2,…,vn需要進行期末考試.同一學(xué)生不能在同一天里參加兩門課程的考試.問學(xué)校的期末考試需要幾天?

構(gòu)建簡單圖G=<V,E>,其中V(G)={v1,v2,…,vn}

邊{vi,vj}E(G)vi與vj被同一同學(xué)選修.

故考試需要的最小天數(shù)等于圖G的色素x(G).第91頁，共117頁，2023年，2月20日，星期六順序著色算法

到目前為止,還沒有一個有效算法來確定色素.順序著色算法是一個求x(G)的有效算法:設(shè)G=<V,E>是簡單無向圖，V={x1,x2…xn}用N(xi)表示與xi相鄰的全部頂點集合；對頂點xi著色C，記為(xi)=C.i:=1c:=1若對yN(xi),(y)C,則令(xi)=C并轉(zhuǎn)入第5步。C:=C+1并轉(zhuǎn)入第3步。若i<n，則i:=i+1并轉(zhuǎn)回第2步，否則停止.第92頁，共117頁，2023年，2月20日，星期六例1試用順序著色法求圖G的色數(shù)。1211212121321211321212132121定理1設(shè)G是簡單連通圖，順序著色法產(chǎn)生G的頂點的一個(G）+1著色，所以(G)（G）+1第93頁，共117頁，2023年，2月20日，星期六定理1給出了連通簡單圖G的色數(shù)的上界.1941年R.L.Brooks證明了下面的定理.定理2設(shè)G是一個連通簡單圖,其頂點的最大度為.若G既不是完全圖Kn,也不是奇數(shù)圈圖Cn,則x(G).第94頁，共117頁，2023年，2月20日，星期六邊著色定義1圖G的邊著色對G的每一條邊都指定一個顏色，使得沒有兩個相鄰的邊都為同一種顏色。如果這些顏色都取自一個有K種顏色的集合，而不管這K種顏色是否都用掉，這樣的邊著色稱為K—邊著色。定義2圖G的邊著色數(shù)是著色這個圖G需要的最少顏色數(shù)。記為’(G).第95頁，共117頁，2023年，2月20日，星期六邊著色轉(zhuǎn)化為點著色的方法：

邊著色可以轉(zhuǎn)化為相應(yīng)的點著色,即在邊著色圖中,將所有的邊對應(yīng)地轉(zhuǎn)化成點著色圖中的結(jié)點,結(jié)點轉(zhuǎn)化成相應(yīng)的邊.因此,由點著色性質(zhì)定理不難得到如下定理.定理1若G是非空連通的簡單圖，G的最大頂點度為,則’(G)+1。（不證）第96頁，共117頁，2023年，2月20日，星期六定義3.圖G的不同K—著色的數(shù)目，稱為圖G的色多項式。記作f(G,k).說明:(1)若k<x(G),此時k-著色不存在,顯然有f(G,k)=0,從而即知,滿足f(G,k)>0的最小的k即為G的色數(shù).(2)設(shè)mi是i種顏色對圖G的頂點進行著色的不同方案數(shù).用k(ki)種顏色對圖G進行著色,每取i種顏色時,共有miCki種不同的著色方案,故有:f(G,k)=m1Ck1+m2Ck2+…+mnCkn,其中n為圖G的頂點數(shù).顯然,f(G,k)是k的多項式.第97頁，共117頁，2023年，2月20日，星期六圖的兩種基本運算:(1)Guv設(shè)u,v是圖G的不鄰接的兩個頂點,把u,v收縮成一個頂點x,并把G中凡與u,v關(guān)聯(lián)的邊均使之與x關(guān)聯(lián),這樣所得的新圖。記作Guv.(2)G:e把圖G的一條邊刪去并使它的兩個端點重合,也即邊e被收縮.這樣得到的新圖。記作G:e.第98頁，共117頁，2023年，2月20日，星期六定理3.設(shè)u,v是G的兩個不相鄰的頂點，則f(G,k)=f(G+{u,v},k)+f(G:uv,k)說明:定理3表明,若G是有P個頂點和q條邊的圖,則有一個q+1條邊的圖G1=G+{u,v}(u與v不相鄰接)和一個有P-1個頂點的圖G2=Guv,使f(G,k)=f(G1,k)+f(G2,k).對G1和G2依次類推,直到只出現(xiàn)完全圖為止.因此,一個圖的色多項式f(G,k)是f(Kn,k)型的表達式的和.第99頁，共117頁，2023年，2月20日，星期六完全圖的色多項式例1.對三階完全圖K3而言,有f(K3,k)=k(k-1)(k-2).解:由于對K3中的任何指定一個頂點,可以用k種顏色中的任何一種進行著色;對K3的第二個頂點,可以用k-1種顏色中的任何一種進行著色;對K3的第三個頂點,可以用k-2種顏色中的任何一種進行著色.一般地,對于P階完全圖，有f(Kp,k)=k(k-1)(k-2)…(k-p+1)第100頁，共117頁，2023年，2月20日，星期六例1三階完全圖K3

有f(K3,k)=k(k-1)(k-2)例2求圖G的色多項式。f(G,k)=K5+3K4+K3=k(k-1)(k-2)(k-3)(k-4)+3k(k-1)(k-2)(k-2)(k-3)+k(k-1)(k-2)=k5-7k4+18k3-20k2+8k第101頁，共117頁，2023年，2月20日，星期六匹配匹配問題是運籌學(xué)的重要問題之一,也是圖論研究的重點內(nèi)容,它提供了解決“人員分配問題”和“最優(yōu)分配問題”一種新的思想.定義1.設(shè)G=<V,E>是無環(huán)圖,ME(G),M,若M中任意兩條邊都不相鄰,則稱M是圖G的一個匹配.若對圖G的任何匹配M’,均有M’<M,則稱M是圖G的最大匹配,記作’(G).定義2.設(shè)M是圖G的匹配,G中與M中的邊關(guān)聯(lián)的頂點稱為M飽和點.若圖G的頂點都是M飽和,則稱為G的完美匹配.第102頁，共117頁，2023年，2月20日，星期六說明:(1)完美匹配是最大匹配,反之未然;(2)匹配的定義與邊的方向無關(guān),故匹配是針對無向圖而言.(3)圖G的邊不交匹配的最小數(shù)目即為G的邊色數(shù).定義3.(可增廣路):設(shè)M是圖G的匹配,P是G的一條路,且在P中,M的邊和E(G)-M的邊交替出現(xiàn),則稱P是G的一條交錯路.若M交錯路P的兩個端點為M非飽和點,則稱P為M可增廣路.例1.求下圖G的一條交錯路和一條可增廣路.62341587第103頁，共117頁，2023年，2月20日，星期六匹配的幾個性質(zhì)定理定理1.設(shè)M1和M2是圖G的兩個不同匹配,由M1M2導(dǎo)出的G的邊導(dǎo)出子圖記作H,則H的任意連通分支是下列情況之一:(1)邊在M1和M2中交錯出現(xiàn)的偶圈.(2)邊在M1和M2中交錯出現(xiàn)的路.第104頁，共117頁，2023年，2月20日，星期六定理2.M是圖G的最大匹配,當(dāng)且僅當(dāng)G中不存在M可增廣路.

定義:NG(S):設(shè)S是圖G的任意頂點子集,G中與S的頂點鄰接的所有頂點的集合,稱為S的鄰集,記做NG(S).第105頁，共117頁，2023年，2月20日，星期六定理3(Hall定理,1935)設(shè)G是有二部劃分(V1,V2)的二分圖,則G含有飽和V1的每個頂點的匹配M的充要條件是,對SV1,有N(S)S.推論1具有二部劃分(V1,V2)的二分圖G有完美匹配V1=V2,且對SV1(或V2),有N(S)S.推論2.

設(shè)G是k(>0)正則二分圖,則G有完美匹配.推論3.設(shè)G是二部劃分(V1,V2)的簡單二分圖,且V1=V2=n,若(G)n/2,則G有完美匹配.第106頁，共117頁，2023年，2月20日，星期六定理4.G有完美匹配O(G-S)S,SV(