圖的基本概念演示文稿

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

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

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

定義

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

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

E(G)是頂點集V(G)中的無序或有序的元素偶對表示圖，簡記用目前二十七頁\總數五十頁\編于二十一點

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

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

定義若圖G中的邊均為有序偶對,稱G為有向圖邊為無向邊，稱e連接和，頂點和稱稱邊為有向邊或弧。稱為e的尾，稱為e的頭.若圖G中的邊均為無序偶對，稱G為無向圖.為e的端點.既有無向邊又有有向邊的圖稱為混合圖.目前三十一頁\總數五十頁\編于二十一點

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

定理3.2完全圖Kn的邊數為

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

目前三十五頁\總數五十頁\編于二十一點注意：完全圖是n-1正則圖完全圖的每個結點都與其它n-1個結點相鄰接,即與n-1條邊相關聯,所以是n-1正則圖,反之正則圖不一定是完全圖。1、完全圖：2、正則圖：是3正則圖。完全圖不是完全圖目前三十六頁\總數五十頁\編于二十一點2)賦權圖與子圖

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

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

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

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

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

度或次數．目前三十九頁\總數五十頁\編于二十一點

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

推論3.1：圖G中度數為奇的點的個數為偶數。目前四十頁\總數五十頁\編于二十一點

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

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

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

例一擺渡人欲將