《圖論初步》PPT課件

《《圖論初步》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、圖論初步第六講圖論初步§6.1引言圖論是運(yùn)籌學(xué)的一個(gè)經(jīng)典和重要的分支，它起源于歐拉（Euler）對(duì)七橋問(wèn)題的抽象和論證。1936年，匈牙利數(shù)學(xué)家柯尼希（K?nig）出版了圖論的第一部專著《有限圖與無(wú)限圖理論》，豎立了圖論發(fā)展的第一座里程碑。此后，圖論進(jìn)入發(fā)展與突破的快車道，所研究的問(wèn)題涉及經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸、計(jì)算機(jī)科學(xué)與信息技術(shù)、通訊與網(wǎng)絡(luò)技術(shù)等諸多領(lǐng)域。近幾十年來(lái)，由于計(jì)算機(jī)技術(shù)和科學(xué)的飛速發(fā)展，大大地促進(jìn)了圖論研究和應(yīng)用，圖論的理論和方法已經(jīng)滲透到物理、化學(xué)、通訊科學(xué)、建筑學(xué)、生物遺傳學(xué)、心理學(xué)、經(jīng)濟(jì)學(xué)、社會(huì)學(xué)等學(xué)科中。圖論中所謂的“圖”是指某類具體事物和這些事物之間的聯(lián)

2、系。如果我們用點(diǎn)表示這些具體事物，用連接兩點(diǎn)的線段（直的或曲的）表示兩個(gè)事物的特定的聯(lián)系，就得到了描述這個(gè)“圖”的幾何形象。圖論為任何一個(gè)包含了一種二元關(guān)系的離散系統(tǒng)提供了一個(gè)數(shù)學(xué)模型，借助于圖論的概念、理論和方法，可以對(duì)該模型求解。引例6.1.1最短路問(wèn)題（SPP－shortestpathproblem）一名貨柜車司機(jī)奉命在最短的時(shí)間內(nèi)將一車貨物從甲地運(yùn)往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯(cuò)，因此有多種行車路線，這名司機(jī)應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運(yùn)行速度是恒定的，那么這一問(wèn)題相當(dāng)于需要找到一條從甲地到乙地的最短路。引例6.1.2中國(guó)郵遞員問(wèn)題（CPP－chinesepostmanpr

3、oblem）一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件。如何為他（她）設(shè)計(jì)一條最短的投遞路線（從郵局出發(fā)，經(jīng)過(guò)投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？由于這一問(wèn)題是我國(guó)管梅谷教授1960年首先提出的，所以國(guó)際上稱之為中國(guó)郵遞員問(wèn)題。引例6.1.3旅行商問(wèn)題（TSP－travelingsalesmanproblem）一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他（她）設(shè)計(jì)一條最短的旅行路線（從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市恰好一次，最后返回駐地）？這一問(wèn)題的研究歷史十分悠久，通常稱之為旅行商問(wèn)題。引例6.1.4指派問(wèn)題（assignmentproblem）一家公司經(jīng)理準(zhǔn)備安排名員工去完成項(xiàng)任務(wù)，每人一項(xiàng)。由

4、于各員工的特點(diǎn)不同，不同的員工去完成同一項(xiàng)任務(wù)時(shí)所獲得的回報(bào)是不同的。如何分配工作方案可以使總回報(bào)最大？引例6.1.5運(yùn)輸問(wèn)題（transportationproblem）某種原材料有個(gè)產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運(yùn)往個(gè)使用這些原材料的工廠。假定個(gè)產(chǎn)地的產(chǎn)量和家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運(yùn)費(fèi)已知，那么如何安排運(yùn)輸方案可以使總運(yùn)輸成本最低？§6.2圖的基本概念§6.2.1圖的定義定義6.2.1稱數(shù)學(xué)結(jié)構(gòu)G={V(G),E(G),?G}為一個(gè)圖，其中V(G)={v1,v2,…,vn}稱為圖G的頂點(diǎn)集（vertexset）或節(jié)點(diǎn)集（nodeset），V(G)中的每一個(gè)元素

5、vi（i=1,2,…,n）稱為該圖的一個(gè)頂點(diǎn)（vertex）或節(jié)點(diǎn)（node）；E(G)={e1,e2,…,em}稱為圖G的邊集（edgeset），E(G)中的每一個(gè)元素ek（即V(G)中某兩個(gè)元素vi,vj的無(wú)序?qū)Γ┯洖閑k=(vi,vj)或ek=vivj=ek=vjvi（k=1,2,…,m），被稱為該圖的一條從vi到vj的邊（edge）；?G是從E(G)到V(G)?V(G)的一個(gè)映射，它指定E(G)中的每條邊與V(G)中的點(diǎn)組成的無(wú)序點(diǎn)對(duì)相對(duì)應(yīng)。若用小圓點(diǎn)表示點(diǎn)集V(G)中的點(diǎn)，連線表示邊集E(G)中的邊，則可用圖形將圖表示出來(lái)，稱之為圖的圖形。我們常用圖的圖形代表圖本身。例6.2.

6、1設(shè)V={v1,v2,v3,v4}，E={e1,e2,e3,e4,e5}，?：E?V?V定義為?(e1)=v1v2，?(e2)=v2v3，?(e3)=v2v3，?(e4)=v3v4，?(e5)=v4v4，則G={V,E}是一個(gè)圖，其圖形如圖所示。圖6.2.1例6.2.2設(shè)V={v1,v2,v3,v4}，E={v1v2,v1v2,v2v3}，則G={V,E}是一個(gè)圖，其圖形如圖所示。圖6.2.2定義6.2.2設(shè)e=uv為圖G的一條邊，我們稱u，v是e的端點(diǎn)，u與v相鄰，邊e與點(diǎn)u（或v）相關(guān)聯(lián)；稱u是e的起點(diǎn)，v是e的終點(diǎn)。若兩條邊e1與e2有共同的端點(diǎn)，則稱邊e1與e2相鄰；稱有相同起點(diǎn)

7、和終點(diǎn)的兩條邊為重邊；稱兩端點(diǎn)均相同的邊為環(huán)；稱不與任何邊相關(guān)聯(lián)的點(diǎn)為孤立點(diǎn)。無(wú)環(huán)且無(wú)重邊的圖稱之為簡(jiǎn)單圖。例6.2.1和例6.2.2都不是簡(jiǎn)單圖，因?yàn)槔?.2.1中既含重邊（e2與e3）又含環(huán)（e5），而例6.2.2中含重邊（v1v2）。下圖中給出的則是簡(jiǎn)單圖。圖6.2.3任意兩點(diǎn)均相鄰的簡(jiǎn)單圖稱之為完全圖。n個(gè)點(diǎn)的完全圖記為Kn，圖6.2.4中給出的分別是K2，K3，K4。圖6.2.4如果圖G的各條邊都被賦予了方向，則稱圖G為有