姜新文 吳添君 李鵬坤 樊碩 周泰楊 魏登萍

摘要：MSP問題是文獻[1，2]提出的一個問題。研究表明[3]該問題對NP類問題有很強的表達能力。本文給出一個關(guān)于該問題的求解算法、復(fù)雜性分析，以及正確性證明。本文對于NP完全問題研究有重要意義。

關(guān)鍵詞：算法；MSP問題；算法設(shè)計；復(fù)雜性

中圖分類號：TP301.6文獻標(biāo)識碼：A

1問題引入及若干定義

MSP問題是一個人工構(gòu)造的問題。為了本文的完整性，我們首先轉(zhuǎn)述對MSP問題的定義[1，2]。

定義1稱G=V，E，S，D，L，λ是一個加標(biāo)多級圖（labeledmultistagegraph），如果滿足以下條件：

1.V為頂點集合，L稱為G的級。V=V0∪V1∪V2∪…∪VL，Vi∩Vj=，0≤i，j≤L，i≠j。如果u∈Vi（0≤i≤L），稱u所在級為i級，也稱u是i級的頂點。

2.V0和VL都只包含唯一頂點。稱V0中的唯一頂點為源點，記為S，稱VL中的唯一頂點為匯點，記為D。

3.E為邊的集合，E中的邊均為有向邊。用三元組u，v，l表示一條u到v的邊。如果u，v，l∈E（1≤l≤L），則u∈Vl-1，v∈Vl。稱u，v，l為G的第l級的邊。

4.λ是一個從V-{S}到2E的映射。對每個頂點v∈V-{S}，λ（v）E。稱λ（v）為頂點v的邊集。

上述定義中，用三元組u，v，l表示邊，而不是通常的采用二元組u，v，我們有特殊的考慮。因為我們在算法處理過程中總是需要知道邊的起點、終點以及所在的級，用三元組表示，處理起來更為直觀，而且對于復(fù)雜性的把握變得更加直接。

看兩個例子。圖1所示的兩個圖，都是加標(biāo)多級圖。各個頂點的邊集的一組可能的取值定義如下。對左邊的圖，λ（1）={e1}，λ（2）={e2}，λ（3）={e1，e2，e3，e4}，λ（4）={e1，e3，e5}，λ（5）={e2，e4，e6}，λ（6）={e1，e3，e5，e10}，λ（7）={e12}，λ（8）={e1，e3，e6，e8}，λ（D）={e1，e3，e5，e10，e12}。對右邊的圖，λ（1）=，λ（2）=，λ（3）=，λ（4）={e1，e3，e5}，λ（5）={e2，e4，e6}，λ（6）={e1，e3，e5}，λ（7）=λ（7′）={e1，e3，e6，e8}，λ（8）={e1，e3，e6，e8}，λ（D）=。

定義2設(shè)G=V，E，S，D，L，λ是一個加標(biāo)多級圖，P是G中一條路徑，ES是邊集E的一個子集。如果P上的所有邊都屬于邊集ES，我們稱P屬于ES，或者稱ES包含P，記為P∈ES。

定義3設(shè)G=V，E，S，D，L，λ是一個加標(biāo)多級圖，S-u1-…-ul-…-uL（1≤l≤L，uL=D）是G中一條路徑。如果對任意的頂點ul，其中l(wèi)∈{1，2，…，L}，S-…-ul∈λ（ul），稱G中的這條路徑為簡單路徑。如果對任意的頂點ul，其中l(wèi)∈{1，2，…，L-2}或者l∈{1，2，…，L-1}，S-…-ul∈λ（ul），稱G中的這條路徑為半簡單路徑。

顯然，根據(jù)定義，如果一條路徑是簡單路徑，它必為半簡單路徑。反之不然。

簡單路徑的概念在圖論中已經(jīng)有過。它的傳統(tǒng)的含義是，一條路徑稱為簡單路徑，其中的頂點不能重復(fù)。對本文中定義的加標(biāo)多級圖，一條路徑上的頂點肯定是不重復(fù)的。但是，路徑上的頂點邊集，實際上實現(xiàn)了一種“排它”性，所以，我們借用了簡單路徑這個概念。

現(xiàn)在提出一個問題。

設(shè)G=V，E，S，D，L，λ是一個加標(biāo)多級圖。

問：G中是否存在一條簡單路徑，即是否存在路徑S-u1-…-ul-…-uL（1≤l≤L，uL=D），使得S-…-ul∈λ（ul）？

這個問題就是要判定一個加標(biāo)多級圖中簡單路徑的存在性。我們稱這個問題為MSP問題，即多級圖簡單路徑（MultistagegraphSimplePath）問題。

不是所有的加標(biāo)多級圖都有簡單路徑。一個加標(biāo)多級圖是否包含簡單路徑，取決于圖，同時也取決于各個頂點的邊集的取值。例如，對于圖1中左圖，S-1-3-4-6-D是一條簡單路徑。而圖1右圖中沒有簡單路徑。

在一個加標(biāo)多級圖中，判定從源點到匯點的路徑的存在性是容易的。這是一個簡單的連通性判定的問題。然而，判定簡單路徑的存在性，不是一件容易的事情。

下面開始討論MSP問題的求解算法，稱之為ZH算法。我們的算法只解決判定問題，對于一個給定的加標(biāo)多級圖，回答簡單路徑的存在性。

2求解MSP問題的ZH算法

首先給出四個基本算子。

2.1四個基本算子定義

基本算子1：[ES]vu。

設(shè)G=V，E，S，D，L，λ是一個加標(biāo)多級圖，ES是邊集E的一個子集，u，v∈V。定義[ES]vu={e|e∈ES，eisonapathu-…-v，andalltheedgesonu-…-varecontainedinES}。如果u，v屬于同一級或者u的級高于v的級，定義[ES]vu=。

[ES]vu的目的是整理邊集ES。ES中可能包含一些零零散散的邊。這些邊因為不在u到v路徑上，因而從ES中去掉。[ES]vu的結(jié)果是ES的子集。如果用|E|表示G中邊的數(shù)目，可以設(shè)計O（|E|）的算法計算[ES]vu。

定義4設(shè)G=V，E，S，D，L，λ是一個加標(biāo)多級圖。如果G=V，E，S，D，L，λ中存在一條路徑v-vl+1-…-vL-1-D，使得邊u，v，l∈λ（v）∩λ（vl+1）∩…∩λ（vL-1）∩λ（D），我們稱路徑v-vl+1-…-vL-1-D為u，v，l的可達路徑。u，v，l的所有可達路徑構(gòu)成u，v，l的可達路徑集。u，v，l的所有可達路徑經(jīng)過的邊構(gòu)成可達路徑集邊集。endprint

為了描述u，v，l的可達路徑集邊集，特別是為了算法中處理可達路徑，本文用變量符號R（u，v，l）表示u，v，l的可達路徑集邊集。一般處理和描述路徑都是將路徑一條條描述出來，但本文的R（u，v，l）是邊集E的子集，R（u，v，l）中包含的是u，v，l的可達路徑經(jīng)過的邊。因為R（u，v，l）是算法的變量，所以開始的時候，R（u，v，l）包含的是定義4定義的可達路徑集邊集，計算過程中會單調(diào)減少。

下面的討論中，我們除了用R（u，v，l）表示邊u，v，l的可達路徑集邊集，有時候也用R（e）表示邊e的可達路徑集邊集。當(dāng)需要精確知道一條邊的起點、終點以及所在級的時候，我們選擇用R（u，v，l）表示。否則，就簡單地用R（e）表示。

一個加標(biāo)多級圖給定之后，可以計算出所有邊的可達路徑集邊集。

基本算子2：Init（R（u，v，l））。

Init（R（u，v，l））用來計算加標(biāo)多級圖G=V，E，S，D，L，λ中邊u，v，l的R（u，v，l）的值，計算結(jié)果放在R（u，v，l）中：

1.ES{a，b，k|a，b，k∈E，l

2.R（u，v，l）[ES]Dv //Linkingedgestogether

按照定義，算子2計算的結(jié)果，R（u，v，l）中包含u，v，l的所有可達路徑經(jīng)過的邊。如果用|E|表示G中邊的數(shù)目，可以設(shè)計O（|E|）的算法計算Init（R（u，v，l））。

再次強調(diào)一下，雖然稱作可達路徑集，R（e）僅僅是邊的集合。本文討論中涉及路徑的集合都是邊集，因而，它們的規(guī)模是多項式的而不是指數(shù)的。如同英文單詞很多，但字母表只有26個字符。

基本算子3：Comp（ES，v，R（E））。

設(shè)G=V，E，S，D，L，λ是一個加標(biāo)多級圖，ESE，v∈V，R（E）={R（e）|e∈E}。Comp（ES，v，R（E））等于以下迭代結(jié)束時ES_temp中的結(jié)果：

4.Repeatstep2andstep3untilES_tempwillnotchangeanymore.

解釋一下Comp（ES，v，R（E））的計算過程。簡單地說，步驟2是去掉ES_temp中的邊a，b，k，條件是R（a，b，k）∩ES_temp不含b到v的路徑。步驟3是整理邊集ES_temp。這個去邊和整理的過程反復(fù)實施，直到ES_temp不再變化。由于ES中包含的邊的條數(shù)是一個定數(shù)，這個計算過程必然終止。

R（E）={R（e）|e∈E}是Comp（ES，v，R（E））計算過程中需要使用的一組值。也可以將R（E）={R（e）|e∈E}作為全局變量定義，不需要作為參數(shù)變量帶入到算子中來。有很多人建議在Comp（ES，v，R（E））算子中明顯給出R（E），也有很多人認為不需要給出R（E）。這里還是在Comp（ES，v，R（E））中明顯給出R（E），使我們可以明確看到R（E）對于Comp（ES，v，R（E））的影響。事實上，后面將介紹的ZH算法，就是一個反復(fù)的利用R（E）限制各個Comp（λ（v），v，R（E）），又反過來利用所有的這些Comp（λ（v），v，R（E））限制R（E）的過程。

不同于算子2和下面的算子4適宜于被當(dāng)做子程序看待（調(diào)用子程序的結(jié)果是，參數(shù)變量發(fā)生改變），請將算子3當(dāng)做函數(shù)看待，函數(shù)值作為返回值。

顯然，對任意λ（v），有Comp（λ（v），v，R（E））λ（v）。

可以設(shè)計O（|E|2）的算法計算步驟2。步驟2和步驟3因而可以在O（|E|2）內(nèi)完成。每次迭代至少減少一條邊，ES_temp最多有|E|條邊，所以計算Comp（ES，v，R（E））的時間復(fù)雜性為O（|E|3）。

基本算子4：Change（R（u，v，l））。

Change（R（u，v，l））是用R（E）={R（e）|e∈E}中其它的R（e）限制和綁定R（u，v，l）。Change（R（u，v，l））將修改R（u，v，l）中的值，修改后的值仍然放在R（u，v，l）中。

1.Foralla，b，k∈R（u，v，l），l

ifComp（[{e|e=c，d，kk∈E，kk

thena，b，kiskeptinR（u，v，l）

elsea，b，kisdeletedfromR（u，v，l）.

2.R（u，v，l）[R（u，v，l）]Dv.

3.Repeatstep1andstep2untilR（u，v，l）willnotchangeanymore.

解釋一下Change（R（u，v，l））的計算過程。粗略地說，步驟1中，如果a，b，k繼續(xù)留在R（u，v，l）中，除非有路徑P=S-…-u陪著u，v，l經(jīng)過a，b，k，而且那些路徑P=S-…-u還需要滿足苛刻條件：設(shè)那些路徑的所有邊構(gòu)成集合ES，Comp（ES，u，R（E））必須非空。

算子4是有點復(fù)雜的。如果說算子1、算子2、算子3的提出還是出于一種直覺導(dǎo)致的產(chǎn)生，算子4主要出于一種邏輯證明的需要。我們將在章節(jié)2.4進一步分析指出這一點。算子4完成的信息探測，使我們可以確認在輸入的圖中存在一種性質(zhì)。算子4在我們完成算法證明中起著至關(guān)重要的作用。之所以我們能夠證明NP=P，最有價值的發(fā)現(xiàn)之一在于算子4。

Change（R（u，v，l））的復(fù)雜性依賴于算子1、算子2和算子3。我們可以在|E|*O（|E|3）的時間內(nèi)完成計算Comp（[{e|e=c，d，kk∈E，kk

修改后的R（u，v，l）是修改前的R（u，v，l）子集。我們?nèi)匀徊患訁^(qū)別地稱其為u，v，l的可達路徑集邊集。

2.2ZH算法、復(fù)雜性分析、必要性證明

現(xiàn)在給出求解MSP問題的、由以下四個語句構(gòu)成的ZH算法以及關(guān)于算法的分析證明。

ZH算法的輸入是G=V，E，S，D，L，λ。算法中符號ES[i：j]表示邊集ES中從第i級到第j級的邊，其中1≤i≤j≤L。如果i>j，ES[i：j]=。‘R（a，b，k）[k+1：l]∪v∈Vl[R（a，b，k）∩Comp（λ（v），v，R（E））]vb表示對R（a，b，k）的一部分賦值。只有R（a，b，k）的從第k+1級到第l級的部分被修改，其余的部分不變。將R（a，b，k）看成數(shù)組，這個賦值表示數(shù)組的一部分被改變。如果將R（a，b，k）放在圖靈機工作帶上，這個賦值表示工作帶上存放R（a，b，k）的那片區(qū)域的一部分被重新印刷。

因為算法輸入包含了一個頂點集合V，一個邊集E，一個源點S，一個匯點D，一個表示圖的級的量L，以及除源點S外的每個點v的邊集λ（v）。我們將這些量都當(dāng)成相應(yīng)變量的初值。算法中變量當(dāng)然可以被修改，算法中‘λ（v）Comp（λ（v），v，R（E））表示將修改的值放入λ（v）。R（e）是因為算法執(zhí)行需要而新開辟的變量，所有的R（e）構(gòu)成R（E）={R（e）|e∈E}。

算法執(zhí)行中會修改λ（v）。λ（v）中保留的值與初始的值一般是不同的?，F(xiàn)在開始一個約定：如不特別聲明，今后說到λ（v），我們是指圖定義時給出的值，或者算法輸入的初值。而用Comp（λ（v），v，R（E））表達變量λ（v）中保留的值，稱為λ（v）的計算值。簡單路徑的定義是基于初始值而不是計算值。

解釋一下算法的動作?！甊（a，b，k）[k+1：l]∪v∈Vl[R（a，b，k）∩Comp（λ（v），v，R（E））]vb意味著R（a，b，k）的從k+1級到l級的邊由∪v∈Vl[R（a，b，k）∩Comp（λ（v），v，R（E））]vb替換。替換之后，進一步執(zhí)行‘R（a，b，k）[R（a，b，k）]Db，以便保持R（a，b，k）=[R（a，b，k）]Db。

ZH算法的基本思想是用R（E）綁定R（u，v，l）（步驟2.1），用R（E）修改λ（v）（步驟2.2），同時，使用Comp（λ（v），v，R（E））限制修改R（E）（步驟2.3）。步驟3之后，用R（E）計算Comp（λ（D），D，R（E））。

ZHAlgorithm

1.Foralle∈E，wecallInit（R（e））togenerateR（e）directly.

2.Forl=2toL-1

2.1Forallu，v，lofstagel，callChangeR（u，v，l）tomodifyR（u，v，l）

2.2Forallvofstagel，λ（v）Comp（λ（v），v，R（E））

2.3Foralla，b，k∈E，k

R（a，b，k）[k+1：l]∪v∈Vl[R（a，b，k）∩Comp（λ（v），v，R（E））]vb//LimitR（e）

R（a，b，k）[R（a，b，k）]Db//TidyR（e）

3.Repeatstep2untilnoR（u，v，l）inR（E）={R（e）|e∈E}willchangeanymore.

4.IfComp（λ（D），D，R（E））≠，weclaimtheexistenceofasimplepathinG.

Otherwise，weclaimthatthereisnosimplepathinG.

結(jié)論是令人驚異的簡潔：G中存在簡單路徑，當(dāng)且僅當(dāng)Comp（λ（D），D，R（E））≠。

討論一下幾個算子和ZH算法的一些性質(zhì)。

顯然，Comp（λ（v），v，R（E））是λ（v）的子集，Change（R（u，v，l））后得到的R（u，v，l）是修改之前的R（u，v，l）的子集。ZH算法最終肯定會停止，因為每次迭代至少減少一條邊，而邊的總數(shù)受限于|E|。

但是計算是有順序的。比如，點的編號順序不同，邊的編號順序不同，會使得λ（v）和R（u，v，l）中的邊以不同的順序被去掉。不同的計算順序會不會使計算結(jié)果不同？答案是否定的。即計算結(jié)果與順序無關(guān)。

設(shè)ZH算法對于輸入的G=V，E，S，D，L，λ計算到了完全穩(wěn)定。此時算法中所有λ（v）和R（u，v，l）都不能再改變。改變頂點編號和邊的編號，重新按照新的順序開始計算過程。開始時，新的λ（v）和R（u，v，l）都比原來算到穩(wěn)定時的λ（v）和R（u，v，l）包含更多邊。如果新的計算過程第一次出現(xiàn)必須消去某條邊，比如R（u，v，l）需要消去a，b，k，而原來已經(jīng)穩(wěn)定的計算過程沒有消去該邊（形式上，可能a，b，k原來有不同編號），這是不可能的。因為消去a，b，k之前，新的λ（v）和R（u，v，l）一直保持了比原來算到穩(wěn)定時的λ（v）和R（u，v，l）包含更多邊，因此，如果新的λ（v）和R（u，v，l）必須遭受消去a，b，k，原來算到穩(wěn)定時的λ（v）和R（u，v，l）更應(yīng)該消去a，b，k。

這就說明，按照不同的順序計算，一定得到相同的結(jié)果。

定理1.設(shè)|V|表示V的頂點個數(shù)，|E|表示E中邊的條數(shù)。ZH算法的時間復(fù)雜性是|V|*|E|的多項式函數(shù)。

證明首先指出，任意邊集，任意可達路徑集中包含的邊的條數(shù)≤|E|，因為他們都是邊集E的子集；頂點邊集的個數(shù)≤|V|；可達路徑集的個數(shù)≤|E|。

前面已述，計算Comp（ES，v，R（E））的復(fù)雜性為O（|E|3）。計算Change（R（u，v，l））的復(fù)雜性為O（|E|6）?？梢苑治龀鰜聿襟E2.3限制R（e）的復(fù)雜性為O（|E|3）。對步驟3的每次迭代，R（u，v，l）至少減少一條邊。

ZH算法的步驟2是ZH算法中最為復(fù)雜的語句。所以ZH算法的時間復(fù)雜性為|E|*|E|*O（|E|6）。由此證明了ZH算法的時間復(fù)雜性為|V|*|E|的多項式函數(shù)。

定理2.如果G中存在簡單路徑，則一定有Comp（λ（D），D，R（E））≠。

證明設(shè)v0-v1-v2-…-vL是G中一條簡單路徑，v0=S，vL=D。根據(jù)簡單路徑定義，有v0-v1-v2-…-vl∈λ（vl）（1≤l≤L），并且，對路徑v0-v1-v2-…-vL上所有vl-1，vl，l（1≤l≤L），有vl-1，vl，l∈λ（vl）∩…∩λ（vL-1）∩λ（vL）。所以，ZH算法步驟1執(zhí)行完畢，R（vl-1，vl，l）將包含vl-vl+1-…-vL（1≤l≤L）。步驟2之后，R（vl-1，vl，l）仍然包含vl-vl+1-…-vL（1≤l≤L）。步驟3不會截斷R（vl-1，vl，l）中的任何路徑。我們因此知道Comp（λ（D），D，R（E））包含v0-v1-v2-…-vL。

2.3充分性證明準備

我們現(xiàn)在開始證明，如果Comp（λ（D），D，R（E））≠，則G中存在簡單路徑。

2.3.1兩個函數(shù)

為了下面討論需要，引進兩個函數(shù)，一個是換名函數(shù)Ixy，另一個是撕裂函數(shù)Iv1，v2v。兩個函數(shù)都是處理三元組的。一個三元組在我們定義的加標(biāo)多級圖中表示一條邊。建議在后面引理2證明中介紹完撕裂，獲得一些直觀認識后，再細看這里的定義。

換名函數(shù)Ixy.設(shè)EL是一個集合，ET={a，b，k|a，b∈EL，k是一個整數(shù)}，ESET，e∈ET，并且x，y∈EL。Ixy遞歸定義如下：

Ixy（{e}）={b，y，k}，ife=b，x，k

{y，b，k}，ife=x，b，k

{e}，otherwise

Ixy（ES）=∪e∈ESIxy（{e}）

撕裂函數(shù)Iv1，v2v.設(shè)EL是一個集合；ET={a，b，k|a，b∈EL，k是一個整數(shù)}；v，v1，v2∈EL，l是一個整數(shù)；ES，ES1，ES2是ET的子集，ES1≠，ES2≠，ES1∩ES2=，ES1∪ES2={e|e∈ES，e=c，v，l，c∈EL}。Iv1，v2v定義如下：

Iv1，v2v（ES，ES1，ES2）=（ES-{e|e∈ES，e=a，v，lore=v，a，l+1，a∈EL}

∪{e|e=a，v1，l，a，v，l∈ES1，a∈EL}

∪{e|e=a，v2，l，a，v，l∈ES2，a∈EL}

∪{e|e=v1，a，l+1ore=v2，a，l+1，v，a，l+1∈ES，a∈EL}

在Iv1，v2v（ES，ES1，ES2）中，我們從ES中去掉所有三元組a，v，l和v，a，l+1，如果a，v，l∈ES1，用a，v1，l替換a，v，l，如果a，v，l∈ES2，用a，v2，l替換a，v，l，如果v，a，l+1∈ES，用v1，a，l+1和v2，a，l+1替換v，a，l+1。

2.3.2構(gòu)造證明框架

我們還需要兩個符號。

G+：設(shè)G=V，E，S，D，L，λ是一個加標(biāo)多級圖。將G的L-2級的λ（u）都置成λ（u）=λ（u）∪E[3：L]，將G的L-1級的λ（u）都置成λ（u）=λ（u）∪E，由此得到的圖稱為G+。

為了構(gòu)造反駁，我們將ZH算法應(yīng)用兩次。一次將算法應(yīng)用于G，得到一個中間結(jié)果。然后將算法應(yīng)用于G+，并結(jié)合剛才得到的中間結(jié)果，得到最終結(jié)果。根據(jù)最終結(jié)果，我們推斷G中簡單路徑的存在性。為了方便提及，我們將ZH算法應(yīng)用兩次的這個過程稱作ProvingAlgorithm。證明算法的輸入包括圖G=V，E，S，D，L，λ以及任意的一個邊集ESS（ESSE）。為了簡化討論，我們討論的圖需要滿足一些性質(zhì)。對不滿足這些性質(zhì)的圖，算法將停機。因為反駁中必須有新的實例構(gòu)造，而新的構(gòu)造同樣必須具備這些性質(zhì)，為了討論中不會遺漏的原因，我們將這些性質(zhì)全部列在證明算法中。

請別糾結(jié)ProvingAlgorithm的復(fù)雜性。實際上，ProvingAlgorithm是一個不同于ZH算法的算法。這兩個算法各自花費代價做各自的事情。ZH算法解決給定的加標(biāo)多級圖中簡單路徑存在性問題，而ProvingAlgorithm解決另外一個問題：給定G=V，E，S，D，L，λ以及任意的一個邊集ESS，ESSE，G中有簡單路徑包含于ESS嗎？

ProvingAlgorithm只做充分性判斷。算法依據(jù)它形成的判據(jù)Comp（ESS1，D，R（E））非空做出G中有簡單路徑包含于ESS的回答，否則，算法不做回答。就像你下網(wǎng)捕魚，發(fā)現(xiàn)網(wǎng)中有魚，你說水中有魚，沒有發(fā)現(xiàn)網(wǎng)中有魚，你不對水中有魚做任何推斷。ProvingAlgorithm可能漏判，但我們證明它絕不誤判。

ProvingAlgorithm

1.FortheinputgraphGandESS，checkifitis：（1.1）v-w-D∈[ESS]DSifλ（w）∩ESScontainsanedgea，b，2forallv-w-D；（1.2）λ（D）=E；（1.3）Thereexistonlyonevertexatstage2；（1.4）λ（v）[1：2]=E[1：2]forallvexceptthoseatstageL-1；（1.5）ForESSandeachλ（v），ifitcontainsanedgea，b，k，itcontainsalla，*，k（a，*，kmeansalledgesstartingfromvertexa）；（1.6）d（v）=1forallvatstageL-1.（Where，d（v）istheindegreeofv）endprint

Ifnot，westopalgorithm.

2.ApplyZH＼step4onG.

3.BasedonallR（e）safterstep2：ESS1ESS∩Comp（λ（D），D，R（E））∪ESS[1∶2].

4.IfthereexistasimplepathinG，wedostep4tochangeG+：WefindoutallsimplepathP′=S-b1-…-bL-1-DinG，P′hasbiggestk（2≤k≤L）suchthatb2-…-bk∈ESS.Thenwesetλ（x）[1：2]=（E-ESS）[1：2]inG+ifx∈αandλ（x）[1：2]=BinG+ifx∈β.Westopalgorithmifk≠L-2.

Where，α={y|y=aL-1，S-b1-…-bL-1-DisasimplepathinGsuchthatb2-…-bk∈ESS，bi-ai+1-…-aL-1isapathinG，2

5.ApplyZH＼step4onG+.

6.BasedonallR（e）safterstep5：

IfComp（ESS1，D，R（E））≠，thereexistsasimplepathSPinGsuchthatESScontainsSP.

算法中‘setλ（x）[1：2]=（E-ESS）[1：2]是指將λ（x）中第1級和第2級的部分用（E-ESS）[1：2]替換。這意味著λ（x）中沒有了ESS[1：2]中的邊?！畇etλ（x）[1：2]=B是指λ（x）中第1級和第2級的部分用B替換。

ESS1是ESS的子集。除了保持住ESS[1：2]，ESS1[3：L]=ESS[3：L]∩Comp（λ（D），D，R（E））[3：L]。

步驟4的目的是限制G+中L-1級的λ（x）的λ（x）[1：2]。根據(jù)G+的構(gòu)造，本來λ（x）[1：2]=E[1：2]。我們需要選取這樣的簡單路徑P′，依據(jù)他們將G的L-1級的點劃分成α和β兩個集合，依據(jù)α和β修改G+的L-1級的λ（x）的λ（x）[1：2]：P′有最大的k使得k以下部分在ESS中。為方便，稱P′為最大k路徑。步驟4是有條件地執(zhí)行的。如果G中沒有簡單路徑，步驟4不會執(zhí)行。如果G中有簡單路徑，當(dāng)然會有最大k路徑。最大k路徑可能不止一條。

如果[ESS]DS=，必然有Comp（ESS1，D，R（E））=。所以不妨認為[ESS]DS≠。結(jié)合步驟（1.3）和（1.5）定義的性質(zhì)，ESS必然包含第3級所有邊。由此可假定，對所有最大k路徑有k>2。

因為G+是G中L-1級和L-2級的頂點邊集擴展成全集得到的圖，所以，對于將ZH算法應(yīng)用于G得到的中間結(jié)果ESS1，將ZH算法應(yīng)用于G+顯然同樣能夠得到，將ZH算法應(yīng)用兩次意義何在？G+是對G的L-1和L-2級的頂點邊集的“松弛”。為什么松弛？后面將看到，松弛對引理2的證明至關(guān)重要。引理2的結(jié)論（4）證明時，我們有針對性的解釋為什么“松弛”。

幾個概念再次明確一下。算法執(zhí)行中會修改λ（v），λ（v）中保留的值與初始的值一般是不同的。簡單路徑的定義基于初始值而不是計算值。證明算法步驟6中推斷存在的簡單路徑，是一條包含于ESS的簡單路徑。

2.4αβ引理及其證明

現(xiàn)在給每個G=V，E，S，D，L，λ定義一個度量。

f（G）=∑v∈VL-2（d（v）-1）。其中，d（v）是v的入度，VL-2是L-2級所有頂點的集合。

我們可以直接驗證ProvingAlgorithm對于所有6級圖能夠做出正確推斷（證明與下面引理1完全相同）。假定ProvingAlgorithm對于所有小于等于L-1級的圖都能做出正確推斷，但是對于L級的圖不能正確推斷。在所有L級圖中必有使算法不正確且f（G）最小的G。我們下面證明，這樣的G不存在。

引理1.設(shè)G=V，E，S，D，L，λ和ESS是ProvingAlgorithm的輸入，G中第3級到L-1級沒有多入度點，如圖2所示。如果Comp（ESS1，D，R（E））≠，則G有簡單路徑SP且ESS包含SP。

證明因為一定有S-a-b∈Comp（ESS1，D，R（E））并且R（a，b，2）∩Comp（ESS1，D，R（E））包含b-a3-…-aL-1-D，λ（aL-1）必然包含S-a-b。否則，B=∩y∈βλ（y）[1：2]不包含S-a-b，因而不可能有R（a，b，2）∩Comp（ESS1，D，R（E））包含b-a3-…-aL-1-D。所以，S-a-b-a3-…-aL-1-D就是G中包含于ESS的簡單路徑。

引理2.設(shè)G=V，E，S，D，L，λ和ESS是ProvingAlgorithm的輸入，頂點v是G中L-2級的一個多入度點，G中L-1級沒有多入度點，如圖3（a）所示。如果Comp（ESS1，D，R（E））≠，則G有簡單路徑SP且ESS包含SP。

證明引理2的證明思想是，構(gòu)造一個新的L-1級圖G1滿足三個條件，從而完成證明：

（1）G1具備步驟1描述的性質(zhì)，并且f（G1）

（2）如果G作為輸入時Comp（ESS1，D，R（E））≠，G1作為輸入時同樣有Comp（ESS1，D，R（E））≠。

（3）如果P是G1的簡單路徑且包含于ESS，P（經(jīng)過適當(dāng)改變）是G的簡單路徑且包含于ESS。

為此，我們將圖3（a）撕裂成另外一個圖，如圖3（b）所示。既然要構(gòu)造另外一個加標(biāo)多級圖，當(dāng)然，我們需要給每個點配置相應(yīng)的邊集，同時構(gòu)造新的ESS，這樣，當(dāng)新的圖和新的ESS作為算法輸入時，我們同樣會得到一個計算結(jié)果Comp（ESS1，D，R（E））?？梢越⒁粋€序關(guān)系，使得f（G1）

我們將λ（v1）和λ（v2）重復(fù)設(shè)置，除了換名，本質(zhì)上都等于λ（v）。同樣地，λ（w1）和λ（w2）重復(fù)設(shè)置，除了換名，本質(zhì)上都等于λ（w）。新的ESS，除了換名，本質(zhì)上也等于原來的ESS。因為在MSP問題中，一個點的頂點邊集實際上是一種控制，重復(fù)設(shè)置相當(dāng)于相同的控制。設(shè)想中國曾經(jīng)有兩湖省，左路從湖南來，右路從湖北來，現(xiàn)在分置成湖南省和湖北省，湖南管左路，湖北管右路。這種控制關(guān)系實質(zhì)上不是一回事嗎？圖3右圖中的一條包含于新的ESS的簡單路徑“實質(zhì)上”就是圖3左圖中的一條包含于原來的ESS的簡單路徑。

困難來了。以上初始設(shè)置是容易的。但是，如果原來Comp（λ（v），D，R（E））非空，現(xiàn)在，以新的圖為輸入，Comp（λ（v1），D，R（E））和Comp（λ（v2），D，R（E））會非空嗎？精確地說，就算賦予本質(zhì)上相同的值，撕裂不會影響計算結(jié)果嗎？或者說，要確保本質(zhì)相同的計算結(jié)果，我們能夠?qū)D撕開嗎？

算子4為這個目的產(chǎn)生，它主要出于一種邏輯證明的需要，而不是簡單地由直覺得到。如何通過一種計算，探測到圖中的一種性質(zhì)，然后使得我們可以確認，對于撕裂前后的圖，ProvingAlgorithm能夠得到本質(zhì)上相同的結(jié)果，就是算子4設(shè)計的方向指導(dǎo)。我們的方向非常明確和堅定，就是尋找一個算法實現(xiàn)以下目標(biāo)：如果對于給定的圖G，算法能夠得到一個結(jié)果，那么，希望算法在一個“更小”的圖上，能夠得到本質(zhì)相同的結(jié)果。“更小”的圖上一個存在的答案，本質(zhì)上就是原來圖中的答案！

下面開始證明引理2。不失一般性，假定d（v）=2并且v的出度也等于2。這意味著G中只有v-w-D和v-w′-D。

將以v為終點的邊分成非空的兩個部分，即group1和group2，自底向上將v撕裂成v1，v2。然后逐個撕裂L-1級的多入度點。因此得到一個L-1級沒有多入度點、L-2級d（v1）+d（v2）=d（v）的圖G1，如圖3（b）所示。

頂點邊集和ESS定義如下：

令V1=（V-{v，w，w′}）∪{v1，v2}∪{w1，w2，w3，w4}。

令E1=Iw1，w2w（Iw3，w4w′（Iv1，v2v（EofG，group1，group2），{v1，w′，L-1}，{v2，w′，L-1}），{v1，w，L-1}，{v2，w，L-1}）。

令（ESS1ofG1）=Iw1，w2w（Iw3，w4w′（Iv1，v2v（ESSofG，group1，group2），{v1，w′，L-1}，{v2，w′，L-1}），{v1，w，L-1}，{v2，w，L-1}）。

（記號說明：（ESSofG1）表示G1為輸入時的ESS。本論文中經(jīng)常要比較G為輸入時的某個量和G1為輸入時的某個量。為了方便和清晰的表示，我們用‘（somethingofG）表示G為輸入時的某個量，用‘（somethingofG1）表示G1為輸入時的某個量。（ESSofG）就是這種表示形式的一個例子）

對于除v1、v2、w1、w2、w3、w4外的每個x，令（λ（x）ofG1）=Iw1，w2w（Iw3，w4w′（Iv1，v2v（λ（x）ofG，group1，group2），{v1，w′，L-1}，{v2，w′，L-1}），{v1，w，L-1}，{v2，w，L-1}）。

對于x=v1、v2、w1、w2、w3、w4，給（λ（x）ofG1）賦一個值，使得

Iw4w′Iw3w′Iw2wIw1wIv2vIv1v（λ（v1））=

Iw4w′Iw3w′Iw2wIw1wIv2vIv1v（λ（v2））=λ（v），

Iw4w′Iw3w′Iw2wIw1wIv2vIv1v（λ（w1））=

Iw4w′Iw3w′Iw2wIw1wIv2vIv1v（λ（w2））=λ（w），

Iw4w′Iw3w′Iw2wIw1wIv2vIv1v（λ（w3））=

Iw4w′Iw3w′Iw2wIw1wIv2vIv1v（λ（w4））=λ（w′）。

（說明：比如，撕裂λ（v），將結(jié)果賦給λ（v1）和λ（v2），撕裂λ（w），將結(jié)果賦給λ（w1）和λ（w2），撕裂λ（w′），將結(jié)果賦給λ（w3）和λ（w4）。

顯然，對于所有x，Iw4w′Iw3w′Iw2wIw1wIv2vIv1v（λ（x））λ（x）。如果P是G1的簡單路徑，Iw4w′Iw3w′Iw2wIw1wIv2vIv1v（P）是G的簡單路徑）

如果[ESSofG]Dv≠，對于每條邊u，vi，L-2∈λ（vi）（i=1，2），在G1中增加包含u，vi，L-2的簡單路徑P=S-…-u-vi-w-D，并使λ（w）[1：2]=E1[1：2]，P上第2級頂點是G1中的那個唯一頂點，但僅擴展（ESSofG1）使（ESSofG1）包含P[L-1：L]。

（說明：[ESSofG]Dv≠，意味著[ESSofG]Dvi≠。增加包含u，vi，L-2的簡單路徑P可以確保（ESS1ofG1）包含P[L-1：L]。這樣做，沒有破壞步驟1定義的性質(zhì)，沒有在G1中增加包含于（ESSofG1）的簡單路徑，也沒有增加最大k路徑，從而影響以G1為輸入時產(chǎn)生的α集。但是增加了（Comp（ESS1，D，R（E））ofG1）實質(zhì)上包含不少于（Comp（ESS1，D，R（E））ofG）的邊的可能性）

對于G1中的S-a-b，增加S-aa-b并擴展G1中所有λ（x）使λ（x）包含S-aa-b。

（說明：因為有可能L-1級的某些λ（x）中包含的第1級和第2級的邊需要去掉（請繼續(xù)看下面的討論），所以，在所有λ（x）中額外增加兩條邊S-aa-b。因為所有λ（x）中增加了這兩條邊，這兩條邊可以參加到需要S-a-b參加的所有計算過程。但是我們沒有在（ESSofG1）中增加S-aa-b，因此沒有在G1中增加包含于（ESSofG1）的簡單路徑）endprint

如果（ESSofG1）不包含u，vi，L-2（i=1，2），λ（wj）∩（ESSofG）包含S-a-b（j=1，2，3，4），vi，wj，L-1是G1的邊：去掉λ（wj）中的S-a-b（說明：這是步驟（1.1）定義的性質(zhì)的要求，G1必須滿足。因為此種情況下，[[ESSofG1]DS]Dvi=）。如果G1中有簡單路徑且S-b1-…-bL-1-D是一條最大k路徑，G1中增加b3到u的路徑。

（說明：僅僅增加從b3到u的路徑，不會使得G1中增加包含于（ESSofG1）的簡單路徑。如果L>7，λ（u）可以不包含這條路徑上的第5級的邊。如果L=7，b3到u的路徑只有一條邊，λ（u）可以不包含任何從b3出發(fā)的邊。如果有，也可以去掉。這樣處理后，G1滿足步驟（1.5）定義的性質(zhì)的要求。

增加從b3到u的路徑，使得我們可以迫使wj進入α集合，確保λ（wj）中去掉S-a-b后不會使得（∩y∈βλ（y）[1：2]ofG1）變小，確保（∩y∈βλ（y）[1：2]ofG1）（∩y∈βλ（y）[1：2]ofG））。

如果（ESSofG1）包含u，vi，L-2（i=1，2）、vi，wj，L-1是G1的邊，但沒有最大k路徑經(jīng)過u，vi，L-2，令λ（wj）[1：2]=E1[1：2]，并擴展（ESSofG1）包含vi-wj-D。

（說明：因為此種情況下，如果原來w屬于α集合，wj可能脫離α集合進入β集合，所以我們擴大λ（wj）[1：2]，以確保（BofG1）（BofG）。由于步驟（1.1）定義的性質(zhì)要求，擴大λ（wj）[1：2]，迫使我們必須同時擴展（ESSofG1）使其包含vi-wj-D。但是，因為沒有最大k路徑經(jīng)過u，vi，L-2，故擴大λ（wj）[1：2]不會導(dǎo)致G1中增加包含于（ESSofG1）的簡單路徑。為了確保[[ESSofG1]DS]Dvi≠，設(shè)第2級的唯一頂點為f，可以在G1中增加從f到u的路徑，但使該路徑不可能在簡單路徑上（令該路徑上第3級的點的頂點邊集等于E1[1：2]即可，這是可以做到的，因為L>6），同時（ESSofG1）增加該路徑）

因此完成G1構(gòu)造以及頂點邊集和ESS定義，得到一個L-1級沒有多入度點、L-2級d（v1）+d（v2）=d（v）的圖G1，如圖3（b）所示。

總結(jié)一下G1的構(gòu)造：如果不考慮換名，G1中包含于ESS的簡單路徑與G中包含于ESS的簡單路徑是一樣的。即使增加了路徑，增加的多入度點不在L-2級和L-1級。第2級仍然只有一個點。步驟1定義的性質(zhì)仍然被保持。如果G1的L-1級某個點的λ（x）[1：2]可能減少，x進入α。如果G1的L-1級某個點x不在最大k路徑上，λ（x）[1：2]獲得最大增加，使得x即使進入β也不會使（∩y∈βλ（y）[1：2]ofG1）減少。

現(xiàn)在，將構(gòu)造的G1和（ESSofG1）作為的輸入進行計算?？梢宰C明以下結(jié)論（1）、（2）、（3）、（4）、（5）。

（1）f（G1）

v是出現(xiàn)在l級的多入度點，l=L-2。G1可能增加了路徑，但多入度點在于L-3級。

∑u∈VlofG1（d（u）-1）=∑u∈（Vl-{v1，v2}）ofG1（d（u）-

1）+（d（v1）-1）+（d（v2）-1）=∑u∈（Vl-{v}）ofG

（d（u）-1）+（d（v）-1）-1=∑u∈VlofG（d（u）-1）-1

因此f（G1）

（2）對G中L-1級的每個λ（w），如果步驟2之后λ（w）包含邊e=a，b，k，G一定包含經(jīng)過邊a，b，k和點w的半簡單路徑。

為不影響對整體思路的理解，將證明附在本引理2的尾部。

結(jié)論（2）非常重要。因為G有半簡單路徑經(jīng)過邊a，b，k和點w，又因為λ（D）=E，這條半簡單路徑實際上是簡單路徑。撕裂之后，這條半簡單路徑必然在λ（w1）或者λ（w2）中。因此，當(dāng)G1作為ProvingAlgorithm輸入，步驟2結(jié)束時，λ（w1）或者λ（w2）中必然包含這條半簡單路徑。如果a，b，k曾經(jīng)進入（ESS1ofG），a，b，k必將進入（ESS1ofG1）。由此導(dǎo)致Iw4w′Iw3w′Iw2wIw1wIv2vIv1v（ESS1ofG1）（ESS1ofG）。（實際上，嚴格地說，我們只有Iw4w′Iw3w′Iw2wIw1wIv2vIv1v（ESS1ofG1）[1：L-2]（ESS1ofG）[1：L-2]。從vi到D的路徑上的邊，可能會是新增加的簡單路徑上經(jīng)過的L-2和L-1級邊，換名是不能換成v-w-D的，請見G1的構(gòu)造。但是這兩條邊可以代替v-w-D幫助我們完成（Comp（ESS1，D，R（E））ofG1）的計算，所以我們不加區(qū)分地認為Iw4w′Iw3w′Iw2wIw1wIv2vIv1v（ESS1ofG1）（ESS1ofG））

（3）G1具備步驟1所列性質(zhì)，并且，G有簡單路徑的情況下，（BofG1）[1：2]（BofG）[1：2]。

根據(jù)G1的構(gòu)造，G1顯然具備步驟1所列性質(zhì)。理由如下。

如果G1中沒有簡單路徑，此時當(dāng)然G中也沒有簡單路徑：如果L-1級某個λ（x）可能破壞步驟（1.1）定義的性質(zhì)，我們?nèi)サ袅似渲械腟-a-b，改用不屬于（ESSofG1）的S-aa-b替換。步驟（1.2）、（1.3）、（1.4）的性質(zhì)沒有觸及過。撕裂不改變步驟（1.5）的性質(zhì)。撕裂L-2級頂點后，緊跟著撕裂由撕裂L-2級的點帶來的L-1級的多入度點就是為了保持步驟（1.6）定義的性質(zhì)。

如果G1中有簡單路徑，此時當(dāng)然G中也有簡單路徑：如果L-1級某個λ（x）可能破壞步驟（1.1）定義的性質(zhì)，我們?nèi)サ袅似渲械腟-a-b，改用不屬于（ESSofG1）的S-aa-b替換。只要保證λ（D）對所有增加的路徑的包含，（1.2）的性質(zhì)自然滿足?？赡茉黾拥哪菞l路徑的第2級的點就是原來第2級的點，（1.3）的性質(zhì)自然滿足。（1.4）的性質(zhì)可以滿足，只要增加的路徑上的頂點邊集多包含第1級和第2級的邊即可。（1.5）的性質(zhì)在增加路徑時被保持。撕裂L-2級頂點后，緊跟著撕裂由撕裂L-2級的點帶來的L-1級的多入度點就是為了保持（1.6）定義的性質(zhì)。

G1有簡單路徑的情況下，此時當(dāng)然G中也有簡單路徑，因為我們迫使wj進入α集合，或者擴展了λ（wj）[1：2]（請見G1的構(gòu)造），因此，（BofG1）[1：2]（BofG）[1：2]。

（4）將證明算法作用于G1，（Comp（ESS1，D，R（E））ofG1）≠。

首先，根據(jù)結(jié)論（2），證明算法步驟4之前，Iw4w′Iw3w′Iw2wIw1wIv2vIv1v（ESS1ofG1）（ESS1ofG）。

步驟3之后，如果G1沒有簡單路徑（此時當(dāng)然G中也沒有簡單路徑），L-1級和L-2級的所有λ（v）被擴展成包含E中所有邊（即G+）。如果G1有簡單路徑（此時當(dāng)然G中也有簡單路徑），L-1級和L-2級的所有λ（v）被擴展成包含E[3：L]中所有邊，并且（BofG1）[1：2]（BofG）[1：2]。

因此，對所有a，b，k（k

對所有u，v，L-2，如果（R（u，v，L-2）ofG）包含v-w-D并且u，v，L-2∈group1，（R（u，v1，L-1）ofG1）包含v1-w1-D；如果（R（u，v，L-2）ofG）包含v-w-D并且u，v，L-2∈group2，（R（u，v2，L-1）ofG1）包含v2-w2-D。

因此，Iw4w′Iw3w′Iw2wIw1wIv2vIv1v（Comp（ESS1，D，R（E））ofG1）（Comp（ESS1，D，R（E））ofG）≠。

（對于S-a-b，需要證明（R（a，b，2）ofG1）不受某些點由β集合中的點變成α集合中的點的影響。由于圖具備步驟（1.4）定義的性質(zhì)，這是可以推斷的。但最簡單的辦法是將步驟6中“BasedonallR（e）safterstep5”修改成“BasedonallR（u，v，k）（k>2）afterstep5andR（u，v，k）（k≤2）afterstep1instep5”：由于步驟5中間有三步，其中第1步是計算所有R（e）的初值，然后反復(fù)修改R（e）。步驟6計算（Comp（ESS1，D，R（E））ofG1）時，對于R（a，b，k），若k≤2，我們可以用步驟5中計算得到的R（e）的初值。這個值當(dāng)然比步驟5結(jié)束時的R（e）“大”，而且不受某些點由β集合中的點變成α集合中的點的影響）

（5）G有簡單路徑SP且ESS包含SP。

已經(jīng)假定G是使證明算法不正確的最小的圖，而f（G1）

如果SP是G1中的簡單路徑，P′=Iw4w′Iw3w′Iw2wIw1wIv2vIv1v（SP）必為G中的簡單路徑。

引理2之結(jié)論（2）的證明

我們證明，對G中L-1級的每個λ（w），如果步驟2之后λ（w）包含邊e=a，b，k，G一定包含經(jīng)過邊a，b，k和點w的半簡單路徑。

這個結(jié)論的證明是本文最重要最漂亮的亮點。算子4以及本結(jié)論的證明是我們能夠完成證明的關(guān)鍵。

我們現(xiàn)在唯一知道的是，將L級加標(biāo)多級圖G′以及邊集ESS′作為ProvingAlgorithm的輸入，如果f（G′）

所以，我們基于G1構(gòu)造一個G2，確保f（G2）

令V2=V1，E2=E1。

對于L-1級和L-2級之外的所有頂點x，令（λ（x）ofG2）=（λ（x）ofG1）。

對于L-1級和L-2級的所有頂點x，令（λ（x）ofG2）=E2。

令（ESSofG2）=Iv1，v2v（（λ（w）∩λ（v）[1：L-2]ofG）-（{e|e=a1，b1，k，a1≠a}∪{e|e=a1，b1，k+1，a1≠b}），group1，group2）∪E2[L-1：L]。

設(shè)第2級唯一頂點為f，對E2[L-2：L-2]中的每條邊a，b，L-2，在G2中增加f到a的路徑f-…-x-a，并令λ（x）=E2[1：2]。同時，在（ESSofG2）中增加包含f-…-x-a-b，確保[ESSofG2]DS包含E2[L-1：L]中的邊，使構(gòu)造的G2滿足步驟（1.1）定義的性質(zhì)，并且S-…-x-a不在簡單路徑上。

再增加一條簡單路徑P=S-…-w-D，除S、D，以及第2級的點，其余頂點都是全新增加的。從第3級到第L-1級都是單入度點，使λ（w）不包含（ESSofG2）[1：2]中的邊，使所有頂點邊集取值服從步驟（1.2）、（1.3）、（1.4）、（1.5）、（1.6）定義的性質(zhì)要求，僅僅使得P[3：L-2]∈（ESSofG1）。

（說明：令A(yù)1=（λ（w）∩λ（v）[1：L-2]ofG）-（{e|e=a1，b1，k，a1≠a}∪{e|e=a1，b1，k+1，a1≠b}），A2=（Comp（λ（w），w，R（E））ofG）-{a1，b1，k|a1，b1，k≠a，b，k}，A1比A2包含更多邊。但是，前者滿足步驟（1.5）定義的性質(zhì)，后者不滿足步驟（1.5）定義的性質(zhì)。其實我們下面關(guān)心的是A2。

可以假定G2除了增加的那條簡單路徑外，沒有k=L-2的最大k路徑。否則G2已經(jīng)有簡單路徑包含于（ESSofG2），本結(jié)論（2）已經(jīng)成立。因為不確定G2有否簡單路徑，所以增加一條簡單路徑，使得ProvingAlgorithm必然執(zhí)行步驟4。而增加的這條簡單路徑是一條k=L-2的最大k路徑，于是最大k路徑必然取增加的這條簡單路徑。

后面這句話有點難懂。增加的這條最大k路徑還有一個作用。必要的話，可以通過增加從最大k路徑上第3級的頂點到G2的L-3級頂點的路徑。因為L>6，這是可以增加的。改變的也僅僅是L-3級的頂點的入度，不影響f（G2）。這樣可以迫使邊集A2中的邊關(guān)聯(lián)的L-1級頂點之外的那些L-1級頂點進入α集，而進入α集的那些L-1級頂點的邊集包含的第1級和第2級邊，可以沒有（ESSofG2）[1：2]的邊，因而那些點不在包含于（ESSofG2）的簡單路徑上，但（ESS1ofG2）[3：L]不會因此變少。（不這樣做，可能會有半簡單路徑包含于A1而不包含于A2））

得到的圖如圖3（b）所示。增加的簡單路徑上的第L-2級的點是單入度點，所以，f（G2）=f（G1）。

將證明算法作用于G2，我們有以下（a）、（b）、（c）、（d）4個結(jié)果：

（a）（BofG2）=E2[1：2]。

按照G2的構(gòu)造，開始的時候，除新增加的簡單路徑上的頂點外，對于L-1級和L-2級的所有頂點x，（λ（x）ofG2）=E2。

另一方面，因為最大k路徑只能是新增加的那條簡單路徑，所以，α包含點w以及那些被迫使進入α的L-1級頂點，對L-1級的x∈β，（λ（x）ofG2）=E2，所以，B=E2[1：2]。

結(jié)論（a）告訴我們，對于G+2的L-1級的頂點x，若x∈β，λ（x）[1：2]=E2[1：2]。

（b）G2具備步驟1所列性質(zhì)。

根據(jù)G2的構(gòu)造，可以逐條核對，G2顯然具備步驟（1.1）到（1.6）所列性質(zhì)。

（c）（Comp（ESS1，D，R（E））ofG2）≠。

先總結(jié)G+2中L-1級和L-2級所有λ（x）的取值。對于A2中的邊關(guān)聯(lián)的L-1級和L-2級所有x，λ（x）等于E2；對于A2中的邊關(guān)聯(lián)的L-1級和L-2級頂點之外的x，λ（x）[3：L]等于E2[3：L]。因為我們增加的S-aa-b可以替代S-a-b參加所有計算（請見G1的構(gòu)造，G2是在G1的基礎(chǔ)上修改得到），就（Comp（ESS1，D，R（E））ofG2）的計算而言，可以不加區(qū)分的認為G+2中L-1級和L-2級所有λ（x）的取值E2。

（ESSofG2）Iv1，v2v（（Comp（λ（w），w，R（E））ofG）-{a1，b1，k|a1，b1，k≠a，b，k}，group1，group2）∪E2[L-1：L]；尤其重要的是，（Comp（[{e|e=c，d，kk∈E，kk

我們詳細說明一下為什么（Comp（ESS1，D，R（E））ofG2）≠。

將Iv1，v2v（（Comp（λ（w），w，R（E））ofG）-{a1，b1，k|a1，b1，k≠a，b，k}，group1，group2）∪E2[L-1：L]賦予（ESSofG2），其中，（Comp（λ（w），w，R（E））ofG）是以G為ProvingAlgorithm的輸入時步驟2結(jié)束后，λ（w）中的結(jié)果。

計算（Comp（ESS1，D，R（E））ofG2）之前，R（E）是基于G+2得到的，此時，L-1級和L-2級所有λ（x）都等于E2。頂點邊集是全集，意味著對R（E）的計算不會產(chǎn)生任何阻擋。

分5步看。

第一步，將眼光放在G上，因為步驟2的迭代已經(jīng)穩(wěn)定，如果將（Comp（λ（w），w，R（E））ofG）再算一遍（Comp（λ（w），w，R（E））ofG），不會有任何改變。

第二步，還是將眼光放在G上，將（Comp（λ（w），w，R（E））ofG）中邊a，b，k所在級，除a，b，k之外的其他邊去掉，得到集合A=（Comp（λ（w），w，R（E））ofG）-{a1，b1，k|a1，b1，k≠a，b，k}?；诋?dāng)前的R（E），再計算（Comp（A，w，R（E））ofG），可以斷定（Comp（A，w，R（E））ofG）≠，這是算子4保證的。因為，（Comp（[{e|e=c，d，kk∈E，kk

第三步，將G的L-1級和L-2級的頂點邊集都換成全集，還是對上一步的A，R（E）不變，再算一次（Comp（A，w，R（E））ofG），可以斷定（Comp（A，w，R（E））ofG）≠。

第四步，將G撕裂成G2。因為G的L-1級和L-2級的頂點邊集都換成了全集，撕裂不會影響R（E）的計算。撕裂后，實際上得到的是G+2，L-1級和L-2級所有λ（x）都等于E2，所以，ProvingAlgorithm的步驟5后得到的R（E）與上面第三步得到的R（E），除了換名，本質(zhì)上一樣。

第五步，此時，在G2上計算（Comp（ESS1，D，R（E））ofG2），相當(dāng)于第三步計算（Comp（A，w，R（E））ofG）。所以，（Comp（ESS1，D，R（E））ofG2）≠。

（d）f（G2）

f（G2）=f（G1）而f（G1）

基于（a）、（b）、（c）、（d），我們可以推斷G2中存在簡單路徑PP且（ESSofG2）包含PP。由于a，b，k是（ESSofG2）中第k級的唯一邊，因此a，b，k必在PP上。

設(shè)PP在L-3級的點為u。由于PP在（ESSofG2）中，必有路徑u-vi-wj-D在（ESSofG2）中。另一方面，根據(jù)（ESSofG2）的定義，PP[1：L-3]∈λ（wj）∩λ（vi），u，*，L-2∈λ（wj）∩λ（vi），所以，PP[1：L-3]//u-vi-wj-D（表示兩條路徑連接一起，去掉一個重復(fù)的頂點u）構(gòu)成包含于（ESSofG2）的簡單路徑（vi和wj的有些組合不構(gòu)成G2的邊，這里只考慮可以構(gòu)成邊的組合）。

Iw4w′Iw3w′Iw2wIw1wIv2vIv1v（PP[1：L-3]//u-vi-wj-D）[1：L-1]就是我們關(guān)心的半簡單路徑。

結(jié)論（2）因此得證。

（a）（b）

圖4Typicalgraphoflemma3

引理3.設(shè)G=V，E，S，D，L，λ和ESS是ProvingAlgorithm的輸入，v是G中l(wèi)級的一個多入度點，2

證明引理3的證明思想是，構(gòu)造一個新的圖G1滿足三個條件，從而完成證明：

（1）G1具備步驟1描述的性質(zhì)，并且G1是一個L-1級圖。

（2）如果G作為輸入時Comp（ESS1，D，R（E））≠，G1作為輸入時同樣有Comp（ESS1，D，R（E））≠。

（3）如果P是G1的簡單路徑且包含于ESS，P本質(zhì)上是G的簡單路徑且包含于ESS。

傳統(tǒng)的歸納證明是通過去點或者去邊構(gòu)造更小的圖。引理2證明的時候，我們很難找到這樣構(gòu)造更小的圖的方法。所以我們采用撕裂，不是去點，而是復(fù)制更多點，完成了引理2的證明。引理3的證明可以回歸傳統(tǒng)證明方法了。

去掉G中L-2級所有點，我們構(gòu)造一個L-1級圖G1=V1，E1，S，D，L-1，λ，如圖4（b）所示：

1.G1的頂點：V1=（VofG）-（VL-2ofG）。其中，VL-2表示圖G的L-2級頂點的集合。

2.G1的邊，即E1：如果kL-1，g1，g2，k-1變成G1的邊。如果c，b，L-2和b，w，L-1是G的邊，c，w，（L-1）-1是G1的邊。

3.G1的頂點邊集，以及（ESSofG1）：

對所有w∈V1，如果w在k級，k=（L-1）-1：

令（λ（w）ofG1）=（（Comp（λ（w），w，R（E））ofG）-E[L-2：L-1]）∪{e|e=c，w，（L-1）-1，存在b使得c，b，L-2∈（λ（w）ofG）并且b，w，L-1∈（λ（w）ofG）}∪（λ（w）ofG）[1：2]。

（這樣設(shè)置的λ（w）是我們實質(zhì)上關(guān)心的內(nèi)容，兩級控制合并成由（λ（w）ofG1）統(tǒng)一控制。但是形式上可能不滿足步驟（1.5）定義的性質(zhì)。為了形式上滿足步驟（1.5）定義的性質(zhì)要求，我們可以這樣設(shè)置（λ（w）ofG1）的值：如果（Comp（λ（w），w，R（E））ofG）為空，可以令（λ（w）ofG1）為空。否則，設(shè)b，w，L-1是G中的邊，我們令（λ（w）ofG1）=（（λ（w）ofG）∩（λ（b）ofG）-E[L-2：L-1]）∪{e|e=c，w，（L-1）-1，存在b使得c，b，L-2∈E并且b，w，L-1∈E}∪（λ（w）ofG）[1：2]。這樣就滿足步驟（1.5）定義的性質(zhì)了）

對所有x∈V1，如果x在k級，k=L-1：令（λ（x）ofG1）=E1。

對所有x∈V1，如果x在k級，k<（L-1）-1：令（λ（x）ofG1）=（λ（x）ofG）[1：k]。

令（ESSofG1）=（（ESSofG）-E[L-2：L-1]）∪{e|e=c，w，（L-1）-1，存在b使得c，b，L-2∈（ESSofG）并且b，w，L-1∈（ESSofG）}。（說明：為了滿足步驟（1.5）定義的性質(zhì)，必要時可增加（L-1）-1級的邊，同時去掉L-1級的邊）

4.修改邊集

對G中所有g(shù)1，g2，k，如果（λ（x）ofG1）包含g1，g2，k并且g1，g2，k已經(jīng)變成G1的g1，g2，k-1，用g1，g2，k-1替換（λ（x）ofG1）中的g1，g2，k。

現(xiàn)在證明以下結(jié)論（1）、（2）、（3）、（4）、（5）。

（1）G1具備步驟1所列性質(zhì)，并且若G有簡單路徑，（βofG1）=（βofG），（BofG1）=（BofG）。

根據(jù)G1的構(gòu)造，G1顯然具備步驟1所列性質(zhì)。

如果G有最大k路徑P=S-a1-…-aL-3-aL-2-aL-1-D，P′=S-a1-…-aL-3-aL-1-D必為G1的最大k路徑。

若某個頂點屬于β集，壓縮G不會使其變成屬于α集。若某個頂點屬于α集，壓縮G不會使其變成屬于β集。因此，G1和G有完全相同的β集，進一步有完全相同的B集。

（2）將證明算法作用于G1，（Comp（ESS1，D，R（E））ofG1）≠。

因為頂點v以上沒有多入度點，壓縮的結(jié)果，只是將兩條鄰接的邊合并成一條邊（例如，c，b，L-2、b，w，L-1變成c，w，（L-1）-1），所以，以G1中為輸入得到的所有的計算結(jié)果，包括所有Comp（λ（x），x，R（E）），以及所有R（e），都與G中為輸入得到相應(yīng)的計算結(jié)果本質(zhì)上相同。所以，由（Comp（ESS1，D，R（E））ofG）≠，知道（Comp（ESS1，D，R（E）））ofG1）≠。

（3）G1有簡單路徑SP且（ESSofG1）包含SP。

因為G1是L-1級圖，G1具備步驟1所列性質(zhì)，同時（Comp（ESS1，D，R（E））ofG1）≠，所以，G1有簡單路徑SP且（ESSofG1）包含SP。

（4）如果G1有簡單路徑P=S-a1-…-aL-3-aL-1-D并且（ESSofG1）包含P，那么，P′=S-a1-…-aL-3-aL-2-aL-1-D一定是G的簡單路徑并且（ESSofG）包含P′。

理由如下：

（ESSofG1）=（（ESSofG）-E[L-2：L-1]）∪{e|e=c，w，（L-1）-1，存在b使得c，b，L-2，b，w，L-1∈（ESSofG）}。因此，（ESSofG1）包含P意味著（ESSofG）包含P′。

（λ（aL-1）ofG1）包含P[1：（L-1）-1]即（λ（aL-1）ofG）∩（λ（aL-2）ofG）包含P′[1：L-1]，因為（λ（w）ofG1）=（（Comp（λ（w），w，R（E））ofG）-E[L-2：L-1]）∪{e|e=c，w，（L-1）-1，存在b使得c，b，L-2、b，w，L-1∈（λ（w）ofG）}。

（5）G有簡單路徑SP且ESS包含SP。

根據(jù)結(jié)論（4），結(jié)論（3）中提到的簡單路徑SP實際上就是G中一條包含于（ESSofG）的簡單路徑。

總結(jié)引理1、引理2、引理3，我們有下面的αβ引理。

αβ引理.設(shè)G=V，E，S，D，L，λ和ESS是ProvingAlgorithm的輸入。如果Comp（ESS1，D，R（E））≠，G有簡單路徑SP且ESS包含SP。

2.5證明ZH算法充分性

定理3.設(shè)G=V，E，S，D，L，λ是一個加標(biāo)多級圖。以G作為ZH算法輸入，如果Comp（λ（D），D，R（E））≠，則G中存在簡單路徑。

證明在G中增加路徑S0-a-S和D-w1-Dnew，令λ（w1）=λ（Dnew）=E∪{S0-a-S，D-w1-Dnew}并且擴展所有頂點邊集包含S0-a-S，我們得到G′。然后，我們令ESS=E∪{S0-a-S，D-w1-Dnew}。G′具備證明算法步驟1所列性質(zhì)。（要滿足步驟（1.5）定義的性質(zhì)，加標(biāo)多級圖定義中也必須對每個λ（v）的取值加限制）

步驟4不會被執(zhí)行，因為可假定G′沒有簡單路徑。否則，設(shè)P為G′的簡單路徑，P[3：L+2]即為G的簡單路徑，定理3得證。

因為ZH算法執(zhí)行結(jié)果有Comp（λ（D），D，R（E））≠，以G′和ESS為證明算法輸入，必有Comp（ESS1，D，R（E））≠。

依據(jù)αβ引理，G′有簡單路徑SP。這意味著SP[3：L+2]是G中的簡單路徑。

3結(jié)論

本文給出了求解MSP問題的一個算法，分析了時間復(fù)雜性，并對算法進行了證明。實際上，我們還對算法進行了實現(xiàn)。大量測試都驗證了算法的正確性。

參考文獻

[1]XinwenJiang.DeterminingtheHPropertyofAGraphbyChangingItintoAMultistageGraph[J].ComputerTechnologyAndAutomation，2004，23（2）：52-54.

[2]XinwenJiang，QiWang，andZihengJiang.ThefourthversionoftheProofforZHAlgorithmtoSolveMSPProblem[J].ComputerTechnologyAndAutomation，2010，29（3）：35-48.

[3]FANS，JIANGXW，PENGLH.PolynomialtimeHeuristicAlgorithmsforSeveralNPcompleteOptimizationProblems[J].JournalofComputationalInformationSystems，2014，10（22）：9707-9723.

（特約專家稿）endprint