圖論在數(shù)學建模中應(yīng)用

圖論及其應(yīng)用主講：劉飛月大連大學數(shù)學建模工作室圖論最基本的概念線(edge)：兩個事物間具有的關(guān)系。

圖(Graph)：由點及連接線所構(gòu)成的圖形，用G=(V,E)表示。點(vertex)：代表事物。圖的基本概念一、圖的定義及其表示定義1圖G是一個三元組，其中V是一個非空的結(jié)集合，E是邊的集合，從邊集合E到結(jié)點無序偶或有序偶集合上的函數(shù)。常記為：例1

設(shè)

則是一個圖 有關(guān)圖的一些術(shù)語和概念點與邊的關(guān)聯(lián)

:點是邊的一個端點點與點的相鄰:兩點被同一邊相連邊與邊的相鄰:兩邊至少有一個公共端點環(huán)邊:兩端點重合的邊重邊:連接兩點的兩條或兩條以上的邊稱為這兩點的重邊簡單圖:既無環(huán)邊也無重邊的圖完全圖:任意兩點間都有一條邊的簡單圖度的概念度（次）：節(jié)點v相連的邊的數(shù)目，表示為d（v）。設(shè)圖G=<V,E>為無向圖或有向圖，則G中所有點的度數(shù)之和是邊數(shù)之和的2倍。奇數(shù)度節(jié)點：節(jié)點的度的數(shù)目為奇數(shù)的點；偶數(shù)度節(jié)點：節(jié)點的度的數(shù)目為偶數(shù)的點。關(guān)于度的定理定理圖G中所有節(jié)點的度數(shù)和是邊數(shù)的2倍。推理任意圖，奇數(shù)度節(jié)點的個數(shù)總和為偶數(shù)。最短路問題賦權(quán)圖：

對圖G的每條邊e，賦以一個實

數(shù)稱為邊e的權(quán)。每條邊都賦有權(quán)的圖稱為賦權(quán)圖.

權(quán)在不同問題中會有不同的含義，例如交通網(wǎng)絡(luò)中，權(quán)可能表示運費，里程或道路的造價等。

給定賦權(quán)圖G及G中兩點u，v，求u到v的具有最小權(quán)的路（稱為u到v的最短路）

注：賦權(quán)圖中路的權(quán)也稱路的長，最短（u，v）路的長也稱為u，v的距離，記為

最短路問題是一個優(yōu)化問題屬于網(wǎng)絡(luò)優(yōu)化和組合優(yōu)化的范疇，對這種優(yōu)化問題的解答一般是一個算法，Dijkstra是最基本的一個算法。最短路問題:dijkstra算法思想：設(shè)賦權(quán)圖G中所有邊具有非負權(quán)，dijkstra算法的目標是求出是求出G中某個指定頂點到其他所有點的最短路。它依據(jù)的基本原理是：若路是從到的最短路，則必是從的最短路?；谶@一原理，算法由近及遠逐次求出到其他各點的最短路。例Dijkstra算法步驟G中從

到其余各點的最短路第一步：令,。第二步：對每個令

取使得

記

令第三步：令

如果，則停止，輸出各

點標號并反向追溯最短路；否則，轉(zhuǎn)第二步。

算法中步驟(1)和(3)是清楚的,現(xiàn)在對2給以說明。

表示從

到

的不包含

中其它結(jié)點的最短通路的長度,但

不一定是從

到

的距離,因為從

到

可能有包含

中另外結(jié)點的更短通路。

首先我們證明“若

是

中具有最小

值的結(jié)點,則

是從

到

的最小距離”,用反證法。若另有一條含有

中另外結(jié)點的更短通路,不妨設(shè)這個通路中第一個屬于

的結(jié)點是

,于是

,但這與題設(shè)矛盾?？梢娨陨蠑嘌猿闪?。在下圖中求到其它各點的最短路

Dijkstra算法是求源點到其它頂點的最短路徑。怎樣求任意兩個頂點之間的最短路徑？我們可以把Dijkstra算執(zhí)行n次，每次從不同的頂點開始，則算法時間復(fù)雜度為O（n3）。

Floyd弗洛伊德給出了另一個算法，時間復(fù)雜度也是O（n3），但是形式上簡單些。Floyd算法算法的基本步驟（1）輸入權(quán)矩陣（2）計算

其中（3）中元素

就是vi到vj的最短路長優(yōu)缺點分析Floyd算法適用于APSP(AllPairsShortestPaths)，是一種動態(tài)規(guī)劃算法，稠密圖效果最佳，邊權(quán)可正可負。此算法簡單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對于稠密圖，效率要高于執(zhí)行|V|次Dijkstra算法。優(yōu)點：容易理解，可以算出任意兩個節(jié)點之間的最短距離，代碼編寫簡單.

缺點：時間復(fù)雜度比較高，不適合計算大量數(shù)據(jù)。樹及其性質(zhì)：不含圈的圖稱為森林，不含圈的連通圖稱為樹。生成樹：設(shè)是的一個子圖，如果是一棵樹，且，則稱是的一個生成樹。每個連通圖都有生成樹。樹的性質(zhì)（下例命題等價）：是樹；中無環(huán)邊且任二頂點之間有且僅有一條路；中無圈且；連通且；連通且對任何不連通；無圈且對任何恰有一個圈；kruskal算法1.算法思想先從圖G中找出權(quán)最小的一條邊（具有最小耗費的邊）作為最小生成樹的邊，然后逐次從剩余邊中選邊添入最小生成樹中。選邊原則：每次挑選不與已邊構(gòu)成圈的邊中權(quán)最小的一條直至選出條邊為止。算法步驟第一步：取使得，令。第二步：取使得（1）不含圈；（2）是滿足（1）的權(quán)最小的邊。第三步：當時，輸出最小生成樹，算法停止，否則令，轉(zhuǎn)第二步。

第一步我們要做的事情就是將所有

的

邊的長度排

序，用

排序的結(jié)果作為我們

選

擇

邊

的

依

據(jù)。這里再次體現(xiàn)

了貪心算

法

的思想。

資源排序，對局部最優(yōu)的資源進行選擇。

排序完成后，我們率先選擇了邊AD。這樣我們的圖就變成了。第二步，在剩下的邊中尋找。我們找到了CE。這里邊的權(quán)重也是5依次類推我們找到了6,7,7。完成之后，圖變成了這個樣子。

下一步就是關(guān)鍵了。下面選擇那條邊呢？BC或者EF嗎？都不是，盡管現(xiàn)在長度為8的邊是最小的未選擇的邊。但是現(xiàn)在他們已經(jīng)連通了（對于BC可以通過CE,EB來連接，類似的EF可以通過EB,BA,AD,DF來接連）。所以我們不需要選擇他們。類似的BD也已經(jīng)連通了（這里上圖的連通線用紅色表示了）。

最后就剩下EG和FG了。當然我們選擇了EG。最后成功的圖就是下圖：到這里所有的邊點都已經(jīng)連通了，一個最小生成樹構(gòu)建完成。Kruskal算法的實現(xiàn)及其復(fù)雜度分析：Kruskal的計算主要在第二步.算法共需執(zhí)行次第二步，在第次執(zhí)行第二步時，須比較集合中所有邊的以求得一條權(quán)最小的邊，并檢驗該邊是否與已有邊構(gòu)成圈，如果構(gòu)成圈，還需要再找新的最小權(quán)邊，這是比較浪費的。在實際應(yīng)用Kruskal算法時，一般先將所有的邊按權(quán)由小到大排序，每次執(zhí)行算法第二步時，不必再比較邊的權(quán)，而是直接選取此前尚未考慮過的權(quán)最小的邊，檢驗它是否與已有邊構(gòu)成圈即可，這樣可以省去許多次重復(fù)比較。接下來的問題如何檢驗所選邊是否與已有邊構(gòu)成圈？Prim算法算法思想：先從圖G中找出權(quán)最小的一條邊作為最小生成樹的邊，在算法任一輪循環(huán)中，設(shè)已經(jīng)選出的邊導(dǎo)出的子圖為G1,從G1的頂點向G1以外頂點的連邊權(quán)集合E1，則選擇E1中權(quán)值最小的邊向G1中添加，如此反復(fù)循環(huán)直至選出邊為止。算法步驟：第1步：任，令第2步：求到間權(quán)最小的邊，設(shè)屬于的端點為，令第3步：當時，輸出最小生成樹，算法停止；否則令，轉(zhuǎn)第2步。算法的計算復(fù)雜度：Prim算法的主要計算量在第2步。在算法第輪循環(huán)執(zhí)行第步時，中有個頂點，中有個頂點，故到間最多有條邊，從這些邊中選出一條權(quán)最小的邊，需要次比較。算法需循環(huán)執(zhí)行第2部次，因此總的計算量為由此，Prim算法的計算復(fù)雜度為標號Prim算法算法思想：給圖中的頂點賦以標號，該標號與邊的權(quán)有關(guān)，在執(zhí)行Prim算法的過程中，通過修改頂點標號和比較頂點的標號大小，來選擇滿足Prim要求的最小權(quán)邊。頂點的標號記為，用表示邊的權(quán)。若兩點間沒有邊，則算法步驟：第一步：任取，令第二步：對，若，則令第三步：選取使得。設(shè)，使得，令，。第四步：當時，輸出最小生成樹，算法停止；否則，令，轉(zhuǎn)第二步停止算法的計算復(fù)雜度分析：算法的主要計算量在第2步和第3步。算法第一次執(zhí)行第三步至多需做次比較，第二次執(zhí)行第三步至多需做次比較，，因此執(zhí)行第三步至多共需要做：次比較；同樣執(zhí)行第二步共需不超過次比較，于是標號Prim算法的時間復(fù)雜度為。標號Prim算法將Prim算法每次循環(huán)中比較到間所有邊的權(quán)改為，并比較中頂點的標號，因此節(jié)省了計算量。Euler圖與Hamilton圖：歐拉通路（路徑）：走遍圖G每一條邊一次僅且一次的通路。歐拉回路：走遍圖G每一條邊一次僅且一次的回路。具有歐拉回路的圖稱為歐拉圖。漢密爾頓通路（路徑）：走遍圖G每個頂點一次且僅一次的通路。漢密爾頓回路：走遍圖G每個頂點一次僅且一次的回路。具有哈密爾頓回路的圖稱為哈密爾頓圖。判別條件無向連通圖G具有一條歐拉路徑當且

僅當G具有零個或兩個奇數(shù)次數(shù)的頂點。若無奇數(shù)度頂點（全為偶度頂點），則通路為回路；若僅有兩個奇數(shù)度頂點，則它們是每條歐拉通路的端點。求Euler圖中的Euler閉跡--Fleury算法：對于復(fù)雜一些的圖，即使判定出它有Euler閉跡，也未必能很快地找出一條Euler閉跡。在許多大規(guī)模應(yīng)用中，需要借助于算法來找圖的Euler閉跡——Fleury算法。基本思想：從圖中一個頂點出發(fā)，用深度優(yōu)先方法找圖的跡，在任何一步，盡可能不要用剩余圖的割邊，除非沒有別的選擇。Fleury算法的步驟：第1步：任取，令，第2步：設(shè)跡已取定.從中選取一條邊使得（1）和相關(guān)聯(lián)；（2）不選的割邊，除非沒有別的選擇。第3步：當?shù)?步不能再執(zhí)行時，停止。中國郵遞員問題：問題（管梅谷，1960）：一位郵遞員從郵局出發(fā)投遞郵件，經(jīng)過他所管轄的每條街道至少一次后，回到郵局。請為他選擇一條路線，使其所行路程盡可能短。圖論模型：求賦權(quán)連通圖中含所有邊且權(quán)最小的閉途徑。這樣的閉途徑稱為最優(yōu)郵路基本思想：

（1）若G是Euler圖，則G的Euler閉跡便是最優(yōu)郵路，可用Fleury算法求得。（2）若G不是Euler圖，則含有所有邊的閉途徑必須重復(fù)經(jīng)過一些邊。此可以構(gòu)造一個Euler圖。如何構(gòu)造Euler圖：閉途徑重復(fù)經(jīng)過一些邊，實質(zhì)上可看成給圖G添加了一些重復(fù)邊（其權(quán)值與原邊的權(quán)相等），最終消除了奇度頂點形成一個Euler圖。因此這種情況下求最優(yōu)郵路可分為兩步。首先給圖G添加一些重復(fù)邊得到Euler圖G1，使得添加邊的權(quán)之和最小，（其中）；用FLeury算法求得G1的一條Euler閉跡。這樣便得到G的一條最優(yōu)郵路。問題是：如何給圖G添加重復(fù)邊得到Euler圖G1，使得添加邊的權(quán)之和最小Edmons-Johnson方法：第1步：若G中無奇度頂點，令G1=G，轉(zhuǎn)第2步；否則轉(zhuǎn)第3步。第2步：求G1中的Euler閉跡，并按該Euler閉跡輸出G的最優(yōu)郵路；