網(wǎng)絡(luò)最短路的解集結(jié)構(gòu)及有關(guān)問題.pdf

1、鄭州大學(xué)碩士學(xué)位論文網(wǎng)絡(luò)最短路的解集結(jié)構(gòu)及有關(guān)問題姓名：張振坤申請學(xué)位級別：碩士專業(yè)：運(yùn)籌學(xué)與控制論指導(dǎo)教師：羅來興林詒勛2002.5.1P：構(gòu)成的子圖中含有k個2一重路，則P。與P：所構(gòu)成的子圖的2一變換圖為含2‘個頂點(diǎn)的k一立方體。定理7若網(wǎng)絡(luò)N為準(zhǔn)樹形網(wǎng)絡(luò)，且含有至少兩條最短路，則N的最短路2一變換圖是完全圖K。，其中n為N的最短路的條數(shù)。。定理8對任意網(wǎng)絡(luò)N，如果其等勢子網(wǎng)絡(luò)N。是準(zhǔn)樹形網(wǎng)絡(luò)。則其最短路2～變換圖是完全圖耽，其中

2、n為N。中(s，t)路的條數(shù)。定理9有向?qū)j(luò)Ⅳ的最短路的2一變換圖是連通圖。定理lO若網(wǎng)絡(luò)N含有k／3條最短路，則其最短路2一變換圖的圍長等于3或4。定理11若網(wǎng)絡(luò)Ⅳ含^≥3條最短路，則其最短路的2一變換圖是Ham—ilton圖。命題如果網(wǎng)絡(luò)N含有k條最短路，則其最短路的2一變換圖的直徑至多為k一1。3多端最短路的縮減模型本文第四章討論了多端最短路的縮減問題(也稱為網(wǎng)絡(luò)最短路的提速問題)，其具有重要的應(yīng)用背景。該問題由文[20]提出并得

3、到了其數(shù)學(xué)模型(41)與它的算法。以此為基礎(chǔ)，我們在本章中討論了它的特殊情形：(0，1)一縮減模型的計(jì)算復(fù)雜性以及指定路線情形的線性規(guī)劃模型(42)和它的算法。定理12在(0，1)一縮減方式下，模型(41)的判定形式是NP一完全的。即使網(wǎng)絡(luò)N的基礎(chǔ)圖是一棵樹且對任意弧(i，，)∈E，其縮減費(fèi)用“(￡)=t和a。=0，此結(jié)論仍然成立。定理13如果網(wǎng)絡(luò)N中連結(jié)每一源匯對(跏t；)(i=I，2，，k)的最短路Pi(i=1，2，，k)均被指定，

4、則模型(41)是有多項(xiàng)式時間算法的。推論1如果網(wǎng)絡(luò)N是一棵樹單源有向樹，則線性規(guī)劃模型(42)具有強(qiáng)多項(xiàng)式的時間算法。本章最后討論了單源網(wǎng)絡(luò)N=(s，t；，V，E)(i=1，2，。k)在指定路線情形下的線性規(guī)劃模型，給出了此種情形下的線性規(guī)劃算法41，并研究了算法41的正確性和計(jì)算復(fù)雜性。定理14算法41結(jié)束時，可以得到模型(45)的一個最優(yōu)解。定理15算法41是多項(xiàng)式時間算法，計(jì)算復(fù)雜性為0(月mlogn)，其中n=fyf，m=fE【