圖的基本概念演示文稿

圖的基本概念演示文稿目前一頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)圖的基本概念目前二頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)一、涉及圖論的歷年數(shù)學(xué)建模題目7、99B鉆井布局：最大完全子圖8、00B管道訂購(gòu)：最短路9、01B公交車調(diào)度10、02D賽程安排11、04A奧運(yùn)會(huì)臨時(shí)超市網(wǎng)點(diǎn)設(shè)計(jì)12、07乘公交，看奧運(yùn)目前三頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)一、涉及圖論的歷年數(shù)學(xué)建模題目13、08C地面搜索14、08DNBA賽程的分析與評(píng)價(jià)目前四頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)1.問(wèn)題引入與分析1)98年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B題“最佳災(zāi)今年(1998年)夏天某縣遭受水災(zāi).為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視.巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線.情巡視路線”中的前兩個(gè)問(wèn)題是這樣的：目前五頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)1）若分三組（路）巡視，試設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路線.2）假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2小時(shí)，在各村停留時(shí)間t=1小時(shí)，汽車行駛速度V=35公里/小時(shí).要在24小時(shí)內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下最佳的巡視路線.目前六頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)公路邊的數(shù)字為該路段的公里數(shù).目前七頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)2)問(wèn)題分析：本題給出了某縣的公路網(wǎng)絡(luò)圖，要求的是在不同的條件下，災(zāi)情巡視的最佳分組方案和路線.將每個(gè)鄉(xiāng)（鎮(zhèn)）或村看作一個(gè)圖的頂點(diǎn)，各鄉(xiāng)鎮(zhèn)、村之間的公路看作此圖對(duì)應(yīng)頂點(diǎn)間的邊，各條再回到點(diǎn)O，使得總權(quán)（路程或時(shí)間）最小.公路的長(zhǎng)度（或行駛時(shí)間）看作對(duì)應(yīng)邊上的權(quán)，所給公路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問(wèn)題就轉(zhuǎn)化圖論中一類稱之為旅行售貨員問(wèn)題，即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)O出發(fā)，行遍所有頂點(diǎn)至少一次目前八頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)二、圖論簡(jiǎn)介圖論是應(yīng)用十分廣泛的運(yùn)籌學(xué)分支，它已廣泛地應(yīng)用在物理學(xué)、化學(xué)、控制論、信息論、科學(xué)管理、電子計(jì)算機(jī)等各個(gè)領(lǐng)域。在實(shí)際生活、生產(chǎn)和科學(xué)研究中，有很多問(wèn)題可以用圖論的理論和方法來(lái)解決。目前九頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)例如：在組織生產(chǎn)中，為完成某項(xiàng)生產(chǎn)任務(wù)，各工序之間怎樣銜接，才能使生產(chǎn)任務(wù)完成得既快又好。一個(gè)郵遞員送信，要走完他負(fù)責(zé)投遞的全部街道，完成任務(wù)后回到郵局，應(yīng)該按照怎樣的路線走，所走的路程最短。各種通信網(wǎng)絡(luò)的合理架設(shè)，交通網(wǎng)絡(luò)的合理分布等。目前十頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)圖論是運(yùn)籌學(xué)的一個(gè)經(jīng)典和重要的分支，它起源于18世紀(jì)歐拉（Euler）對(duì)七橋問(wèn)題的抽象和論證。1936年，匈牙利數(shù)學(xué)家柯尼希（K?nig）出版了圖論的第一部專著《有限圖與無(wú)限圖理論》，豎立了圖論發(fā)展的第一座里程碑。目前十一頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)幾個(gè)著名的圖論問(wèn)題：2.1七橋問(wèn)題（Euler）18世紀(jì)東普魯士有一個(gè)城市稱為哥尼斯堡，它位于普雷格爾河畔，河中有兩個(gè)小島，通過(guò)七座橋彼此相聯(lián)（如圖2.1）。當(dāng)時(shí)有人提出：

能否從某個(gè)地點(diǎn)出發(fā)經(jīng)過(guò)每個(gè)橋一次且僅一次然后返回出發(fā)點(diǎn)？DABC圖2.1目前十二頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)DABCABCD建模：點(diǎn)——陸地島嶼邊——橋Euler的做法：圖2.1圖2.2目前十三頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)2.2Hamilton周游世界問(wèn)題1859年Hamilton提出這樣一個(gè)問(wèn)題：一個(gè)正十二面體有20個(gè)頂點(diǎn)，它們代表世界上20個(gè)重要城市。正十二面體的每個(gè)面均為五邊形，若兩個(gè)頂點(diǎn)之間有邊相連，則表示相應(yīng)的城市之間有航線相通。Hamilton提出“能否從某城市出發(fā)經(jīng)過(guò)每個(gè)城市一次且僅一次然后返回出發(fā)點(diǎn)？”目前十四頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)十二面體的20個(gè)頂點(diǎn)代表世界上20個(gè)城市，能否從某個(gè)城市出發(fā)在十二面體上依次經(jīng)過(guò)每個(gè)城市恰好一次最后回到出發(fā)點(diǎn)？目前十五頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)2.3四色問(wèn)題（猜想）四色問(wèn)題又稱四色猜想、四色定理，是世界近代三大數(shù)學(xué)難題之一。地圖四色定理(Fourcolortheorem)最先是由一位叫古德里（FrancisGuthrie）的英國(guó)大學(xué)生提出來(lái)的。德·摩根（AugustusDeMorgan）1852年10月23日致哈密頓的一封信提供了有關(guān)四色定理來(lái)源的最原始的記載。目前十六頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)德·摩爾根致哈密頓的信（1852年10月23日）

我的一位學(xué)生今天請(qǐng)我解釋一個(gè)我過(guò)去不知道，現(xiàn)在仍不甚了了的事實(shí)。他說(shuō)如果任意劃分一個(gè)圖形并給各部分著上顏色，使任何具有公共邊界的部分顏色不同，那么需要且僅需要四種顏色就夠了。下圖是需要四種顏色的例子（圖1）。目前十七頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)1890年希五德（Heawood）指出“4換為5”猜想成立。1976年美國(guó)數(shù)學(xué)家阿佩爾（K.Appel）與哈肯（W.Haken）在兩臺(tái)百萬(wàn)次的電子計(jì)算機(jī)上花了1200小時(shí)，作了100億判斷，證明了猜想成立。猜想成為定理。目前十八頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)2.4中國(guó)郵路問(wèn)題或中國(guó)郵遞員問(wèn)題（CPP－ChinesePostmanProblem）1962年中國(guó)數(shù)學(xué)家管梅谷提出：一個(gè)郵遞員從郵局出發(fā)遞送郵件，要求對(duì)他所負(fù)責(zé)的轄區(qū)的每條街至少走一次，問(wèn)如何選取路程最短的路線？國(guó)際上稱之為中國(guó)郵遞員問(wèn)題。目前十九頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)其它相關(guān)問(wèn)題2.5最短路問(wèn)題（SPP－shortestpathproblem）一名貨柜車司機(jī)奉命在最短的時(shí)間內(nèi)將一車貨物從甲地運(yùn)往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯(cuò)，因此有多種行車路線，這名司機(jī)應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運(yùn)行速度是恒定的，那么這一問(wèn)題相當(dāng)于需要找到一條從甲地到乙地的最短路。目前二十頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)2.6旅行商問(wèn)題（TSP－travelingsalesmanproblem）一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他（她）設(shè)計(jì)一條最短的旅行路線（從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市恰好一次，最后返回駐地）？這一問(wèn)題的研究歷史十分悠久，通常稱之為旅行商問(wèn)題。2.7指派問(wèn)題（assignmentproblem）一家公司經(jīng)理準(zhǔn)備安排名員工去完成項(xiàng)任務(wù)，每人一項(xiàng)。由于各員工的特點(diǎn)不同，不同的員工去完成同一項(xiàng)任務(wù)時(shí)所獲得的回報(bào)是不同的。如何分配工作方案可以使總回報(bào)最大？目前二十一頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)2.8運(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)輸成本最低?目前二十二頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)例1我國(guó)北京、上海等十城市間的鐵路交通圖北京天津濟(jì)南青島鄭州徐州連云港南京上海..........武漢一、圖論的基本概念目前二十三頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)例28種化學(xué)品，某些藥品不能存放在同一個(gè)庫(kù)房里，求庫(kù)房最少。圖示：目前二十四頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)例3有5個(gè)球隊(duì)，他們之間的比賽情況，可以用圖表示出來(lái)。。。。。。目前二十五頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)共同特征：用點(diǎn)與點(diǎn)的聯(lián)線構(gòu)成圖，去反映實(shí)際生活中某些對(duì)象之間的特定關(guān)系。點(diǎn)：代表研究對(duì)象；聯(lián)線：兩個(gè)對(duì)象之間的特定關(guān)系；目前二十六頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)1)圖的概念

定義

一個(gè)圖G是指一個(gè)二元組(V(G),E(G))，其中:其中元素稱為圖G的頂點(diǎn).組成的集合，即稱為邊集,其中元素稱為邊.

定義圖G的階是指圖的頂點(diǎn)數(shù)|V(G)|,用來(lái)表示；圖的邊的數(shù)目|E(G)|用來(lái)表示.也用來(lái)表示邊是非空有限集，稱為頂點(diǎn)集，1)2)

E(G)是頂點(diǎn)集V(G)中的無(wú)序或有序的元素偶對(duì)表示圖，簡(jiǎn)記用目前二十七頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)

定義若一個(gè)圖的頂點(diǎn)集和邊集都是有限集，則稱其為有限圖.只有一個(gè)頂點(diǎn)的圖稱為平凡圖，其他的所有圖都稱為非平凡圖.目前二十八頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)一個(gè)圖會(huì)有許多外形不同的圖解,下面兩個(gè)圖表示同一個(gè)圖G=(V,E)的圖解.其中V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4}.

今后將不計(jì)較這種外形上的差別,而用一個(gè)容易理解的、確定的圖解去表示一個(gè)圖.目前二十九頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)實(shí)際生活中，有許多關(guān)系具有不對(duì)稱性，可以用一條帶箭頭的聯(lián)線表示。。。。。。例3（非對(duì)稱關(guān)系圖）有5個(gè)球隊(duì)，他們之間的比賽情況，可以用圖表示出來(lái)。目前三十頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)

定義若圖G中的邊均為有序偶對(duì),稱G為有向圖邊為無(wú)向邊，稱e連接和，頂點(diǎn)和稱稱邊為有向邊或弧。稱為e的尾，稱為e的頭.若圖G中的邊均為無(wú)序偶對(duì)，稱G為無(wú)向圖.為e的端點(diǎn).既有無(wú)向邊又有有向邊的圖稱為混合圖.目前三十一頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)

常用術(shù)語(yǔ)1)邊和它的兩端點(diǎn)稱為互相關(guān)聯(lián).2)與同一條邊關(guān)聯(lián)的兩個(gè)端點(diǎn)稱為相鄰的頂點(diǎn)，與同一個(gè)頂點(diǎn)點(diǎn)關(guān)聯(lián)的兩條邊稱為相鄰的邊.3)端點(diǎn)重合為一點(diǎn)的邊稱為環(huán)，4)若一對(duì)頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊稱為重邊．目前三十二頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)下圖3.3給出了一個(gè)簡(jiǎn)單圖。圖3.35)既沒(méi)有環(huán)也沒(méi)有重邊的圖，稱為簡(jiǎn)單圖．目前三十三頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)6）任意兩點(diǎn)均相鄰的簡(jiǎn)單圖稱之為完全圖。n個(gè)點(diǎn)的完全圖記為Kn，圖3.4中給出的分別是K2，K3，K4。圖3.4目前三十四頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)

定理3.2完全圖Kn的邊數(shù)為

m==n(n1)/2。如果簡(jiǎn)單圖G的每個(gè)頂點(diǎn)都有相同的度數(shù)k，則稱G為k次正則圖（或k-正則圖）。

目前三十五頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)注意：完全圖是n-1正則圖完全圖的每個(gè)結(jié)點(diǎn)都與其它n-1個(gè)結(jié)點(diǎn)相鄰接,即與n-1條邊相關(guān)聯(lián),所以是n-1正則圖,反之正則圖不一定是完全圖。1、完全圖：2、正則圖：是3正則圖。完全圖不是完全圖目前三十六頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)2)賦權(quán)圖與子圖

定義若圖的每一條邊e都賦以一個(gè)實(shí)數(shù)w(e)，稱w(e)為邊e的權(quán)，G連同邊上的權(quán)稱為賦權(quán)圖.

定義設(shè)和是兩個(gè)圖.1)若,稱是的一個(gè)子圖,記2)若，，則稱是的生成子圖.

目前三十七頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)3)若，且，以為頂點(diǎn)集，以兩端點(diǎn)均在中的邊的全體為邊集的圖的子圖，稱4)若，且，以為邊集，以的端點(diǎn)集為頂點(diǎn)集的圖的子圖，稱為的由導(dǎo)出的邊導(dǎo)出的子圖，記為.為的由導(dǎo)出的子圖，記為.目前三十八頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)圖的頂點(diǎn)度定義1)在無(wú)向圖G中，與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目(環(huán)算兩次),稱為頂點(diǎn)v的度或次數(shù)，記為d(v)或dG(v).稱度為奇數(shù)的頂點(diǎn)為奇點(diǎn)，度為偶數(shù)的頂點(diǎn)為偶點(diǎn).2)在有向圖中，從頂點(diǎn)v引出的邊的數(shù)目稱為頂點(diǎn)

v的出度，記為d+(v)，從頂點(diǎn)v引入的邊的數(shù)目稱為

v的入度，記為d-(v).稱d(v)=d+(v)+d-(v)為頂點(diǎn)v的

度或次數(shù)．目前三十九頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)

定理3.1（圖論第一定理：握手定理）Euler提出設(shè)G是具有n個(gè)頂點(diǎn)m條邊的圖，則頂點(diǎn)度數(shù)的總和等于邊數(shù)的2倍，即

推論3.1：圖G中度數(shù)為奇的點(diǎn)的個(gè)數(shù)為偶數(shù)。目前四十頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)

例3.4請(qǐng)說(shuō)明：在任意一次集會(huì)中和奇數(shù)個(gè)人握手的人的個(gè)數(shù)為偶數(shù)個(gè)。

目前四十一頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)給定一個(gè)圖：一個(gè)點(diǎn)、邊的交錯(cuò)序列如果滿足則稱為一條聯(lián)結(jié)和的鏈記為稱為鏈的中間點(diǎn)。目前四十二頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)鏈中，若,則稱之為一個(gè)圈鏈中，點(diǎn)均不同，稱之為初等鏈鏈中，均不同，稱之為初等圈。若鏈（圈）中含的邊均不相同，稱之為簡(jiǎn)單（鏈）圈或跡目前四十三頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)是一條簡(jiǎn)單鏈，不是初等鏈?zhǔn)且粭l初等鏈不存在是簡(jiǎn)單圈，不是初等圈目前四十四頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)路和連通（1）若途徑W的頂點(diǎn)和邊均互不相同，則稱W為路或路徑.一條起點(diǎn)為,終點(diǎn)為的路稱為路記為（2）若在圖G中存在(u,v)路，則稱頂點(diǎn)u和v在圖G中連通.（3）若在圖G中頂點(diǎn)u和v是連通的，則頂點(diǎn)u和v之之間的距離d(u,v)是指圖G中最短(u,v)路的長(zhǎng)；若沒(méi)沒(méi)有路連接u和v，則定義為無(wú)窮大.目前四十五頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)（4）圖G中任意兩點(diǎn)皆連通的圖稱為連通圖．

（5）對(duì)于有向圖G，若，且有類似地，可定義有向跡，有向路和有向圈.頭和尾，則稱W為有向途徑.例在右圖中：路或路徑：圈或回路：目前四十六頁(yè)\總數(shù)五十頁(yè)\編于二十一點(diǎn)

例一擺渡人欲將