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

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

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

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

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

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

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

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

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

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

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

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

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

設(shè)G＝<V，E>是n階無(wú)向簡(jiǎn)單圖,以V為頂點(diǎn)集,以所有能使G成為完全圖Kn的添加邊組成的集合為邊集的圖,稱為G相對(duì)于完全圖Kn補(bǔ)圖,簡(jiǎn)稱G的補(bǔ)圖,記作.定義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頁(yè)，共117頁(yè)，2023年，2月20日，星期六路與連通圖(一)定義1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第45頁(yè)，共117頁(yè)，2023年，2月20日，星期六10.哈密頓圖(6)應(yīng)用定理5若G是一個(gè)n(n3)階任意圖,且對(duì)G的每個(gè)頂點(diǎn)x,都有deg(x)n/2,則G是哈密頓圖.例1.11個(gè)學(xué)生要共進(jìn)晚餐,他們將坐成一個(gè)圓桌,計(jì)劃要求每次晚餐上,每個(gè)學(xué)生有完全不同的鄰座.這樣能共進(jìn)晚餐幾次.分析:如何將該問(wèn)題轉(zhuǎn)化成圖論中的相關(guān)問(wèn)題.實(shí)際上,可以這樣來(lái)構(gòu)造一個(gè)圖,即以每個(gè)學(xué)生看作圖的頂點(diǎn),以學(xué)生的鄰座關(guān)系作為圖的邊,第46頁(yè)，共117頁(yè)，2023年，2月20日，星期六11.哈密頓圖(7)這樣學(xué)生每次進(jìn)餐的就坐方式就對(duì)應(yīng)一個(gè)哈密頓回路.兩次進(jìn)餐中,每個(gè)學(xué)生有完全不同的鄰座對(duì)應(yīng)著兩個(gè)沒(méi)有公共邊的哈密頓回路.因?yàn)槊總€(gè)學(xué)生都可以與其余學(xué)生鄰座,故問(wèn)題轉(zhuǎn)化為在圖K11中找出所有沒(méi)有公共邊的哈密頓回路的個(gè)數(shù).K11中共有條邊,而K11中每條哈密頓回路的長(zhǎng)度為11,因此K11中最多有55/11=5條沒(méi)有公共邊的哈密頓回路,構(gòu)造方法為:設(shè)第一條哈密頓回路為(1,2,3,…,11,1),將1固定在圓心,其余固定在圓周上,如圖(1)所示,然后將圖的頂點(diǎn)旋轉(zhuǎn)i×3600/10(i=1,2,3,4),從而就得到另外4個(gè)哈密頓回路.第47頁(yè)，共117頁(yè)，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頁(yè)，共117頁(yè)，2023年，2月20日，星期六第五節(jié)最短路路問(wèn)題1.加權(quán)圖:邊上有數(shù)的圖稱為加權(quán)圖;該數(shù)稱為邊的權(quán)。2.最短路問(wèn)題:如何求兩個(gè)結(jié)點(diǎn)之間的最短路.3.迪克斯曲拉算法:這是荷蘭計(jì)算機(jī)科學(xué)教授EdsgerW.Dijkstra(1930-)在1959年發(fā)現(xiàn)的一個(gè)算法.他在1972年獲得計(jì)算機(jī)協(xié)會(huì)授予的圖靈獎(jiǎng),這是計(jì)算機(jī)科學(xué)中最具聲望的獎(jiǎng)項(xiàng).迪克斯曲拉算法是求出一個(gè)連通加權(quán)簡(jiǎn)單圖中從結(jié)點(diǎn)a到結(jié)點(diǎn)z的最短路.邊{i,j}的權(quán)(i,j)>0,且結(jié)點(diǎn)x的標(biāo)號(hào)為L(zhǎng)(x),結(jié)束時(shí),L(z)是從x到z的最短路的長(zhǎng)度.第49頁(yè)，共117頁(yè)，2023年，2月20日，星期六4.迪克斯曲拉算法流程ProcedureDijkstra(G:所有權(quán)為正的加權(quán)連通簡(jiǎn)單圖){G帶有頂點(diǎn)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é)點(diǎn)標(biāo)記為,S是空集}WhilezSbeginu:=不屬于S的L(u)最小的一個(gè)頂點(diǎn)S:=S{u}For所有不屬于S的頂點(diǎn)vIfL(u)+w(u,v)<L(v)thenL(v):=L(u)+w(u,v){這樣就給S中添加帶最小標(biāo)記的頂點(diǎn)并且更新不在S中的頂點(diǎn)的標(biāo)記}End{L(z)=從a到z的最短路的長(zhǎng)度}.第50頁(yè)，共117頁(yè)，2023年，2月20日，星期六例1.用迪克斯曲拉算法求下圖所示的加權(quán)圖中頂點(diǎn)a與z之間最短路的長(zhǎng)度.（見(jiàn)65頁(yè)）a4b5d2110c8e263z第51頁(yè)，共117頁(yè)，2023年，2月20日，星期六定理1迪克斯曲拉算法求出連通簡(jiǎn)單無(wú)向圖的中兩點(diǎn)之間的最短路的長(zhǎng)度。定理2迪克斯曲拉算法使用O(n2)次運(yùn)算（加法和比較）來(lái)求出n階連通簡(jiǎn)單無(wú)向加權(quán)圖中兩個(gè)頂點(diǎn)之間的最短路的長(zhǎng)度。迪克斯曲拉算法可以推廣到求加權(quán)有向圖的最短路。定理3

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

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

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

可以利用上面定義的運(yùn)算求任意兩點(diǎn)間的最短距離.

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

若結(jié)點(diǎn)i到結(jié)點(diǎn)j無(wú)邊相連時(shí),則取dij=.

然后依次計(jì)算出矩陣D[2],D[3],…,D[n]及S,其中第54頁(yè)，共117頁(yè)，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é)點(diǎn)i到結(jié)點(diǎn)j經(jīng)k邊的路(在有向圖中即為有向路)中的長(zhǎng)度最短者.這就是Floyd算法.Floyd算法的時(shí)間復(fù)雜度為O(n4).第55頁(yè)，共117頁(yè)，2023年，2月20日，星期六v121v27v6v41332v6例2.利用Floyd算法求下圖中任意兩點(diǎn)間最短有向路的長(zhǎng)度.(p71-73)第56頁(yè)，共117頁(yè)，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);否則停止。實(shí)質(zhì)上是考慮經(jīng)過(guò)n次結(jié)點(diǎn)轉(zhuǎn)換每一次保留最短路的長(zhǎng)度。舉例見(jiàn)P74.第57頁(yè)，共117頁(yè)，2023年，2月20日，星期六旅行推銷員問(wèn)題和中國(guó)投遞員問(wèn)題（NPC問(wèn)題）

一、旅行推銷員問(wèn)題

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

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

v43

v58

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

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

4

33

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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