【摘要】：本論文主要研究限制性路構(gòu)建問題,包括兩個基本內(nèi)容,即限制性路增廣問題和限制性路構(gòu)建問題。限制性路增廣問題可以描述為:給定一個有向圖D =(V,A;c)以及圖D中的一條s-t有向路Ps,t,其中s,t∈V,費用函數(shù)c:A →R+,要尋找弧子集A1(?)A-A(Ps,t),滿足對任一條弧a ∈ A(Ps,t)(或者對任一個頂點u ∈ V(Ps,t)-{s,t}),在誘導子圖Ps,t ∪A1-{a}(或者誘導子圖Ps,t ∪A1-{u})中仍存在一條s-t有向路,目標是使得所選弧集合A1的總費用c(A1)達到最小,即c(A1)=∑e∈A1c(e)達到最小。對于這兩個問題,本文設計了兩個時間復雜度為O(mn)多項式時間最優(yōu)算法,其中m表示有向圖D中弧的數(shù)目,n表示有向圖D中頂點的數(shù)目。在上述問題的基礎上,本文研究了限制性路構(gòu)建問題,具體描述為:給定一個賦權(quán)有向圖D=(V,A;w,c),長度為L的材料若干,以及圖DD中一條s-t有向路Ps,t,其中s,t∈V,長度函數(shù)w:A→RR+,施工費用函數(shù)c:→→R+,要構(gòu)建一個弧集合A1(?)A-A(Ps,t),滿足對任一條弧a∈A(Ps,t(或者對任一個頂點u∈V(s,t)-{s,t}),在誘導子圖Ps,u A1—{a}(或者誘導子圖Ps,∪ A1—{u})中仍存在一條s-t有向路,目標是使得構(gòu)建弧集合A1的總費用cost(A1)達到最小,即cost(A1)= ∑e∈A1(e)+k(A1)·c0達到最小,這里總費用包括施工費用和購買材料的費用,k(A1)表示構(gòu)建弧集合A1所需材料的根數(shù),c0為每根材料的購買費用。對于此類問題,本文設計了兩個時間復雜度為O(mn)的2-近似算法,其中m表示有向圖D中弧的數(shù)目,n表示有向圖D中頂點的數(shù)目。
【學位授予單位】：云南大學
【學位級別】：碩士
【學位授予年份】：2018
【分類號】：O157.5

【參考文獻】

相關(guān)博士學位論文 前1條

1 丁紅林;限制性路由與網(wǎng)絡構(gòu)建問題[D];云南大學;2014年

本文編號：2750089