資源描述：
《09_圖論初步.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、圖論初步第六講 圖論初步§6.1引言圖論是運籌學的一個經(jīng)典和重要的分支，它起源于歐拉（Euler）對七橋問題的抽象和論證。1936年，匈牙利數(shù)學家柯尼希（K?nig）出版了圖論的第一部專著《有限圖與無限圖理論》，豎立了圖論發(fā)展的第一座里程碑。此后，圖論進入發(fā)展與突破的快車道，所研究的問題涉及經(jīng)濟管理、工業(yè)工程、交通運輸、計算機科學與信息技術、通訊與網(wǎng)絡技術等諸多領域。近幾十年來，由于計算機技術和科學的飛速發(fā)展，大大地促進了圖論研究和應用，圖論的理論和方法已經(jīng)滲透到物理、化學、通訊科學、建筑學、生物遺傳學、心理學、經(jīng)濟學、社會學等學科中。圖論中所謂的“圖”是指某類具體
2、事物和這些事物之間的聯(lián)系。如果我們用點表示這些具體事物，用連接兩點的線段（直的或曲的）表示兩個事物的特定的聯(lián)系，就得到了描述這個“圖”的幾何形象。圖論為任何一個包含了一種二元關系的離散系統(tǒng)提供了一個數(shù)學模型，借助于圖論的概念、理論和方法，可以對該模型求解。引例6.1.1最短路問題（SPP－shortestpathproblem）一名貨柜車司機奉命在最短的時間內(nèi)將一車貨物從甲地運往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯，因此有多種行車路線，這名司機應選擇哪條線路呢？假設貨柜車的運行速度是恒定的，那么這一問題相當于需要找到一條從甲地到乙地的最短路。引例6.1.2中國郵遞員問
3、題（CPP－chinesepostmanproblem）一名郵遞員負責投遞某個街區(qū)的郵件。如何為他（她）設計一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？由于這一問題是我國管梅谷教授1960年首先提出的，所以國際上稱之為中國郵遞員問題。引例6.1.3旅行商問題（TSP－travelingsalesmanproblem）一名推銷員準備前往若干城市推銷產(chǎn)品。如何為他（她）設計一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地）？這一問題的研究歷史十分悠久，通常稱之為旅行商問題。引例6.1.4指派問題（assignmentp
4、roblem）一家公司經(jīng)理準備安排名員工去完成項任務，每人一項。由于各員工的特點不同，不同的員工去完成同一項任務時所獲得的回報是不同的。如何分配工作方案可以使總回報最大？引例6.1.5運輸問題（transportationproblem）某種原材料有個產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運往個使用這些原材料的工廠。假定個產(chǎn)地的產(chǎn)量和家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運費已知，那么如何安排運輸方案可以使總運輸成本最低？§6.2圖的基本概念§6.2.1圖的定義定義6.2.1稱數(shù)學結構G={V(G),E(G),?G}為一個圖，其中V(G)={v1,v2,…,vn}
5、稱為圖G的頂點集（vertexset）或節(jié)點集（nodeset），V(G)中的每一個元素vi（i=1,2,…,n）稱為該圖的一個頂點（vertex）或節(jié)點（node）；E(G)={e1,e2,…,em}稱為圖G的邊集（edgeset），E(G)中的每一個元素ek（即V(G)中某兩個元素vi,vj的無序對）記為ek=(vi,vj)或ek=vivj=ek=vjvi（k=1,2,…,m），被稱為該圖的一條從vi到vj的邊（edge）；?G是從E(G)到V(G)?V(G)的一個映射，它指定E(G)中的每條邊與V(G)中的點組成的無序點對相對應。若用小圓點表示點集V(G)中的
6、點，連線表示邊集E(G)中的邊，則可用圖形將圖表示出來，稱之為圖的圖形。我們常用圖的圖形代表圖本身。例6.2.1設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}是一個圖，其圖形如圖所示。圖6.2.1例6.2.2設V={v1,v2,v3,v4}，E={v1v2,v1v2,v2v3}，則G={V,E}是一個圖，其圖形如圖所示。圖6.2.2定義6.2.2設e=uv為圖G的一條邊，我們稱u，v是e的端點，u
7、與v相鄰，邊e與點u（或v）相關聯(lián)；稱u是e的起點，v是e的終點。若兩條邊e1與e2有共同的端點，則稱邊e1與e2相鄰；稱有相同起點和終點的兩條邊為重邊；稱兩端點均相同的邊為環(huán)；稱不與任何邊相關聯(lián)的點為孤立點。無環(huán)且無重邊的圖稱之為簡單圖。例6.2.1和例6.2.2都不是簡單圖，因為例6.2.1中既含重邊（e2與e3）又含環(huán)（e5），而例6.2.2中含重邊（v1v2）。下圖中給出的則是簡單圖。圖6.2.3任意兩點均相鄰的簡單圖稱之為完全圖。n個點的完全圖記為Kn，圖6.2.4中給出的分別是K2，K3，K4。圖6.2.4如果圖G的各條邊都被賦予了方向，則稱圖G為有
