網(wǎng)絡最短路的解集結構及有關問題.pdf

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

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

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

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