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

1.圖論問題的起源

18世紀(jì)東普魯士哥尼斯堡被普列戈爾河分為四塊,它們通過七座橋相互連接,如下圖.當(dāng)時該城的市民熱衷于這樣一個游戲:“一個散步者怎樣才能從某塊陸地出發(fā)，經(jīng)每座橋一次且僅一次回到出發(fā)點(diǎn)？”SNAB七橋問題的分析

七橋問題看起來不難，很多人都想試一試，但沒有人找到答案.后來有人寫信告訴了當(dāng)時的著名數(shù)學(xué)家歐拉.千百人的失敗使歐拉猜想,也許那樣的走法根本不可能.1876年,他證明了自己的猜想.Euler把南北兩岸和兩個島抽象成四個點(diǎn),將連接這些陸地的橋用連接相應(yīng)兩點(diǎn)的一條線來表示,就得到如下一個簡圖:SNAB歐拉的結(jié)論歐拉指出:一個線圖中存在通過每邊一次僅一次回到出發(fā)點(diǎn)的路線的充要條件是:1)圖是連通的,即任意兩點(diǎn)可由圖中的一些邊連接起來;2)與圖中每一頂點(diǎn)相連的邊必須是偶數(shù).由此得出結(jié)論:七橋問題無解.歐拉由七橋問題所引發(fā)的研究論文是圖論的開篇之作,因此稱歐拉為圖論之父.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ī)通訊網(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)化的問題.6.基本的網(wǎng)絡(luò)優(yōu)化問題基本的網(wǎng)絡(luò)優(yōu)化問題有:最短路徑問題、最小生成樹問題、最大流問題和最小費(fèi)用問題.圖論作為數(shù)學(xué)的一個分支,已經(jīng)有有效的算法來解決這些問題.當(dāng)然這當(dāng)中的有些問題也可以建立線性規(guī)劃的模型,但有時若變量特別多,約束也特別多,用線性規(guī)劃的方法求解效率不高甚至不能在可忍受的時間內(nèi)解決.而根據(jù)這些問題的特點(diǎn),采用網(wǎng)絡(luò)分析的方法去求解可能會非常有效.例如,在1978年,美國財政部的稅務(wù)分析部門在對卡特爾稅制改革做評估的過程中,就有一個100,000個約束以上,25,000,000個變量的問題,若用普通的線性規(guī)劃求解,預(yù)計要花7個月的時間.他們利用網(wǎng)絡(luò)分析的方法,將其分解成6個子問題,利用特殊的網(wǎng)絡(luò)計算機(jī)程序,花了大約7個小時問題就得到了解決.

圖的基本概念(2)定義2.鄰接結(jié)點(diǎn):關(guān)聯(lián)于同一條邊的兩個結(jié)點(diǎn).孤立結(jié)點(diǎn):不與任何結(jié)點(diǎn)相連接的結(jié)點(diǎn).鄰接邊:關(guān)聯(lián)于同一頂點(diǎn)的兩條邊.環(huán):兩端點(diǎn)相同的邊稱為環(huán)或自回路.平行邊:兩個結(jié)點(diǎn)間方向相同的若干條邊稱為平行邊或重邊對稱邊:兩端點(diǎn)相同但方向相反的兩條有向邊.圖的基本概念(3)定義3

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

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

特別,若,則以G-V1表示從G中刪去V1內(nèi)的所有點(diǎn)以及與這些頂點(diǎn)關(guān)聯(lián)的邊所得到的子圖,若V1={v},常把G-{v}簡記為G-v,,類似地,設(shè),G-E1表示在G中刪去E1中所有邊所得的子圖,同樣G-{e}簡記為G-e.路與連通圖(一)定義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的兩個端點(diǎn).數(shù)n(鏈中出現(xiàn)的邊數(shù))稱為鏈的長度.u(u0)和v(un)稱為鏈的端點(diǎn),其余的頂點(diǎn)稱為鏈的內(nèi)部點(diǎn).一條u-v鏈,當(dāng)uv時,稱它為開的,否則稱為閉的.邊互不相同的鏈稱為跡,內(nèi)部點(diǎn)互不相同的鏈稱為路.注釋1.(1)在一條鏈中,頂點(diǎn)和邊可以重復(fù).(2)若G是簡單圖,G中的鏈u0e1u1e2…un-1enun還可用結(jié)點(diǎn)序列u0u1…un-1un表示.(3)不含邊的鏈(即長度為0)稱為平凡鏈.(4)設(shè)W是有向圖D中u-v鏈(跡,路),指定W的方向從u到v.若W中所有邊的方向與此方向一致,則稱W為D中從u到V的有向鏈(跡,路).路與連通圖(二)定義2.兩端點(diǎn)相同的跡(即閉集)稱為回.兩端點(diǎn)相同的路(即閉路)稱為圈或回路.長度為K,奇數(shù),偶數(shù)的回(圈)分別稱為K,奇,偶回(圈).有向閉跡(閉路)稱為有向回(有向圈).路與連通圖(四)1.說明:容易驗(yàn)證,結(jié)點(diǎn)集V(G)上的頂點(diǎn)間的連通關(guān)系是V(G)上的一個等價關(guān)系,該等價關(guān)系確定V(G)的一個劃分{V1,V2,…,Vm},使得當(dāng)且僅當(dāng)兩個頂點(diǎn)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中每一對不同的頂點(diǎn)x和y都有一條路,即W(G)=1,則稱G是連通圖,反之稱為非連通圖.路與連通圖(五)引理1非平凡圖G是連通圖當(dāng)且僅當(dāng)對V(G)的每一個非空真子集S,定理3設(shè)G是P階連通圖,則懸掛點(diǎn):度數(shù)為1頂點(diǎn).定理4設(shè)連通圖G至少有兩個頂點(diǎn),其邊數(shù)小于頂點(diǎn)數(shù),則此圖至少有一個懸掛點(diǎn).路與連通圖(七)定義5設(shè)是有向圖,,若圖D中存在x到y(tǒng)的有向路,稱結(jié)點(diǎn)x可達(dá)結(jié)點(diǎn)y.規(guī)定x到自身總是可達(dá)的.

連通圖和二分圖(1)定義1如果在圖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沒有割點(diǎn)的非平凡連通圖稱為塊.G中不含割點(diǎn)的極大連通子圖稱為圖G的塊.定義3如果G的頂點(diǎn)集的一個真子集T滿足G-T不連通或是平凡圖,則稱T為G的一個點(diǎn)割.如果圖G的邊集的一個真子集S滿足G-S不連通或是平凡圖,則稱S為G的一個邊割.定義4設(shè)G是連通圖,稱是G的點(diǎn)割}為G的點(diǎn)連通度或連通度;稱是G的邊割}為G的邊連通度.定理1對一個圖G,有是圖G的最小頂點(diǎn)度.

圖的矩陣表示(1)1.鄰接矩陣:設(shè)是任意圖,其中V={x1,x2,…,xn},E={e1,e2,…,em},則n階方陣A=(aij)稱為G的鄰接矩陣.其中aij為圖G中以xi為起點(diǎn)且以xj為終點(diǎn)的邊的數(shù)目.說明1:由定義易知,無向圖的鄰接矩陣是對稱矩陣,而有向圖的鄰接矩陣未必是對稱矩陣.定理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的每一個頂點(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中的每個元素都不為零.2.關(guān)聯(lián)矩陣:設(shè)是有向圖,且V=,稱階矩陣M=(mij)為有向圖D的關(guān)聯(lián)矩陣,其中設(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)兩個頂點(diǎn));(2)關(guān)聯(lián)矩陣的每一行元素之和為對應(yīng)頂點(diǎn)的度;(3)若某行中元素全為零,則相應(yīng)頂點(diǎn)為孤立點(diǎn);(4)重邊所對應(yīng)的列完全相同.3.可達(dá)矩陣:設(shè)G=<V,E>是無重邊有向圖,其中V=,稱階矩陣P=(Pij)為G的可達(dá)矩陣.其中圖的矩陣表示(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)矩陣,其中圖的矩陣表示(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)兩個頂點(diǎn));(2)關(guān)聯(lián)矩陣的每一行元素之和為對應(yīng)頂點(diǎn)的度;(3)若某行中元素全為零,則相應(yīng)頂點(diǎn)為孤立點(diǎn);(4)重邊所對應(yīng)的列完全相同.歐拉圖(1)定義1給定無孤立結(jié)點(diǎn)的無向圖G,經(jīng)過圖G的每邊一次且僅一次的跡為一條歐拉路.經(jīng)過圖G的每邊一次且僅一次的回為一條歐拉回路.說明:(1)由定義,含有歐拉路(回)的圖顯然是連通的;(2)歐拉路是跡(邊互不重復(fù)),但不是嚴(yán)格意義上的路.定理1連通圖G具有歐拉回路當(dāng)且僅當(dāng)其每個頂點(diǎn)的度數(shù)為偶數(shù).歐拉圖與哈密頓圖(2)定理2連通圖G具有歐拉路而無歐拉回路,當(dāng)且僅當(dāng)G恰有兩個奇數(shù)度頂點(diǎn).定義2給定有向圖D,經(jīng)過D中每邊一次且僅一次的有向跡稱為D的有向歐拉路.經(jīng)過D中每邊一次且僅一次的有向閉跡(回),稱為有向歐拉回路.歐拉圖與哈密頓圖(3)定理3具有弱連通性的有向圖G具有有向歐拉回路,當(dāng)且僅當(dāng)G的每個結(jié)點(diǎn)的入度等于出度.具有弱連通性的有向圖G具有有向歐拉路,當(dāng)且僅當(dāng)在G中,一個結(jié)點(diǎn)的入度比出度大1,另一個結(jié)點(diǎn)的入度比出度小1,而其余每個結(jié)點(diǎn)的入度等于出度.定義3含有歐拉回路的無向連通圖與含有向歐拉回路的弱連通有向圖,統(tǒng)稱為歐拉圖.求Euler圖的Euler回路的Fleury算法.(1)任意選取一個頂點(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)除非沒有別的邊可選擇,ei+1不是Gi=G-{e1,e2,…,ei}的割邊.(3)當(dāng)(2)不能執(zhí)行時,停止.否則讓i+1→i,轉(zhuǎn)(2).(以p46為例)定理4若G是Euler圖,則Fleury算法終止時得到的跡是Euler回路。定義1給定無向圖G,若存在一條路經(jīng)過圖G的每個結(jié)點(diǎn)一次且僅一次,這條路稱為哈密頓路.若存在一條閉路經(jīng)過圖G的每個結(jié)點(diǎn)一次且僅一次,這條閉路稱為哈密頓回路.定義2給定有向圖D,若存在一條路經(jīng)過圖G的每個結(jié)點(diǎn)一次且僅一次,這條路稱為哈密頓有向路.若存在一條閉路經(jīng)過圖G的每個結(jié)點(diǎn)一次且僅一次,這條有向閉路稱為哈密頓有向回路.哈密頓圖(1)哈密頓圖(1)定義3具有哈密頓回路的無向圖與具有哈密頓有向回路的有向圖,統(tǒng)稱為哈密頓圖.例1對于完全圖Kn(n3),由于Kn中任意兩個頂點(diǎn)之間都有邊,從Kn的某一頂點(diǎn)開始,總可以遍歷其余節(jié)點(diǎn)后,再回到該結(jié)點(diǎn),因而Kn(n3)是哈密頓圖.說明:判斷一個給定的圖是否為哈密頓圖,是圖論中尚未解決的難題之一,下面介紹若干必要條件和充分條件.哈密頓圖(3)定理1設(shè)任意n(n3)階圖G,對所有不同非鄰接頂點(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)用一條邊連接起來得圖G’,對圖G’重復(fù)上述過程,直到不再有這樣的結(jié)點(diǎn)對存在為止,所得到的圖,稱為是原圖G的閉包,記作C(G).定理3一個圖是哈密頓圖當(dāng)且僅當(dāng)它的閉包是哈密頓圖.定理4設(shè)G是階至少為3的圖,如果G的閉包是完全圖,則G是哈密頓圖.定理5如果G是一個n階(n3)任意圖,且對G的每個頂點(diǎn)x,都有deg(x)n/2,則G是哈密頓圖.說明:由哈密頓圖的定義可知,哈密頓圖有向圖必是強(qiáng)連通的,哈密頓無向圖必?zé)o割點(diǎn).8.哈密頓圖(4)定理5若G是一個哈密頓圖,則對于V(G)的每個非空真子集S,其中W(G-S)為G-S的分支數(shù).

9.哈密頓圖(5)說明:定理6只是一個必要條件,如下的皮特森圖,盡管有但它不是哈密頓圖.

10.哈密頓圖(6)應(yīng)用定理5若G是一個n(n3)階任意圖,且對G的每個頂點(diǎn)x,都有deg(x)n/2,則G是哈密頓圖.例1.11個學(xué)生要共進(jìn)晚餐,他們將坐成一個圓桌,計劃要求每次晚餐上,每個學(xué)生有完全不同的鄰座.這樣能共進(jìn)晚餐幾次.分析:如何將該問題轉(zhuǎn)化成圖論中的相關(guān)問題.實(shí)際上,可以這樣來構(gòu)造一個圖,即以每個學(xué)生看作圖的頂點(diǎn),以學(xué)生的鄰座關(guān)系作為圖的邊,11.哈密頓圖(7)這樣學(xué)生每次進(jìn)餐的就坐方式就對應(yīng)一個哈密頓回路.兩次進(jìn)餐中,每個學(xué)生有完全不同的鄰座對應(yīng)著兩個沒有公共邊的哈密頓回路.因?yàn)槊總€學(xué)生都可以與其余學(xué)生鄰座,故問題轉(zhuǎn)化為在圖K11中找出所有沒有公共邊的哈密頓回路的個數(shù).K11中共有條邊,而K11中每條哈密頓回路的長度為11,因此K11中最多有55/11=5條沒有公共邊的哈密頓回路,構(gòu)造方法為:設(shè)第一條哈密頓回路為(1,2,3,…,11,1),將1固定在圓心,其余固定在圓周上,如圖(1)所示,然后將圖的頂點(diǎn)旋轉(zhuǎn)i×3600/10(i=1,2,3,4),從而就得到另外4個哈密頓回路.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第五節(jié)最短路路問題1.加權(quán)圖:邊上有數(shù)的圖稱為加權(quán)圖;該數(shù)稱為邊的權(quán)。2.最短路問題:如何求兩個結(jié)點(diǎn)之間的最短路.3.迪克斯曲拉算法:這是荷蘭計算機(jī)科學(xué)教授EdsgerW.Dijkstra(1930-)在1959年發(fā)現(xiàn)的一個算法.他在1972年獲得計算機(jī)協(xié)會授予的圖靈獎,這是計算機(jī)科學(xué)中最具聲望的獎項(xiàng).迪克斯曲拉算法是求出一個連通加權(quán)簡單圖中從結(jié)點(diǎn)a到結(jié)點(diǎn)z的最短路.邊{i,j}的權(quán)(i,j)>0,且結(jié)點(diǎn)x的標(biāo)號為L(x),結(jié)束時,L(z)是從x到z的最短路的長度.4.迪克斯曲拉算法流程ProcedureDijkstra(G:所有權(quán)為正的加權(quá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)最小的一個頂點(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的最短路的長度}.例1.用迪克斯曲拉算法求下圖所示的加權(quán)圖中頂點(diǎn)a與z之間最短路的長度.（見65頁）a4b5d2110c8e263z定理1迪克斯曲拉算法求出連通簡單無向圖的中兩點(diǎn)之間的最短路的長度。定理2迪克斯曲拉算法使用O(n2)次運(yùn)算（加法和比較）來求出n階連通簡單無向加權(quán)圖中兩個頂點(diǎn)之間的最短路的長度。迪克斯曲拉算法可以推廣到求加權(quán)有向圖的最短路。定理3設(shè)有向圖G中不含長度非正的有向圈，并且從點(diǎn)1到其余各點(diǎn)都有有限長的有向路，那么式（2）有唯一有限解。.Floyd算法Dijkstra算法只求出一個特定頂點(diǎn)到其他各頂點(diǎn)的最短路.但在許多實(shí)際問題中,需求出任意兩點(diǎn)之間的最短路,如全國各城市之間最短的航線,選址問題等.Floyd算法可以比較好地解決這一問題.為介紹Floyd算法,先定義矩陣的兩種運(yùn)算.定義1已知矩陣A=(aij)ml,B=(bij)ln,規(guī)定C=AB=(cij)mn,其中cij=min(ai1+b1j,ai2+b2j,…,ail+blj).定義2已知矩陣A=(aij)mn,B=(bij)mn,規(guī)定D=A?B=(dij)mn,其中dij=min(aij,bij).可以利用上面定義的運(yùn)算求任意兩點(diǎn)間的最短距離.

已知n階加權(quá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無邊相連時,則取dij=.然后依次計算出矩陣D[2],D[3],…,D[n]及S,其中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邊的路(在有向圖中即為有向路)中的長度最短者.這就是Floyd算法.Floyd算法的時間復(fù)雜度為O(n4).v121v27v6v41332v6例2.利用Floyd算法求下圖中任意兩點(diǎn)間最短有向路的長度.(p71-73)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)過n次結(jié)點(diǎn)轉(zhuǎn)換每一次保留最短路的長度。舉例見P74.旅行推銷員問題和中國投遞員問題（NPC問題）

一、旅行推銷員問題

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

v43

v58

v6B4455447799

8864636C446466654444793836D44

433

455364666642樹的基本概念定義1樹是無圈連通無向圖.樹中度數(shù)為1的結(jié)點(diǎn)稱為樹的葉.樹中度數(shù)大于1的結(jié)點(diǎn)稱為樹的分枝點(diǎn)或內(nèi)點(diǎn).不相交的若干樹稱為森林,即森林的每個連通分枝是樹.定義2設(shè)T是有向圖,若T的基礎(chǔ)圖是樹,稱T是有向樹.定義3僅一個結(jié)點(diǎn)的入度為0,其余所有結(jié)點(diǎn)的入度都為1的有向樹稱為根樹.入度為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的有向路的長度,稱為v的層數(shù).根樹的高度就是頂點(diǎn)層數(shù)的最大值.支撐樹定義1若T是G的一個生成子圖且又是一棵樹,則稱T是圖G的一棵生成樹或支撐樹.生成樹T中的邊稱為T的樹枝,不在生成樹T中的G的邊,稱為樹T的弦.定理1圖G有生成樹G為連通圖.求連通簡單圖的生成樹

深度優(yōu)先搜索和廣度優(yōu)先搜索深度優(yōu)先搜索:任意選擇圖G的一個頂點(diǎn)為根,通過不斷地增加邊來形成以頂點(diǎn)v0為起點(diǎn)的路,直到這條路經(jīng)過圖G的每個頂點(diǎn),此時得到的這條路就是該圖的生成樹.其中每條新邊都與路上的一個頂點(diǎn)以及不在路上的一個頂點(diǎn)關(guān)聯(lián).如果這條路不經(jīng)過圖G的所有頂點(diǎn),則返回倒數(shù)第二個頂點(diǎn),繼續(xù)重復(fù)上面過程,直到不能添加更多的邊為止.又圖G是有有限邊數(shù)的連通圖,故最后總能產(chǎn)生一棵生成樹.例1用深度搜索來找出下圖G的生成樹abcdefghijk廣度優(yōu)先搜索基本思想:從圖的頂點(diǎn)中任意地選擇一個根,然后添加與該頂點(diǎn)相關(guān)聯(lián)的所有邊,在這個階段添加的新頂點(diǎn)成為生成樹里1層上的頂點(diǎn),任意地排序它們.下一步,按順序訪問1層上的每一個頂點(diǎn),只要不產(chǎn)生回路,就添加與這個頂點(diǎn)相關(guān)聯(lián)的每條邊,這樣就產(chǎn)生了樹里2層上的頂點(diǎn).遵循這樣的原則繼續(xù)下去,經(jīng)有限步驟后(因?yàn)閳D中只有有限條邊)就產(chǎn)生了生成樹.例2.用廣度優(yōu)先搜索找出例1中圖G的生成樹.P106最小支撐樹定義1:連通加權(quán)圖里權(quán)和最小的支撐樹稱為最小支撐樹.最小支撐樹的實(shí)際應(yīng)用背景:在某一國家或地區(qū),需建造一鐵路網(wǎng)/公路網(wǎng)把一些城市連接起來,需要總長度最短或造價最低.尋找最小支撐樹的貪心算法原理:通過添加還沒使用過的具有規(guī)定性質(zhì)且權(quán)最小的邊來進(jìn)行的,其實(shí)質(zhì)就是在每步上進(jìn)行最優(yōu)選擇,即“局部最優(yōu)化”.

普林算法算法的基本思想:首先選擇帶最小權(quán)的邊,把它放進(jìn)支撐樹里.相繼向樹里添加帶最小權(quán)的邊,這些邊與已在樹里的頂點(diǎn)相關(guān)聯(lián),并且不與已在樹里的邊形成圈,直到添加了n-1條邊止.算法描述如下:算法1普林算法Procedureprim(G:帶n個頂點(diǎn)的連通無向圖)T:=權(quán)最小的邊Fori:=1ton-2begine:=與T里頂點(diǎn)相關(guān)聯(lián)的權(quán)最小的邊,并且若添加到T里則不形成圈T:=添加e之后的Tend{T是G的最小支撐樹}例1用普林算法求下圖所示的最小支撐樹定理1普林算法是正確的,即在算法結(jié)束時,得到一棵最小支撐樹.(證略)1745102616158abcgfde克魯斯卡爾(Kruskal)算法算法的基本思想:選擇圖中最小的一條邊,相繼添加不與已經(jīng)選擇的邊形成圈的權(quán)最小的邊,直到挑選n-1(n為結(jié)點(diǎn)的個數(shù))條邊為止.該算法的偽代碼如下:ProcedureKruskal(G:n個頂點(diǎ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é)點(diǎn)數(shù).基于破圈法的最小生成樹的生成方法該方法是由管梅谷教授給出的,其基本思想為:設(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的一棵最小生成樹.平面圖的著色定義1設(shè)G是無孤立結(jié)點(diǎn)的連通的平面圖，且G有K個面F1，F(xiàn)2，…Fk(包括外部面).則按下列過程作G的對偶圖G.（1）在G的每個面內(nèi)設(shè)置一個結(jié)點(diǎn)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的對偶圖為圖中虛線.12341324定義2圖的著色是對該圖的每個頂點(diǎn)都指定一種顏色，使沒有兩個相鄰的頂點(diǎn)指定為相同的顏色。如果這些頂點(diǎn)選自于一個有k種顏色的集合，而不管k種顏色是否都用到，這樣的著色稱為k著色。定義3圖G的色數(shù)是著色這個圖G所需要的最少顏色數(shù)。記作(G)。圖G的色素也稱為圖G的點(diǎn)色素.從定義可知,對于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)的一個上界.定理1設(shè)u和v是圖G中兩個不相鄰的頂點(diǎn),則(G)=min{(G+{u,v}),(G?{u,v})},其中G?{u,v}是把G中結(jié)點(diǎn)u與v重合成一個新結(jié)點(diǎn)，且G中分別與u與v關(guān)聯(lián)的邊都與該新結(jié)點(diǎn)關(guān)聯(lián)。四色問題:連通簡單平面圖的色素不超過4.四色問題是蓋思里于1852年提出,后經(jīng)眾多數(shù)學(xué)家嘗試證明,均以失敗告終.1976年,美國數(shù)學(xué)家阿佩爾和黑肯宣布借助用計算機(jī)證明,但時間超過了1000小時,其可靠性仍在置疑之中.例1求下圖G和H的色數(shù)acfgbedGHa:紅,b:藍(lán),c:綠,d:紅,e:綠，f:藍(lán),g:紅(3色)定理2（五色定理）連通簡單平面圖G的色數(shù)為不超過5.例2.由n(n3)個頂點(diǎn)v1,v2,…,vn以及邊{v1,v2},{v2,v3},…,{vn-1,vn}{vn,v1}組成的圖稱為圈圖,記作Cn,試問圈圖的Cn的色數(shù)是多少。（分n為奇數(shù)，或偶數(shù)）例3.Kn和Km,n的色數(shù)分別是多少？解:由于Kn的每兩個頂點(diǎn)都相鄰,而當(dāng)兩個相鄰的頂點(diǎn)必指定不同的顏色,故Kn的色素為n.Km,n的色數(shù)為2.用一種顏色著色m個頂點(diǎn),用另一種顏色著色n個頂點(diǎn).第五節(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).電視頻道分配問題某地區(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).考試安排問題某高校有n門選修課程v1,v2,…,vn需要進(jìn)行期末考試.同一學(xué)生不能在同一天里參加兩門課程的考試.問學(xué)校的期末考試需要幾天?構(gòu)建簡單圖G=<V,E>,其中V(G)={v1,v2,…,vn}邊{vi,vj}E(G)vi與vj被同一同學(xué)選修.故考試需要的最小天數(shù)等于圖G的色素x(G).順序著色算法

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

邊著色可以轉(zhuǎn)化為相應(yīng)的點(diǎn)著色,即在邊著色圖中,將所有的邊對應(yīng)地轉(zhuǎn)化成點(diǎn)著色圖中的結(jié)點(diǎn),結(jié)點(diǎn)轉(zhuǎn)化成相應(yīng)的邊.因此,由點(diǎn)著色性質(zhì)定理不難得到如下定理.定理1若G是非空連通的簡單圖，G的最大頂點(diǎn)度為,則’(G)+1。（不證）定義3.圖G的不同K—著色的數(shù)目，稱為圖G的色多項(xiàng)式。記作f(G,k).說明:(1)若k<x(G),此時k-著色不存在,顯然有f(G,k)=0,從而即知,滿足f(G,k)>0的最小的k即為G的色數(shù).(2)設(shè)mi是i種顏色對圖G的頂點(diǎn)進(jìn)行著色的不同方案數(shù).用k(ki)種顏色對圖G進(jìn)行著色,每取i種顏色時,共有miCki種不同的著色方案,故有:f(G,k)=m1Ck1+m2Ck2+…+mnCkn,其中n為圖G的頂點(diǎn)數(shù).顯然,f(G,k)是k的多項(xiàng)式.圖的兩種基本運(yùn)算:(1)Guv設(shè)u,v是圖G的不鄰接的兩個頂點(diǎn),把u,v收縮成一個頂點(diǎn)x,并把G中凡與u,v關(guān)聯(lián)的邊均使之與x關(guān)聯(lián),這樣所得的新圖。記作Guv.(2)G:e把圖G的一條邊刪去并使它的兩個端點(diǎn)重合,也即邊e被收縮.這樣得到的新圖。記作G:e.定理3.設(shè)u,v是G的兩個不相鄰的頂點(diǎn)，則f(G,k)=f(G+{u,v},k)+f(G:uv,k)說明:定理3表明,若G是有P個頂點(diǎn)和q條邊的圖,則有一個q+1條邊的圖G1=G+{u,v}(u與v不相鄰接)和一個有P-1個頂點(diǎn)的圖G2=Guv,使f(G,k)=f(G1,k)+f(G2,k).對G1和G2依次類推,直到只出現(xiàn)完全圖為止.因此,一個圖的色多項(xiàng)式f(G,k)是f(Kn,k)型的表達(dá)式的和.完全圖的色多項(xiàng)式例1.對三階完全圖K3而言,有f(K3,k)=k(k-1)(k-2).解:由于對K3中的任何指定一個頂點(diǎn),可以用k種顏色中的任何一種進(jìn)行著色;對K3的第二個頂點(diǎn),可以用k-1種顏色中的任何一種進(jìn)行著色;對K3的第三個頂點(diǎn),可以用k-2種顏色中的任何一種進(jìn)行著色.一般地,對于P階完全圖，有f(Kp,k)=k(k-1)(k-2)…(k-p+1)例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匹配匹配問題是運(yùn)籌學(xué)的重要問題之一,也是圖論研究的重點(diǎn)內(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)的頂點(diǎn)稱為M飽和點(diǎn).若圖G的頂點(diǎn)都是M飽和,則稱為G的完美匹配.說明:(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的兩個端點(diǎn)為M非飽和點(diǎn),則稱P為M可增廣路.例1.求下圖G的一條交錯路和一條可增廣路.62341587匹配的幾個性質(zhì)定理定理1.設(shè)M1和M2是圖G的兩個不同匹配,由M1M2導(dǎo)出的G的邊導(dǎo)出子圖記作H,則H的任意連通分支是下列情況之一:(1)邊在M1和M2中交錯出現(xiàn)的偶圈.(2)邊在M1和M2中交錯出現(xiàn)的路.定理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).定理3(Hall定理,1935)設(shè)G是有二部劃分(V1,V2)的二分圖,則G含有飽和V1的每個頂點(diǎn)的匹配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有完美匹配.定理4.G有完美匹配O(G-S)S,SV(G),其中O(G-S)是G-S的奇數(shù)階連通分支數(shù)目.例1.有n張紙牌,每張紙牌的正反兩面都寫上1,2,…n的某一個數(shù),證明:如果每個數(shù)字恰好出現(xiàn)兩次,則這些紙牌一定可以這樣攤開,使朝上的面中1,2,…n都出現(xiàn).證明:作一個二分圖G=<V1,V2,E>,其中V1={1,2,…,n},V2={y1,y2,…,yn}表示這n張紙牌.i與yi之間連接的邊數(shù)等于數(shù)i在紙牌yj中出現(xiàn)的次數(shù),這樣得到的圖G是一個2-正則二分圖,因此圖G中有完美匹配,設(shè)為M={1yi1,2yi2,…,nyin}

則只要把紙牌yi1中的1朝上,yi2中的2朝上,…,yin的n朝上,這樣攤開,這樣攤開的紙牌就能使上面中1,2,…,n都出現(xiàn).例2.某工廠生產(chǎn)由6種不同顏色的紗布織成的雙色布,由該廠所生產(chǎn)的雙色布中,每一種顏色至少和其他三種顏色搭配.證明可以挑選出三種不同的雙色布,它們含有所有的6種顏色.(從匹配方面思考)第五節(jié)最大匹配的生成算法-匈牙利算法定義1.根在x的M交錯子圖:設(shè)M是圖G的匹配,x是G中非M飽和點(diǎn).G中由起點(diǎn)為x的M交錯路所能連接的頂點(diǎn)集所導(dǎo)出的G的導(dǎo)出子圖稱為根在x的M交錯子圖.定理1.設(shè)M是具有二部劃分(V1,V2)的二分圖G的匹配,xV1是非M飽