數(shù)學(xué)建模——圖論

1、數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 沈陽(yáng)工業(yè)大學(xué)理學(xué)院杜洪波杜洪波hb_2015年8月數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 一、涉及圖論的歷年數(shù)學(xué)建模題目一、涉及圖論的歷年數(shù)學(xué)建模題目 二、圖論簡(jiǎn)介二、圖論簡(jiǎn)介 三、圖論的基本概念三、圖論的基本概念 四、最短路問題及其算法四、最短路問題及其算法 五、最小生成樹及其算法五、最小生成樹及其算法

2、六、幾個(gè)可以用圖論解決的范例六、幾個(gè)可以用圖論解決的范例數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling1、93B 足球隊(duì)排名次2、94A 逢山開路3、94B 鎖具裝箱問題4、95B 天車與冶煉爐的作業(yè)調(diào)度5、97B 截?cái)嗲懈睿鹤疃搪纷疃搪?、98B 災(zāi)情巡視：最小生成樹、最小生成樹、Hamilton圈、旅行商問題圈、旅行商問題數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Mod

3、eling7、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) 數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling13、08C地面搜索14、08DNBA賽程的分析與評(píng)價(jià)數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 現(xiàn)實(shí)生活中許多問題都可歸

4、結(jié)為由點(diǎn)和線組成的現(xiàn)實(shí)生活中許多問題都可歸結(jié)為由點(diǎn)和線組成的圖形的問題，例如，鐵路交通圖，公路交通圖，市區(qū)圖形的問題，例如，鐵路交通圖，公路交通圖，市區(qū)交通圖，自來水管網(wǎng)系統(tǒng)，甚至電路圖在研究某些問交通圖，自來水管網(wǎng)系統(tǒng)，甚至電路圖在研究某些問題時(shí)也可簡(jiǎn)化為由點(diǎn)和線組成的圖形。題時(shí)也可簡(jiǎn)化為由點(diǎn)和線組成的圖形。 如果我們用點(diǎn)表示這些具體事物，用連接兩點(diǎn)如果我們用點(diǎn)表示這些具體事物，用連接兩點(diǎn)的線段（直的或曲的）表示兩個(gè)事物的特定的聯(lián)系，的線段（直的或曲的）表示兩個(gè)事物的特定的聯(lián)系，就得到了描述這個(gè)就得到了描述這個(gè)“圖圖”的幾何形象。的幾何形象。 圖論就是研究這些由點(diǎn)和線組成的圖形的問題。圖論就

5、是研究這些由點(diǎn)和線組成的圖形的問題。數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 圖論是運(yùn)籌學(xué)的一個(gè)經(jīng)典和重要的分支，它起源于18世紀(jì)歐拉（Euler）對(duì)七橋問題的抽象和論證。 1936年，匈牙利數(shù)學(xué)家柯尼希（Knig）出版了圖論的第一部專著有限圖與無(wú)限圖理論，豎立了圖論發(fā)展的第一座里程碑。數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling2.1 七橋問題（Eul

6、er） 18世紀(jì)東普魯士有一個(gè)城市稱為哥尼斯堡，它位于普雷格爾河畔，河中有兩個(gè)小島，通過七座橋彼此相聯(lián)（如圖2.1）。當(dāng)時(shí)有人提出： 能否從某個(gè)地點(diǎn)出發(fā)經(jīng)過每個(gè)橋一次且僅一次然后返能否從某個(gè)地點(diǎn)出發(fā)經(jīng)過每個(gè)橋一次且僅一次然后返回出發(fā)點(diǎn)？回出發(fā)點(diǎn)？數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical ModelingD DA AB BC CA AB BC CD Dv建模：點(diǎn)陸地 島嶼 邊橋Euler的做法：圖 2.1圖 2.2數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECH

7、NOLOGYGraph Theory in Mathematical Modeling2.2 Hamilton 周游世界問題 1859年 Hamilton 提出這樣一個(gè)問題：一個(gè)正十二面體有20個(gè)頂點(diǎn)，它們代表世界上20個(gè)重要城市。正十二面體的每個(gè)面均為五邊形，若兩個(gè)頂點(diǎn)之間有邊相連，則表示相應(yīng)的城市之間有航線相通。 Hamilton 提出 “能否從某城市出發(fā)經(jīng)過每個(gè)城能否從某城市出發(fā)經(jīng)過每個(gè)城市一次且僅一次然后返回出發(fā)點(diǎn)？市一次且僅一次然后返回出發(fā)點(diǎn)？”數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathemati

8、cal Modeling2.3 四色問題（猜想） 四色問題又稱四色猜想、四色定理，是世界近代三大數(shù)學(xué)難題之一。 地圖四色定理(Four color theorem)最先是由一位叫古德里（Francis Guthrie）的英國(guó)大學(xué)生提出來的。 德摩根（Augustus De Morgan）1852年10月23日致哈密頓的一封信提供了有關(guān)四色定理來源的最原始的記載。 數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling四色問題的內(nèi)容是：“任何一張地圖只用四種顏色就任何一張地圖只用四種顏色

9、就能使具有共同邊界的國(guó)家著上不同的顏色能使具有共同邊界的國(guó)家著上不同的顏色?！庇脭?shù)學(xué)語(yǔ)言表示，即“將平面任意地細(xì)分為不相重疊的區(qū)域，每一個(gè)區(qū)域總可以用1，2，3，4這四個(gè)數(shù)字之一來標(biāo)記，而不會(huì)使相鄰的兩個(gè)區(qū)域得到相同的數(shù)字?！?1890年希五德（Heawood）指出“4換為5”猜想成立。1976年美國(guó)數(shù)學(xué)家阿佩爾（K.Appel）與哈肯（W.Haken）在三臺(tái)百萬(wàn)次的電子計(jì)算機(jī)上花了1200小時(shí)證明了猜想成立。猜想成為定理。數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling2.4

10、中國(guó)郵路問題或中國(guó)郵遞員問題（CPPChinese Postman Problem） 1962年中國(guó)數(shù)學(xué)家管梅谷提出：一個(gè)郵遞員從郵局出發(fā)遞送郵件，要求對(duì)他所負(fù)責(zé)的轄區(qū)的每條街至少走一次，問如何選取路程最短的路線？國(guó)際上稱之為中國(guó)郵遞員問題中國(guó)郵遞員問題。 該問題可用專門的算法來求解。數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling2.5 最短路問題（SPPshortest path problem） 一名貨柜車司機(jī)奉命在最短的時(shí)間內(nèi)將一車貨物從甲地運(yùn)往乙地。從甲地到乙地的公路網(wǎng)

11、縱橫交錯(cuò)，因此有多種行車路線，這名司機(jī)應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運(yùn)行速度是恒定的，那么這一問題相當(dāng)于需要找到一條從甲地到乙地的最短路。數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling2.6旅行商問題（TSPtraveling salesman problem） 一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他（她）設(shè)計(jì)一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個(gè)城市恰好一次，最后返回駐地）？這一問題的研究歷史十分悠久，通常稱之為旅行商問題。 2.7 指派問題（assignment p

12、roblem） 一家公司經(jīng)理準(zhǔn)備安排名員工去完成項(xiàng)任務(wù)，每人一項(xiàng)。由于各員工的特點(diǎn)不同，不同的員工去完成同一項(xiàng)任務(wù)時(shí)所獲得的回報(bào)是不同的。如何分配工作方案可以使總回報(bào)最大？數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling2.8 運(yùn)輸問題（transportation problem） 某種原材料有個(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)輸成本最低?數(shù)數(shù) 學(xué)

13、學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 3.1 圖的定義 3.2 圖的分類 3.3 圖的同構(gòu) 3.4 子圖 3.5 圖的運(yùn)算 3.6 圖的代數(shù)表示及特征 數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 定義定義3.1 稱數(shù)學(xué)結(jié)構(gòu)稱數(shù)學(xué)結(jié)構(gòu)G = V(G), E(G), G 為一個(gè)為一個(gè)圖圖，其中其中V(G) = v1, v2, , vn 稱為圖稱為圖 G的的頂點(diǎn)

14、集頂點(diǎn)集(vertex set)或或節(jié)點(diǎn)集節(jié)點(diǎn)集(node set)，V(G) 中的每一個(gè)元素中的每一個(gè)元素 vi（i = 1, 2, , n）稱為該圖的一個(gè)）稱為該圖的一個(gè)頂點(diǎn)頂點(diǎn)(vertex)或或結(jié)點(diǎn)結(jié)點(diǎn)(node); E(G) = e1, e2, , em 稱為圖稱為圖 G 的的邊集邊集（edge set），），E(G) 中的每一中的每一個(gè)元素個(gè)元素 ek（即（即V(G) 中某兩個(gè)元素中某兩個(gè)元素vi, vj 的無(wú)序?qū)Γ┯洖榈臒o(wú)序?qū)Γ┯洖?ek = (vi, vj) 或或 ek = vivj = vjvi（k = 1, 2, , m），被稱為該圖的），被稱為該圖的一條從一條從 vi到到

15、 vj的的邊邊(edge)；上級(jí)目錄數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical ModelingG是從 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) 中的邊，則可用圖形將圖表示出來，稱之為圖的圖形。我們常用圖的圖形代表圖本身。數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathemati

16、cal Modeling 定義定義3.2 設(shè)e = uv 為圖 G 的一條邊，我們稱 u、v 是 e 的端點(diǎn)端點(diǎn)，u 與 v 相鄰相鄰，邊 e 與點(diǎn) u（或v）相關(guān)聯(lián)關(guān)聯(lián)；稱 u 是 e 的起點(diǎn)，v 是 e 的終點(diǎn)。若兩條邊 e1 與 e2 有共同的端點(diǎn)，則稱邊 e1與 e2 相鄰； 稱有相同起點(diǎn)和終點(diǎn)的兩條邊為重邊重邊； 稱兩端點(diǎn)均相同的邊為環(huán)環(huán)； 稱不與任何邊相關(guān)聯(lián)的點(diǎn)為孤立點(diǎn)孤立點(diǎn)。 數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling簡(jiǎn)單圖簡(jiǎn)單圖平凡圖平凡圖非非簡(jiǎn)單簡(jiǎn)單圖圖

17、點(diǎn)集與邊集均為有限集合的圖稱為有限圖有限圖，一般我們只討論有限圖。只有一個(gè)頂點(diǎn)而無(wú)邊的圖稱為平凡圖平凡圖。邊集為空的圖稱為空?qǐng)D空?qǐng)D。 無(wú)環(huán)且無(wú)重邊的圖稱之為簡(jiǎn)單圖簡(jiǎn)單圖。其他所有的圖都稱為復(fù)合圖。復(fù)合圖。數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling例3.1 設(shè) V = v1, v2, v3, v4，E = e1, e2, e3, e4, e5，：EVV 定義為(e1) = v1v2，(e2) = v2v3，(e3) = v2v3，(e4) = v3v4，(e5) = v4v4

18、，則G = V, E 是一個(gè)圖，其圖形如圖3.1所示。圖 3.1數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling例3.2 設(shè) V = v1, v2, v3, v4，E = v1v2, v1v2, v2v3，則G = V, E 是一個(gè)圖，其圖形如圖3.2所示。圖 3.2數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling例 3.1 和例 3.2 都不是簡(jiǎn)單圖，因?yàn)槔?.1

19、 中既含重邊（e2 與 e3）又含環(huán)（e5），而例 3.2 中含重邊（v1v2）。下圖3.3給出了一個(gè)簡(jiǎn)單圖。圖 3.3數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 任意兩點(diǎn)均相鄰的簡(jiǎn)單圖稱之為任意兩點(diǎn)均相鄰的簡(jiǎn)單圖稱之為完全圖完全圖。 n 個(gè)點(diǎn)的完全圖記為個(gè)點(diǎn)的完全圖記為 Kn，圖，圖 3.4 中給出的分別是中給出的分別是 K2，K3，K4。圖 3.4數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in M

20、athematical Modeling 如果圖如果圖 G 的各條邊都被賦予了方向，則稱圖的各條邊都被賦予了方向，則稱圖 G 為為有向圖有向圖。如。如果圖果圖 G 的每條邊的每條邊 e 都附有一個(gè)實(shí)數(shù)都附有一個(gè)實(shí)數(shù) w(e)，則稱圖，則稱圖 G 為為賦權(quán)圖賦權(quán)圖，實(shí)，實(shí)數(shù)數(shù) w(e) 稱為邊稱為邊 e 的權(quán)（值）。的權(quán)（值）。 圖 3.5 和圖 3.6 分別給出了有向圖和賦權(quán)圖的例子；而圖 3.7 則給出了有向賦權(quán)圖的例子。圖 3.5：有向圖數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Mod

21、eling圖 3.6：賦權(quán)圖圖 3.7：有向賦權(quán)圖數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 設(shè)設(shè) v 為圖為圖 G 的點(diǎn)，的點(diǎn)，G 中與中與 v 相關(guān)聯(lián)的邊的條數(shù)（環(huán)計(jì)相關(guān)聯(lián)的邊的條數(shù)（環(huán)計(jì)算兩次）稱為點(diǎn)算兩次）稱為點(diǎn) v 的的度度，記為，記為dG(v)，簡(jiǎn)記為，簡(jiǎn)記為 d(v)。v1v2v3v4v5例例3.3圖圖3.8中中 d (v1) = 5 d (v2) = 4 d (v3) = 3 d (v4) = 0 d (v5) = 2注：該圖中各點(diǎn)的度數(shù)注：該圖中各點(diǎn)的度數(shù)

22、 之和等于之和等于14，恰好，恰好 是邊數(shù)是邊數(shù)7的的兩兩倍。倍。圖圖3.8數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 定理定理 3.1（圖論第一定理：握手定理握手定理） Euler提出 設(shè) G 是具有 n 個(gè)頂點(diǎn) m 條邊的圖，則頂點(diǎn)度數(shù)的總和等于邊數(shù)的 2 倍，即 證明：因圖 G 的任一條邊均有兩個(gè)端點(diǎn) (可以相同)，在計(jì)算度時(shí)恰被計(jì)算兩次 (每個(gè)端點(diǎn)各被計(jì)算了一次)，所以各點(diǎn)的度數(shù)之和恰好為邊數(shù)的兩倍，即定理成立。 推論推論3.1：圖圖G中度數(shù)為奇的點(diǎn)的個(gè)數(shù)為偶數(shù)。中

23、度數(shù)為奇的點(diǎn)的個(gè)數(shù)為偶數(shù)。mvdnii2)(1數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 例例3.4 3.4 證明在任意一次集會(huì)中和奇數(shù)個(gè)人握手的人的證明在任意一次集會(huì)中和奇數(shù)個(gè)人握手的人的個(gè)數(shù)為偶數(shù)個(gè)。個(gè)數(shù)為偶數(shù)個(gè)。 證明證明: :將集會(huì)中的人作為點(diǎn)，若兩個(gè)人握手則對(duì)應(yīng)的將集會(huì)中的人作為點(diǎn)，若兩個(gè)人握手則對(duì)應(yīng)的點(diǎn)聯(lián)線，則得簡(jiǎn)單圖點(diǎn)聯(lián)線，則得簡(jiǎn)單圖G。這樣。這樣G中點(diǎn)中點(diǎn)v的度對(duì)應(yīng)于集會(huì)中與的度對(duì)應(yīng)于集會(huì)中與v握手的人的個(gè)數(shù)。于是，問題轉(zhuǎn)化為證明握手的人的個(gè)數(shù)。于是，問題轉(zhuǎn)

24、化為證明“圖圖G中度數(shù)中度數(shù)為奇的點(diǎn)的個(gè)數(shù)為偶數(shù)為奇的點(diǎn)的個(gè)數(shù)為偶數(shù)”，這正是推論，這正是推論3.13.1的結(jié)論。的結(jié)論。數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 定理定理 3.2 完全圖完全圖 Kn 的邊數(shù)為的邊數(shù)為 m = n(n 1)/2。 如果簡(jiǎn)單圖如果簡(jiǎn)單圖 G 的每個(gè)頂點(diǎn)都有相同的度數(shù)的每個(gè)頂點(diǎn)都有相同的度數(shù)k，則稱，則稱 G 為為 k 次正則圖次正則圖（或（或k -正則圖正則圖）。）。 完全圖完全圖 Kn 一定是一定是 n-1 次正則圖，如前圖次正則圖，如前

25、圖3.4。 相關(guān)術(shù)語(yǔ)和記號(hào)：相關(guān)術(shù)語(yǔ)和記號(hào)： ：圖：圖G的頂點(diǎn)的最小度的頂點(diǎn)的最小度 ：圖：圖G的頂點(diǎn)的最大度的頂點(diǎn)的最大度 奇奇(偶偶)點(diǎn)點(diǎn): 奇奇(偶偶)數(shù)度的頂點(diǎn)數(shù)度的頂點(diǎn)( )G( )G數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical ModelingA 按邊的方向分類按邊的方向分類有向圖有向圖與與無(wú)向圖無(wú)向圖:邊有方向的圖邊有方向的圖,叫有向圖；邊無(wú)方向叫有向圖；邊無(wú)方向的圖叫無(wú)向圖。的圖叫無(wú)向圖。起點(diǎn)和終點(diǎn)：在有向圖中，有向邊起點(diǎn)和終點(diǎn)：在有向圖中，有向邊e = vivj中中vi稱為起

26、稱為起點(diǎn)，點(diǎn)， vj稱為終點(diǎn)。稱為終點(diǎn)。數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical ModelingB 按邊的種類分類按邊的種類分類簡(jiǎn)單圖簡(jiǎn)單圖與與多重圖多重圖:不含環(huán)與多重邊的圖叫簡(jiǎn)單圖；含多重不含環(huán)與多重邊的圖叫簡(jiǎn)單圖；含多重邊的圖叫多重圖。邊的圖叫多重圖。賦（有）權(quán)圖賦（有）權(quán)圖與與無(wú)權(quán)圖無(wú)權(quán)圖: 有時(shí)在一個(gè)圖中邊的旁邊可以有時(shí)在一個(gè)圖中邊的旁邊可以附加數(shù)字以刻劃此邊的某些數(shù)量特征，叫做邊的權(quán)，此邊附加數(shù)字以刻劃此邊的某些數(shù)量特征，叫做邊的權(quán)，此邊叫做有權(quán)邊，具有有權(quán)邊的圖叫有權(quán)圖或賦

27、權(quán)圖，無(wú)有權(quán)叫做有權(quán)邊，具有有權(quán)邊的圖叫有權(quán)圖或賦權(quán)圖，無(wú)有權(quán)邊的圖叫無(wú)權(quán)圖。邊的圖叫無(wú)權(quán)圖。數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical ModelingC 按結(jié)點(diǎn)集與邊集的按結(jié)點(diǎn)集與邊集的“階階”分類分類1、有限圖、有限圖與與無(wú)限圖無(wú)限圖：V 與與 E 為有限集合的圖叫有限圖，為有限集合的圖叫有限圖，否則叫無(wú)限圖。否則叫無(wú)限圖。2、(n,m)圖圖：有：有 n 個(gè)結(jié)點(diǎn)與個(gè)結(jié)點(diǎn)與 m 條邊的圖。條邊的圖。 零圖零圖:即即(n,0)圖圖;平凡圖平凡圖:即即(1,0)圖。圖。3、完全圖、完全圖:任

28、意兩個(gè)結(jié)點(diǎn)都相鄰接的圖。任意兩個(gè)結(jié)點(diǎn)都相鄰接的圖。 共共n(n-1)/2 條邊，是條邊，是(n,n(n-1)/2)圖。圖。4、K-正則圖正則圖:每個(gè)結(jié)點(diǎn)都與每個(gè)結(jié)點(diǎn)都與K條邊相關(guān)聯(lián)。條邊相關(guān)聯(lián)。數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling完全圖的每個(gè)結(jié)點(diǎn)都與其它完全圖的每個(gè)結(jié)點(diǎn)都與其它 n-1 個(gè)結(jié)點(diǎn)相鄰接個(gè)結(jié)點(diǎn)相鄰接,即與即與n-1條條邊相關(guān)聯(lián)邊相關(guān)聯(lián),所以是所以是n-1正則圖正則圖,反之正則圖不一定是完全圖。反之正則圖不一定是完全圖。1、完全圖：、完全圖： 2、正則圖：、

29、正則圖：是是3正則圖。正則圖。 完全圖完全圖 不是完全圖不是完全圖數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 定義定義3.33.3 給定兩個(gè)圖給定兩個(gè)圖G=V,E, ,G =V ,E , ,若存在一一若存在一一映射映射f:VV ，使對(duì)任意使對(duì)任意a,b V, ,有有 (a,b) E (f(a),f(b) E , , 并且并且(a,b)與與(f(a),f(b)有相同重?cái)?shù)有相同重?cái)?shù), ,則稱則稱G與與G 同構(gòu)同構(gòu), ,記為記為G G . . 說明：說明： (1) (1) 兩個(gè)同

30、構(gòu)的圖均有相同的結(jié)構(gòu)，沒有本質(zhì)上的差兩個(gè)同構(gòu)的圖均有相同的結(jié)構(gòu)，沒有本質(zhì)上的差異異, , 差異只是頂點(diǎn)和邊的名稱不同。差異只是頂點(diǎn)和邊的名稱不同。 （2 2）圖同構(gòu)的幾個(gè)）圖同構(gòu)的幾個(gè)必要必要條件：條件： 頂點(diǎn)數(shù)相同；頂點(diǎn)數(shù)相同； 邊邊數(shù)相同；數(shù)相同； 度數(shù)相等的頂點(diǎn)個(gè)數(shù)相同。度數(shù)相等的頂點(diǎn)個(gè)數(shù)相同。數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling （3）不難證明：）不難證明：圖的同構(gòu)關(guān)系是一個(gè)等價(jià)關(guān)系圖的同構(gòu)關(guān)系是一個(gè)等價(jià)關(guān)系。該關(guān)系將所有。該關(guān)系將所有的圖的集合，劃分為一些等

31、價(jià)類，即相互同構(gòu)的圖作成同一個(gè)等價(jià)的圖的集合，劃分為一些等價(jià)類，即相互同構(gòu)的圖作成同一個(gè)等價(jià)類。類。 （4）在圖的圖形表示中我們可以不給圖的點(diǎn)和邊標(biāo)上符號(hào)，稱）在圖的圖形表示中我們可以不給圖的點(diǎn)和邊標(biāo)上符號(hào)，稱這樣的圖為這樣的圖為非標(biāo)定（號(hào)）圖非標(biāo)定（號(hào)）圖，否則稱為，否則稱為標(biāo)定（號(hào)）圖標(biāo)定（號(hào)）圖。非標(biāo)定圖實(shí)。非標(biāo)定圖實(shí)際上是代表一類相互同構(gòu)的圖。際上是代表一類相互同構(gòu)的圖。 不誤解時(shí)我們也不嚴(yán)格區(qū)分標(biāo)定圖與非標(biāo)定圖。不誤解時(shí)我們也不嚴(yán)格區(qū)分標(biāo)定圖與非標(biāo)定圖。 （5）尋求判斷圖同構(gòu)的簡(jiǎn)單且有效的方法仍然是當(dāng)前圖論待解）尋求判斷圖同構(gòu)的簡(jiǎn)單且有效的方法仍然是當(dāng)前圖論待解決的重要問題。決的重要

32、問題。數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling GG HH 1 1a,2a,2b, b, 1 1a,2a,2b,3b,3c,c, 3 3c,4c,4d 4d 4d,5d,5e,6e,6f f1234abcdabcdefGG HH 123456數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling存在結(jié)點(diǎn)數(shù)及每個(gè)結(jié)點(diǎn)對(duì)應(yīng)度都相等的兩個(gè)圖仍然不同構(gòu)存在結(jié)點(diǎn)數(shù)及每個(gè)結(jié)點(diǎn)

33、對(duì)應(yīng)度都相等的兩個(gè)圖仍然不同構(gòu)的情況的情況. .一個(gè)例子如下一個(gè)例子如下:(:(注意注意: :兩個(gè)兩個(gè)4 4度點(diǎn)或鄰接或不相鄰度點(diǎn)或鄰接或不相鄰接接) )GG 數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 定義定義3.4 設(shè)圖設(shè)圖G= V, E, ，G1= V1, E1, 1 （1）若）若 且當(dāng)且當(dāng) 時(shí)，時(shí)， ，則稱，則稱G1是是G的的子圖子圖，有，有時(shí)也稱時(shí)也稱G是是G1的的母圖母圖，記作，記作 。 特別的，若特別的，若V1=V，則，則G1稱為稱為G的的生成子圖生成子圖。

34、當(dāng)當(dāng)G1 G但但G1G時(shí)，記為時(shí)，記為G1 G，且稱，且稱G1是是G的的真子圖真子圖。（2）設(shè)）設(shè) 且且 ，以，以V1為頂點(diǎn)集、兩個(gè)端點(diǎn)都在為頂點(diǎn)集、兩個(gè)端點(diǎn)都在V1中的圖中的圖G的的邊為邊集的圖邊為邊集的圖G的子圖，稱為圖的子圖，稱為圖G的的由由V1導(dǎo)出的子圖導(dǎo)出的子圖，記作，記作GV1。（3）設(shè)）設(shè) 且且 ，以，以E1為邊集、為邊集、 E1的頂點(diǎn)集為頂點(diǎn)集的圖的頂點(diǎn)集為頂點(diǎn)集的圖G的的子圖，稱為圖子圖，稱為圖G的的由由E1導(dǎo)出的子圖導(dǎo)出的子圖，記作，記作GE1。11,VV EE1eE1( )( )ee1VV1V 1EE1E 1GG上級(jí)目錄數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVE

35、RSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling: :由由(1,2),(1,4),(5,1)(1,2),(1,4),(5,1)導(dǎo)出的子圖導(dǎo)出的子圖; ; : :由由(1,2),(3,2),(3,4),(1,4)(1,2),(3,2),(3,4),(1,4)導(dǎo)出的子圖導(dǎo)出的子圖( (也是此也是此4 4點(diǎn)導(dǎo)出的子點(diǎn)導(dǎo)出的子圖圖); ); : :由由1,2,4,51,2,4,5導(dǎo)出的子圖導(dǎo)出的子圖. .12534125412341254數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph

36、Theory in Mathematical Modeling 定理定理3.3 簡(jiǎn)單圖簡(jiǎn)單圖G中所有不同的生成子圖（包括中所有不同的生成子圖（包括G和空和空?qǐng)D）的個(gè)數(shù)是圖）的個(gè)數(shù)是2m個(gè)個(gè), 其中其中m為為G的邊數(shù)。的邊數(shù)。 證明：易知證明：易知 其個(gè)數(shù)其個(gè)數(shù) = 含含0條邊的條邊的+含含1條邊的條邊的+含含m條邊的條邊的0122mmmmmmCCCC數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 設(shè)G1，G2是G的子圖，則 G1和和G2不相交不相交: 指它們無(wú)公共頂點(diǎn)；指它們無(wú)

37、公共頂點(diǎn)； G1和和G2邊不重邊不重: 指它們無(wú)公共邊；指它們無(wú)公共邊； 并圖并圖G1G2:是指其頂點(diǎn)集為是指其頂點(diǎn)集為V(G1)V(G2)，邊集為，邊集為E(G1)E(G2) 的的G的一個(gè)子圖的一個(gè)子圖;如果如果G1和和G2是不相交的，是不相交的，有時(shí)就記其并圖為有時(shí)就記其并圖為G1+G2； 交圖交圖G1G2:類似地定義；類似地定義； 對(duì)稱差對(duì)稱差G1G2: G1G2 = (G1G2) - (G1G2) = (G1-G2)(G2-G1)數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Model

38、ing2 d 4a c e1 f 3 G1b2 d 4 g e 5 i 3 j G2 h c 2 d 4 g a c e 5 b i h1 f 3 G1G2j 2 d 4 c e 3G1G2例例數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling2 d 4a c e1 f 3 G1b2 d 4 g e 5 i 3 j G2 h c2 4a b1 f 3 G1-G254 g h i3 j G2-G1254 g h i j 2a b1 f 3G2G1例例數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENY

39、ANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modelingv1 v2v4 v3 G2v1 v2v4 v3 G1G2u1u1G1例例數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling定義定義3.6 設(shè)設(shè)G1=V, E1, 對(duì)于對(duì)于G2=V, E2,若有若有G=V, E1E2是完全圖是完全圖, ,且且E1E2 = , 則稱則稱G2是是G1的補(bǔ)圖。的補(bǔ)圖。 圖圖G1 圖圖G2 圖圖G數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENY

40、ANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 一個(gè)圖除了可以用圖形表示之外，還可用矩陣來表示。用矩陣表示圖有利于計(jì)算機(jī)處理。 3.6.1 鄰接矩陣鄰接矩陣 3.6.2 關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣上級(jí)目錄數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 定義定義3.7：設(shè)圖：設(shè)圖G = V,E，V = v1,v2, vn，則，則G的鄰的鄰接矩陣是一個(gè)接矩陣是一個(gè)nn矩陣矩陣A(G) = aij (簡(jiǎn)記為簡(jiǎn)記

41、為A)，其中若，其中若vi鄰接鄰接vj，則，則aij=1;否則否則aij=0。 注注: 若若aij取為連接取為連接vi與與vj的邊的數(shù)目的邊的數(shù)目, 則稱則稱A為推廣的鄰為推廣的鄰接矩陣。接矩陣。數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling鄰接矩陣鄰接矩陣 A =0 1 0 01 0 1 00 1 0 10 0 1 10 1 0 01 0 2 00 2 0 10 0 1 1推廣的推廣的鄰接矩陣鄰接矩陣 A =數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF

42、 TECHNOLOGYGraph Theory in Mathematical Modeling1） 對(duì)無(wú)向圖對(duì)無(wú)向圖G，其鄰接矩陣為，其鄰接矩陣為A=aij,其中其中., 0, 1不相鄰與若相鄰與若jijiijvvvva54321543210010000100110110010100110vvvvvAvvvvv數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling2） 對(duì)有向圖對(duì)有向圖G=V,E，其鄰接矩陣為，其鄰接矩陣為A=aij,其中其中.),(, 0,),(, 1EvvEvva

43、jijiij若若432143210100001000001110uuuuAuuuu數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling3） 對(duì)有向賦權(quán)圖對(duì)有向賦權(quán)圖G=V,E,其鄰接矩陣為其鄰接矩陣為A=aij,其中其中,(,),0,(,).ijijijijijwv vEwaijv vE若且為其權(quán)，若43214321040608730uuuuAuuuu對(duì)于無(wú)向賦權(quán)圖的鄰接矩陣可類似定義對(duì)于無(wú)向賦權(quán)圖的鄰接矩陣可類似定義. 數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY

44、 OF TECHNOLOGYGraph Theory in Mathematical Modeling定義定義3.8 無(wú)環(huán)圖無(wú)環(huán)圖G的關(guān)聯(lián)矩陣的關(guān)聯(lián)矩陣B(G) = bij (簡(jiǎn)記為簡(jiǎn)記為B)是一個(gè)是一個(gè)nm矩陣矩陣，當(dāng)點(diǎn)，當(dāng)點(diǎn)vi與邊與邊ej關(guān)聯(lián)時(shí)關(guān)聯(lián)時(shí)bij=1，否則，否則bij=0。v1 e1 e5v2 v5 e6 e7 e2 e4v3 e3 v4例例B = e1 e2 e3 e4 e5 e6 e7v1v2v3v4v500110001001100010011000000111110001數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph

45、Theory in Mathematical Modeling說明：定義中說明：定義中“無(wú)環(huán)無(wú)環(huán)”的條件可去掉，此時(shí)的條件可去掉，此時(shí)bij=點(diǎn)點(diǎn)vi與邊與邊ej關(guān)聯(lián)的次關(guān)聯(lián)的次數(shù)（數(shù)（0, 1, 2(環(huán)環(huán))。e1v4v3v2v1e7e5e4e3e2e61 1 0 0 1 0 11 1 1 0 0 0 0( )0 0 1 1 0 0 10 0 0 1 1 2 0M G性質(zhì)：性質(zhì)：關(guān)聯(lián)矩陣的每列和為關(guān)聯(lián)矩陣的每列和為2 2；其行和為對(duì)應(yīng)頂點(diǎn)的度數(shù)。；其行和為對(duì)應(yīng)頂點(diǎn)的度數(shù)。數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in M

46、athematical Modeling1） 對(duì)無(wú)向圖對(duì)無(wú)向圖G=V,E，其關(guān)聯(lián)矩陣為，其關(guān)聯(lián)矩陣為M=mij,其中其中., 0, 1不關(guān)聯(lián)與若相關(guān)聯(lián)與若jijiijevevm54321543211000001000111100010100011vvvvvMeeeee數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling2） 對(duì)有向圖對(duì)有向圖G=V,E，其關(guān)聯(lián)矩陣為，其關(guān)聯(lián)矩陣為M=mij,其中其中1,1,0,.ijijijijvemveve若是的起點(diǎn)若是的終點(diǎn)若不是的起點(diǎn)與終點(diǎn)432

47、15432111000101100001101101uuuuMeeeee數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 4.1 相關(guān)概念相關(guān)概念 4.2 Dijkstra算法算法 4.3 Floyd算法算法數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 定義定義4.1 給定圖給定圖G =V, E，w= v0e1v1e2ekvk是是G中中點(diǎn)邊交替點(diǎn)邊交替組成組成的

48、的序列序列，其中，其中viV，ei=(vi-1,vi)E，i= 0,1, k，則稱，則稱w為一條從起為一條從起點(diǎn)點(diǎn)v0到終點(diǎn)到終點(diǎn)vk的長(zhǎng)為的長(zhǎng)為k的的通路通路(或或路徑路徑、通道通道、途徑途徑、鏈鏈), 簡(jiǎn)稱簡(jiǎn)稱(v0, vk)通路。通路。 注：對(duì)有向圖，要求注：對(duì)有向圖，要求vi-1和和vi為為ei的始點(diǎn)和終點(diǎn)。的始點(diǎn)和終點(diǎn)。 邊不重復(fù)的通路稱為邊不重復(fù)的通路稱為簡(jiǎn)單通路簡(jiǎn)單通路（或（或跡跡）；）； 除起點(diǎn)與終點(diǎn)可以相同外，任意兩點(diǎn)都不同的通路，稱為除起點(diǎn)與終點(diǎn)可以相同外，任意兩點(diǎn)都不同的通路，稱為基本基本通路通路，基本通路簡(jiǎn)稱為，基本通路簡(jiǎn)稱為路路。 顯然，基本通路必為簡(jiǎn)單通路。顯然，基

49、本通路必為簡(jiǎn)單通路。數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 稱起點(diǎn)與終點(diǎn)相同的通路為稱起點(diǎn)與終點(diǎn)相同的通路為回路回路(或或閉途徑閉途徑) ； 邊不重復(fù)的回路稱為邊不重復(fù)的回路稱為簡(jiǎn)單回路簡(jiǎn)單回路； 起點(diǎn)與終點(diǎn)相同的長(zhǎng)為的基本通路稱為起點(diǎn)與終點(diǎn)相同的長(zhǎng)為的基本通路稱為基本回路基本回路，也，也稱為稱為圈圈。 如不引起混淆（如在簡(jiǎn)單圖中），通路與回路均可用如不引起混淆（如在簡(jiǎn)單圖中），通路與回路均可用點(diǎn)序列來表達(dá)。點(diǎn)序列來表達(dá)。 k(奇奇,偶偶)圈：圈：長(zhǎng)為長(zhǎng)為k (奇奇,偶

50、偶)的圈。的圈。 3圈常稱為三角形。圈常稱為三角形。 易知，圖中若兩個(gè)不同點(diǎn)易知，圖中若兩個(gè)不同點(diǎn)u與與v 間存在途徑間存在途徑(通路通路)，則，則 u 與與 v 間必存在路；若過點(diǎn)間必存在路；若過點(diǎn)u存在回路，則過點(diǎn)存在回路，則過點(diǎn)u 必存在必存在圈圈 。 數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling例例4.1 在下圖在下圖G 中，取中，取w1=v1v2v3，w2=v1v2v3v4v2 ，w3=v1v2v3v2v3v4 ( 注：簡(jiǎn)單圖可只用點(diǎn)序列表通路）注：簡(jiǎn)單圖可只用點(diǎn)序

51、列表通路）v1v4v5v3v2Gw1, w2, w3 依次為長(zhǎng)為依次為長(zhǎng)為2,4,5的途徑；的途徑；w1與與w2為為跡跡 ，w1為路。為路。 另外我們可看出另外我們可看出,G中中v1v2v5v1為長(zhǎng)為為長(zhǎng)為3的圈，的圈，v1v2v3 v4v2v5v1 為長(zhǎng)為為長(zhǎng)為 6 的回路。的回路。圖圖4.1數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 定義定義4.2 任意兩點(diǎn)之間均存在通路的圖稱為任意兩點(diǎn)之間均存在通路的圖稱為連通圖連通圖，否則稱為，否則稱為非連通圖非連通圖。非連通圖中的

52、連通子圖，稱為。非連通圖中的連通子圖，稱為連通分支連通分支。 圖圖4.3所示的圖為連通圖，而圖所示的圖為連通圖，而圖4.4所示的圖為非連通圖，它含有所示的圖為非連通圖，它含有兩個(gè)連通分支。兩個(gè)連通分支。圖圖4.3圖圖4.4數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 定義定義4.3 設(shè)圖設(shè)圖G是賦權(quán)圖，是賦權(quán)圖， 為為G中的一條路，則稱中的一條路，則稱 的的各邊權(quán)之和為路各邊權(quán)之和為路 的的長(zhǎng)度長(zhǎng)度。 對(duì)于對(duì)于G的兩個(gè)頂點(diǎn)的兩個(gè)頂點(diǎn)u和和v，從，從u到到v的路一般不只一條，的

53、路一般不只一條，其中最短的一條稱為從其中最短的一條稱為從u到到v的的最短路最短路；最短路的長(zhǎng)稱為從；最短路的長(zhǎng)稱為從u到到v的的距離距離，記為，記為d(u, v)。 約定約定: d(u, u)=0; d(u,v d(u,v)=)= ，若沒有路連接若沒有路連接u和和v。 圖圖G的的直徑直徑: d(G) = max d(u, v) | u, vV數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 最短路問題是圖論應(yīng)用的基本問題，很多實(shí)際問題，最短路問題是圖論應(yīng)用的基本問題，很多實(shí)際問題

54、，如線路的布設(shè)、運(yùn)輸安排、運(yùn)輸網(wǎng)絡(luò)最小費(fèi)用流等問題如線路的布設(shè)、運(yùn)輸安排、運(yùn)輸網(wǎng)絡(luò)最小費(fèi)用流等問題,都可通過建立最短路問題模型來求解都可通過建立最短路問題模型來求解. 求解最短路問題的兩種方法：求解最短路問題的兩種方法：Dijkstra和和Floyd算法算法. (1)求賦權(quán)圖中從給定點(diǎn)到其余頂點(diǎn)的最短路求賦權(quán)圖中從給定點(diǎn)到其余頂點(diǎn)的最短路; ; (2) (2)求賦權(quán)圖中任意兩點(diǎn)間的最短路求賦權(quán)圖中任意兩點(diǎn)間的最短路. .數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 解決上述問

55、題的一個(gè)方法是由解決上述問題的一個(gè)方法是由Dijkstra (迪杰斯特拉迪杰斯特拉)于于1959年提出的算法，此算法不僅能求出賦權(quán)圖指定兩點(diǎn)年提出的算法，此算法不僅能求出賦權(quán)圖指定兩點(diǎn)間的最短路，而且能求出從指定點(diǎn)到其余各頂點(diǎn)的最短路間的最短路，而且能求出從指定點(diǎn)到其余各頂點(diǎn)的最短路. 目前它是求無(wú)負(fù)權(quán)圖最短路的目前它是求無(wú)負(fù)權(quán)圖最短路的最好最好方法方法. Dijkstra算法是一種迭代算法，它依據(jù)的是一個(gè)重要而算法是一種迭代算法，它依據(jù)的是一個(gè)重要而明顯的性質(zhì)：明顯的性質(zhì)： 最短路是一條路，最短路上的任一子段也是最短路。最短路是一條路，最短路上的任一子段也是最短路。數(shù)數(shù) 學(xué)學(xué) 模模 型型 S

56、HENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 按距按距u從近到遠(yuǎn)為順序，依次求得從近到遠(yuǎn)為順序，依次求得u0到圖到圖G的各頂點(diǎn)的各頂點(diǎn)的最短路和距離，直至頂點(diǎn)的最短路和距離，直至頂點(diǎn)v(或直至圖或直至圖G的所有頂點(diǎn)的所有頂點(diǎn))。步驟步驟: :把結(jié)點(diǎn)集把結(jié)點(diǎn)集V V分割為二子集分割為二子集 S,T.S,T.開始時(shí)開始時(shí)S=a,TS=a,T= =V-V-S S. .步驟步驟: :對(duì)每結(jié)點(diǎn)對(duì)每結(jié)點(diǎn) t t T T, ,求出求出 D(tD(t) )之后再定出之后再定出x x T T 使得使得 D(xD(x)=

57、)= minD(x)|tminD(x)|t T T.步驟步驟: :置置 S S 為為 S Sxx 置置 T T為為T-x.T-x.若若 T=T=則停止則停止, ,否則轉(zhuǎn)否則轉(zhuǎn)步驟步驟作作下一次循環(huán)下一次循環(huán). .數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 對(duì)每個(gè)頂點(diǎn)對(duì)每個(gè)頂點(diǎn)v，定義兩個(gè)標(biāo)號(hào)，定義兩個(gè)標(biāo)號(hào)l(v), z(v), 其中其中l(wèi)(v)為從為從u0到到v的路長(zhǎng)；的路長(zhǎng)； z(v)為為v的父節(jié)點(diǎn)（前一個(gè)點(diǎn)）。的父節(jié)點(diǎn)（前一個(gè)點(diǎn)）。S：具有永：具有永久標(biāo)號(hào)的頂集。久標(biāo)號(hào)

58、的頂集。 算法的過程就是在每一步改進(jìn)這兩個(gè)標(biāo)號(hào)，最終算法的過程就是在每一步改進(jìn)這兩個(gè)標(biāo)號(hào)，最終l(v)為為u0到到v的最短路長(zhǎng)。的最短路長(zhǎng)。 輸入帶權(quán)鄰接矩陣（距離矩陣）輸入帶權(quán)鄰接矩陣（距離矩陣）w(u, v).數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling000(1): , ()0, ,( ),( ),(2)( ), ( ): ,( )( )( , ),( )( )( , ),( )(3)*( ), *,*(4),(2);,.Sul uvSVSl vz vuul v z v

59、vSVSl vl uw u vl vl uw u vz vuvl vSSSvuvS 賦初值 令令更新若則令設(shè)是使取最小值的 中的頂點(diǎn) 則令若轉(zhuǎn)否則 停止數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 尋求賦權(quán)圖中各對(duì)頂點(diǎn)之間最短路，顯然可以調(diào)用尋求賦權(quán)圖中各對(duì)頂點(diǎn)之間最短路，顯然可以調(diào)用 Dijkstra 算法。算法。 具體方法是：每次以不同的頂點(diǎn)作為起點(diǎn)，用具體方法是：每次以不同的頂點(diǎn)作為起點(diǎn)，用 Dijkstra 算法求出從該起點(diǎn)到其余頂點(diǎn)的最短路徑，反復(fù)算法求出從該起點(diǎn)到

60、其余頂點(diǎn)的最短路徑，反復(fù)執(zhí)行這樣的操作，就可得到每對(duì)頂點(diǎn)之間的最短路。執(zhí)行這樣的操作，就可得到每對(duì)頂點(diǎn)之間的最短路。 但這樣做需要大量重復(fù)計(jì)算，效率不高。但這樣做需要大量重復(fù)計(jì)算，效率不高。R. W. Floyd（弗洛伊德）另辟蹊徑，提出了比這更好的算法，操作方（弗洛伊德）另辟蹊徑，提出了比這更好的算法，操作方式與式與 Dijkstra 算法截然不同。算法截然不同。數(shù)數(shù) 學(xué)學(xué) 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 直接在圖的帶權(quán)鄰接矩陣中用插入頂點(diǎn)的直接在圖的帶權(quán)鄰接矩陣中用插入