圖的基本概念演示文稿

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

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

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

定義

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

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

E(G)是頂點集V(G)中的無序或有序的元素偶對表示圖，簡記用當前第27頁\共有50頁\編于星期六\23點

定義若一個圖的頂點集和邊集都是有限集，則稱其為有限圖.只有一個頂點的圖稱為平凡圖，其他的所有圖都稱為非平凡圖.當前第28頁\共有50頁\編于星期六\23點一個圖會有許多外形不同的圖解,下面兩個圖表示同一個圖G=(V,E)的圖解.其中V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4}.

今后將不計較這種外形上的差別,而用一個容易理解的、確定的圖解去表示一個圖.當前第29頁\共有50頁\編于星期六\23點實際生活中，有許多關(guān)系具有不對稱性，可以用一條帶箭頭的聯(lián)線表示。。。。。。例3（非對稱關(guān)系圖）有5個球隊，他們之間的比賽情況，可以用圖表示出來。當前第30頁\共有50頁\編于星期六\23點

定義若圖G中的邊均為有序偶對,稱G為有向圖邊為無向邊，稱e連接和，頂點和稱稱邊為有向邊或弧。稱為e的尾，稱為e的頭.若圖G中的邊均為無序偶對，稱G為無向圖.為e的端點.既有無向邊又有有向邊的圖稱為混合圖.當前第31頁\共有50頁\編于星期六\23點

常用術(shù)語1)邊和它的兩端點稱為互相關(guān)聯(lián).2)與同一條邊關(guān)聯(lián)的兩個端點稱為相鄰的頂點，與同一個頂點點關(guān)聯(lián)的兩條邊稱為相鄰的邊.3)端點重合為一點的邊稱為環(huán)，4)若一對頂點之間有兩條以上的邊聯(lián)結(jié)，則這些邊稱為重邊．當前第32頁\共有50頁\編于星期六\23點下圖3.3給出了一個簡單圖。圖3.35)既沒有環(huán)也沒有重邊的圖，稱為簡單圖．當前第33頁\共有50頁\編于星期六\23點6）任意兩點均相鄰的簡單圖稱之為完全圖。n個點的完全圖記為Kn，圖3.4中給出的分別是K2，K3，K4。圖3.4當前第34頁\共有50頁\編于星期六\23點

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

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

當前第35頁\共有50頁\編于星期六\23點注意：完全圖是n-1正則圖完全圖的每個結(jié)點都與其它n-1個結(jié)點相鄰接,即與n-1條邊相關(guān)聯(lián),所以是n-1正則圖,反之正則圖不一定是完全圖。1、完全圖：2、正則圖：是3正則圖。完全圖不是完全圖當前第36頁\共有50頁\編于星期六\23點2)賦權(quán)圖與子圖

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

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

當前第37頁\共有50頁\編于星期六\23點3)若，且，以為頂點集，以兩端點均在中的邊的全體為邊集的圖的子圖，稱4)若，且，以為邊集，以的端點集為頂點集的圖的子圖，稱為的由導出的邊導出的子圖，記為.為的由導出的子圖，記為.當前第38頁\共有50頁\編于星期六\23點圖的頂點度定義1)在無向圖G中，與頂點v關(guān)聯(lián)的邊的數(shù)目(環(huán)算兩次),稱為頂點v的度或次數(shù)，記為d(v)或dG(v).稱度為奇數(shù)的頂點為奇點，度為偶數(shù)的頂點為偶點.2)在有向圖中，從頂點v引出的邊的數(shù)目稱為頂點

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

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

度或次數(shù)．當前第39頁\共有50頁\編于星期六\23點

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

推論3.1：圖G中度數(shù)為奇的點的個數(shù)為偶數(shù)。當前第40頁\共有50頁\編于星期六\23點

例3.4請說明：在任意一次集會中和奇數(shù)個人握手的人的個數(shù)為偶數(shù)個。

當前第41頁\共有50頁\編于星期六\23點給定一個圖：一個點、邊的交錯序列如果滿足則稱為一條聯(lián)結(jié)和的鏈記為稱為鏈的中間點。當前第42頁\共有50頁\編于星期六\23點鏈中，若,則稱之為一個圈鏈中，點均不同，稱之為初等鏈鏈中，均不同，稱之為初等圈。若鏈（圈）中含的邊均不相同，稱之為簡單（鏈）圈或跡當前第43頁\共有50頁\編于星期六\23點是一條簡單鏈，不是初等鏈是一條初等鏈不存在是簡單圈，不是初等圈當前第44頁\共有50頁\編于星期六\23點路和連通（1）若途徑W的頂點和邊均互不相同，則稱W為路或路徑.一條起點為,終點為的路稱為路記為（2）若在圖G中存在(u,v)路，則稱頂點u和v在圖G中連通.（3）若在圖G中頂點u和v是連通的，則頂點u和v之之間的距離d(u,v)是指圖G中最短(u,v)路的長；若沒沒有路連接u和v，則定義為無窮大.當前第45頁\共有50頁\編于星期六\23點（4）圖G中任意兩點皆連通的圖稱為連通圖．

（5）對于有向圖G，若，且有類似地，可定義有向跡，有向路和有向圈.頭和尾，則稱W為有向途徑.例在右圖中：路或路徑：圈或回路：當前第46頁\共有50頁\編于星期六\23點

例一