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

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

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

設(shè)

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

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

對(duì)圖G的每條邊e，賦以一個(gè)實(shí)

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

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

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

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

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

到其余各點(diǎn)的最短路第一步：令,。第二步：對(duì)每個(gè)令

取使得

記

令第三步：令

如果，則停止，輸出各

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

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

表示從

到

的不包含

中其它結(jié)點(diǎn)的最短通路的長(zhǎng)度,但

不一定是從

到

的距離,因?yàn)閺?/p>

到

可能有包含

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

首先我們證明“若

是

中具有最小

值的結(jié)點(diǎn),則

是從

到

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

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

的結(jié)點(diǎn)是

,于是

,但這與題設(shè)矛盾?？梢?jiàn)以上斷言成立。在下圖中求到其它各點(diǎn)的最短路

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

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

其中（3）中元素

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

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

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

的

邊的長(zhǎng)度排

序，用

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

選

擇

邊

的

依

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

了貪心算

法

的思想。

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

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

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

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

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

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