許莉，婁定俊，蔣一帆，秦宗蓉

(中山大學(xué)數(shù)據(jù)科學(xué)與計(jì)算機(jī)學(xué)院，廣東 廣州 510006)

Halin圖是由德國(guó)數(shù)學(xué)家Halin提出的極小3連通平面圖。給定一棵樹(shù)T，其內(nèi)部結(jié)點(diǎn)度數(shù)至少為3，即樹(shù)中無(wú)度數(shù)為2的結(jié)點(diǎn)。將T嵌入到一個(gè)平面中，然后添加一些依次連接T的葉結(jié)點(diǎn)的邊來(lái)組成一個(gè)圈C，同時(shí)使得添加邊后的圖仍然是平面圖。由此得到的G=T∪C即為Halin圖，其中T稱為G的特征樹(shù)，C為G的伴隨圈。以下將G的特征樹(shù)T的葉結(jié)點(diǎn)簡(jiǎn)稱為G的葉結(jié)點(diǎn)。輪是一種特殊的Halin圖，其特征樹(shù)的內(nèi)部結(jié)點(diǎn)只有一個(gè)，如圖1所示。

由Halin圖的定義可知，Halin圖G有如下性質(zhì)：

(i)G的所有葉結(jié)點(diǎn)的度為3。

(ii)G的任意兩個(gè)內(nèi)部面至多有1條公共邊，并且每個(gè)內(nèi)面與外部面恰有1條公共邊。

假設(shè)T至少有兩個(gè)非葉子結(jié)點(diǎn)，w是樹(shù)T中任意一個(gè)非葉子結(jié)點(diǎn)，而且僅與T中一個(gè)非葉子結(jié)點(diǎn)相鄰。不妨令與w相鄰的葉子結(jié)點(diǎn)集合為C(w)，這些結(jié)點(diǎn)在圈C上是一段連續(xù)的結(jié)點(diǎn)。我們將導(dǎo)出子圖F=G[{w}∪C(w)]稱為一個(gè)扇(fan)，w為扇的中心，如圖1(a)虛線中的子圖，其中v5為扇的中心。

圖1 Halin圖中的扇和輪Fig.1 Fans of a Halin graph and a wheel

Halin圖可以作為具有低成本和容錯(cuò)性的網(wǎng)絡(luò)模型，常用于研究普通圖中的NP完全問(wèn)題。David Eppstein提出了Halin圖的判定方法，Halin圖可以經(jīng)過(guò)一系列約化規(guī)則收縮直至K4圖，同時(shí)分解為伴隨圈和特征樹(shù)[1]。Cornuejols等[2]在帶權(quán)Halin圖上提出了一個(gè)解決TSP問(wèn)題的線性時(shí)間算法；Lou[3]證明每個(gè)Halin圖是哈密頓連通的；Li等[4]提出了在帶權(quán)Halin圖的每一對(duì)頂點(diǎn)之間找一個(gè)最小權(quán)值的哈密頓路徑的線性時(shí)間算法；Lou和Liu[5]給出了在線性時(shí)間解決Halin圖的3正則子圖問(wèn)題的算法；Lou等[6]還給出了求解Halin圖中最大線子圖問(wèn)題的線性時(shí)間算法。這些問(wèn)題都是普通圖中的NPC問(wèn)題。

本文要研究的就是一個(gè)在普通圖上的NPC問(wèn)題：最大切割問(wèn)題。最大切割問(wèn)題(max-cut problem)是一類特殊的圖劃分問(wèn)題(partitioning problem)，普通圖劃分是指對(duì)給定的(加權(quán)的)無(wú)向圖的節(jié)點(diǎn)集合進(jìn)行劃分，使得兩個(gè)節(jié)點(diǎn)集合之間的連接數(shù)量(加權(quán)之和)最小化[7]。當(dāng)各邊的權(quán)為1時(shí)，此問(wèn)題轉(zhuǎn)化為：求G的一種切割方法，使得作為邊割的邊數(shù)最多。該問(wèn)題在普通圖上仍是NPC問(wèn)題[8]，接下來(lái)本文將在Halin圖上，求各邊權(quán)為1時(shí)的最大切割問(wèn)題的一個(gè)解。

一般圖的最大匹配算法(Edmonds’s matching algorithm)以Berge定理為基礎(chǔ)，基于圖的內(nèi)部結(jié)點(diǎn)采用廣度優(yōu)先搜索增廣路。而本文將提出的算法基于Halin圖的內(nèi)部面進(jìn)行，對(duì)組成扇的內(nèi)部面進(jìn)行收縮和展開(kāi)且根據(jù)一定的規(guī)則進(jìn)行標(biāo)記，最終得到面與面的匹配，從面的匹配結(jié)果進(jìn)一步得到最大邊數(shù)的割集。

下面，我們對(duì)本文所引入的術(shù)語(yǔ)進(jìn)行定義：

設(shè)G=T∪C是一個(gè)Halin圖，除了伴隨圈圍出的外部面外(該面我們不討論)，以圍起一個(gè)面的圈是奇圈還是偶圈為標(biāo)準(zhǔn)，將Halin圖的內(nèi)部面分為奇面(odd)和偶面(even)，例如：圖2中面F1=v0v1v4v6v5v0是一個(gè)奇面，而面F1=v0v10v12v11v0一個(gè)偶面。隨著Halin圖中扇的收縮，各面是奇(偶)面均指它在原始Halin圖G中是奇(偶)面，不因扇的收縮而改變。

圖2 Halin圖的奇偶面Fig.2 Odd and even faces of Halin graph

本文提出的最大切割算法基于扇的收縮和展開(kāi)，因此我們針對(duì)Halin圖的扇提出“可擴(kuò)”的概念，如圖3所示。在扇中只有一段連續(xù)奇面情況下，如果奇面?zhèn)€數(shù)為2n(n≥1)，則這些奇面可以進(jìn)行完全的奇面對(duì)匹配，不存在未配對(duì)奇面的情況，我們將這種情況標(biāo)記成為“不可擴(kuò)”，即不需要將扇中奇面與扇外的奇面進(jìn)行配對(duì)，如圖3：①(其中兩奇面之間的橫線表示這兩個(gè)奇面配對(duì))；如果奇面?zhèn)€數(shù)為2n+1(n≥0)，則可以從第1個(gè)奇面開(kāi)始進(jìn)行配對(duì)，此時(shí)第2n+1個(gè)奇面沒(méi)有被配對(duì)，定義該扇為“右可擴(kuò)”，即該扇右端奇面可以與扇右側(cè)的奇面進(jìn)行配對(duì)，如圖3：②。若從第2個(gè)奇面開(kāi)始進(jìn)行配對(duì)，則該扇可以定義為“左可擴(kuò)”，如圖3：③；又因?yàn)樵撋燃瓤梢詾椤白罂蓴U(kuò)”又為“右可擴(kuò)”，所以將該扇標(biāo)記為“左可擴(kuò)或右可擴(kuò)”，如圖3：④；對(duì)于可能存在偶面的含收縮扇的扇，若扇中左右兩端存在兩個(gè)連續(xù)的奇面串，奇面串中奇面?zhèn)€數(shù)都為奇數(shù)，且扇中存在偶面使左右兩端的奇面串不連接，則將該扇定義為“左可擴(kuò)且右可擴(kuò)”，如圖3：⑤；若只有右端奇面?zhèn)€數(shù)為奇數(shù)，則標(biāo)記為“右可擴(kuò)”，如圖3：⑥；若只有左端奇面?zhèn)€數(shù)為奇數(shù)，則為“左可擴(kuò)”，如圖3：⑦；若兩端奇面?zhèn)€數(shù)都為偶數(shù)，則標(biāo)記為“不可擴(kuò)”。

圖3 定義“可擴(kuò)屬性”的幾種情形Fig.3 The definition of “extendible” fans

將Halin圖G的特征樹(shù)T上的邊稱為內(nèi)部邊，伴隨圈C上的邊稱為外部邊。

將一個(gè)扇的可擴(kuò)屬性進(jìn)行定義之后，可以將該扇收縮為外圈上一個(gè)葉結(jié)點(diǎn)，稱為“收縮扇”，該葉結(jié)點(diǎn)稱為“收縮扇”的偽點(diǎn)，如圖4。Cornuejols，Naddef和Pulleyblank[3]給出了收縮扇的步驟。

圖4 用“偽點(diǎn)”代表收縮扇Fig.4 Using a pseudo-vertex to represent a “shrink fan”

在將V劃分為V1和V2之后，把一個(gè)端點(diǎn)在V1中，一個(gè)端點(diǎn)在V2中的邊稱為“滿足條件的邊”，其余的邊稱為“不滿足條件的邊”。

將G的特征樹(shù)T的葉結(jié)點(diǎn)和內(nèi)部結(jié)點(diǎn)在G中對(duì)應(yīng)的點(diǎn)分別稱為“G的葉結(jié)點(diǎn)”和“G的內(nèi)部結(jié)點(diǎn)”。

1 算法詳述

易知，存在一種切割方法，使一個(gè)偶面上的邊都是滿足條件的邊。而無(wú)論何種切割方法，都不能使任何奇面上的邊都是滿足條件的邊，至少有一條不滿足條件的邊。本章將把最大切割問(wèn)題轉(zhuǎn)化為求解最大奇面對(duì)問(wèn)題，根據(jù)第一章提出的“可擴(kuò)性”定義，對(duì)每一層Halin圖的扇進(jìn)行“可擴(kuò)性”分析、標(biāo)記并將其收縮為偽點(diǎn)，得到新的Halin圖，重復(fù)標(biāo)記和收縮直至得到帶有層層標(biāo)記的輪。從輪開(kāi)始逐步展開(kāi)每一層收縮扇，使用優(yōu)先匹配“向下可擴(kuò)”的策略，對(duì)每一層扇中的奇面進(jìn)行兩兩匹配，得到基于初始Halin圖的奇面對(duì)。

之后將奇面對(duì)的公共邊標(biāo)記為“轉(zhuǎn)化邊”，基于按層切割原則，將“轉(zhuǎn)化邊”的兩個(gè)端點(diǎn)劃入同一集合。對(duì)比初步切割的結(jié)果，可以看到奇面對(duì)的公共邊轉(zhuǎn)化為不滿足條件的邊，卻增加了兩個(gè)面的外部邊作為滿足條件的邊。

1.1 初步切割

掃描Halin圖，將每個(gè)內(nèi)部面使用數(shù)字(1、2、……)進(jìn)行編號(hào)并做好奇、偶面的標(biāo)記，兩個(gè)面的公共邊則采用它分隔的兩個(gè)面的號(hào)碼對(duì)進(jìn)行標(biāo)記，例如：奇面1和偶面2的公共邊被標(biāo)記為E=(1,2)。

存在一種盡可能簡(jiǎn)單的切割辦法，將G初步劃分成V1和V2。該方法如下：

(i) 任取特征樹(shù)T的內(nèi)部結(jié)點(diǎn)u，標(biāo)記為第0層；

(ii) 使用BFS遍歷T中的所有結(jié)點(diǎn)，將與結(jié)點(diǎn)u距離為n的結(jié)點(diǎn)標(biāo)記為第n層；

(iii) 將偶數(shù)層(包括第0層)的所有結(jié)點(diǎn)劃分到V1中，將奇數(shù)層的所有結(jié)點(diǎn)劃分到V2中。

這種辦法可以取到G的特征樹(shù)T的所有邊，以及伴隨圈C上的一部分邊作為切割邊。易證這種分層切割辦法可以使得每個(gè)偶面上的所有邊都滿足條件，但是每個(gè)奇面上恰有一條邊不滿足條件(即該面包含的外部邊)。如果可以找到兩個(gè)奇面的內(nèi)部公共邊，則在不影響其他面結(jié)點(diǎn)劃分的情況下，把這兩個(gè)奇面不滿足條件的邊都轉(zhuǎn)化到公共邊上，就可以減少一條在當(dāng)前切割集合中的公共邊，而增加兩條切割邊(即這兩個(gè)面包含的外部邊)。

接下來(lái)我們采用收縮扇的辦法來(lái)找出Halin圖中最多可能出現(xiàn)的奇面對(duì)數(shù)，每個(gè)奇面對(duì)中的兩個(gè)奇面具有公共邊，且一個(gè)奇面至多只能出現(xiàn)在一個(gè)奇面對(duì)中。

1.2 收縮扇

在Halin圖中，第一層(最外層)扇中只存在奇面，將第一層的每一個(gè)扇進(jìn)行收縮，如圖5：

圖5 對(duì)第一層扇進(jìn)行收縮Fig.5 Shrink the first layer of fans

(I)若扇中有偶數(shù)個(gè)奇面，則該組奇面已形成兩兩配對(duì)，扇內(nèi)取得最大數(shù)目的奇面對(duì)，該扇標(biāo)記為“不可擴(kuò)”；

(II) 若扇中有奇數(shù)個(gè)奇面，則將該扇標(biāo)記為“左可擴(kuò)或右可擴(kuò)”。

對(duì)于第n(n≥2)層扇的收縮情況如下(如圖6左圖扇中一段連續(xù)奇面，包含的葉結(jié)點(diǎn)可能是收縮扇的偽點(diǎn))：

(Ⅰ) 標(biāo)記收縮扇(偽點(diǎn))的相鄰奇面，如圖6所示：

(i)如果收縮扇為“左可擴(kuò)或右可擴(kuò)”，則相當(dāng)于在兩個(gè)相鄰面中間插入一個(gè)奇面，該奇面可以與左側(cè)或右側(cè)奇面形成配對(duì)，若該奇面與右側(cè)奇面進(jìn)行配對(duì)，則在收縮扇內(nèi)部從左向右兩兩配對(duì)即可，若該奇面與左側(cè)奇面進(jìn)行配對(duì)，則在收縮扇內(nèi)部從左側(cè)第一個(gè)未配對(duì)奇面開(kāi)始，進(jìn)行兩兩配對(duì)；

(ii)如果收縮扇只能向右擴(kuò)，或者只能向左擴(kuò)，則將其可擴(kuò)方向的相鄰奇面標(biāo)記為“向下可擴(kuò)”；

(iii)如果收縮扇既可以向左擴(kuò)又可以向右擴(kuò)，則將其相鄰兩個(gè)奇面都標(biāo)記為“向下可擴(kuò)”；

(iv)如果收縮扇不具有可擴(kuò)屬性，則不對(duì)其相鄰的奇面做任何處理。

圖6 標(biāo)記收縮扇(偽點(diǎn))的相鄰奇面Fig.6 Mark the adjacent odd faces of a shrunk-fan (pseudo-vertex)

(Ⅱ) 在帶有標(biāo)記的連續(xù)奇面上，進(jìn)行奇面兩兩匹配，使其成為對(duì)集，使用帶有“向下可擴(kuò)”屬性的奇面可以對(duì)該段奇面進(jìn)行分割，如圖7所示：

(i)對(duì)于無(wú)屬性奇面與“向下可擴(kuò)”奇面之間片段，“向下可擴(kuò)”奇面與收縮扇中未配對(duì)奇面進(jìn)行配對(duì)，然后向左遍歷該段中所有奇面，并進(jìn)行兩兩配對(duì)；

(ii)對(duì)于“向下可擴(kuò)”奇面與無(wú)屬性奇面之間的片段，“向下可擴(kuò)”奇面與收縮扇中未配對(duì)奇面進(jìn)行配對(duì)，然后向右遍歷該段中所有奇面并進(jìn)行配對(duì)；

(iii)對(duì)于兩個(gè)“向下可擴(kuò)”奇面中間片段，“向下可擴(kuò)”奇面與收縮扇中未配對(duì)奇面進(jìn)行配對(duì)，并從左側(cè)對(duì)一個(gè)非“向下可擴(kuò)”奇面開(kāi)始，進(jìn)行兩兩配對(duì)；

(iv)對(duì)于兩個(gè)無(wú)屬性奇面中間片段，則從第一奇面開(kāi)始，進(jìn)行兩兩配對(duì)，如果奇面?zhèn)€數(shù)為偶數(shù)，則可以進(jìn)行完全匹配，如果奇面?zhèn)€數(shù)為奇數(shù)，則需要討論該片段在扇中位置：

a) 如果該段奇面位于扇中最左端，則從右往左進(jìn)行匹配；

b) 如果該段奇面位于扇中間或最右端，則從左往右進(jìn)行匹配。

圖7 對(duì)包含”向下可擴(kuò)”屬性奇面的奇面串進(jìn)行奇面配對(duì)Fig.7 Pairing odd faces in a “down-extendible” segment

(Ⅲ) 對(duì)第n層扇進(jìn)行收縮：

(i)如果該扇左右兩端都為偶面，則標(biāo)記為“不可擴(kuò)”；

(ii)如果該扇一端為奇面，另外一端為偶面，則對(duì)奇面那一側(cè)的最外端奇面進(jìn)行討論：如果該奇面處于最左端且未配對(duì)，則將該扇收縮且標(biāo)記為“左可擴(kuò)”；如果該奇面處于最右端且未配對(duì)，則該扇收縮并標(biāo)記為“右可擴(kuò)”；如果該奇面已配對(duì)，則將該扇收縮并標(biāo)記為“不可擴(kuò)”；

(iii)該扇兩端都為奇面，如果該扇兩端奇面都未配對(duì)，則將該扇收縮并標(biāo)記為“左可擴(kuò)且右可擴(kuò)”；如果左端奇面未配對(duì)而右端奇面已配對(duì)，則將該扇標(biāo)記為“左可擴(kuò)”并收縮扇，反之標(biāo)記為“右可擴(kuò)”并收縮扇；如果兩端奇面都已配對(duì)，則標(biāo)記為“不可擴(kuò)”并收縮扇；

(iv)注意，如果該扇中不存在偶面和“向下可擴(kuò)”屬性奇面，即該扇為一段連續(xù)奇面，如果奇面?zhèn)€數(shù)為奇數(shù)，則將該扇標(biāo)記為“左可擴(kuò)或右可擴(kuò)”，否則為“不可擴(kuò)”，并收縮該扇。

對(duì)Halin圖中的每一層的扇執(zhí)行以上步驟(Ⅰ)～(Ⅲ)后，當(dāng)Halin圖中不存在可收縮扇時(shí)，我們得到一個(gè)輪(wheel)，輪是一種特殊的Halin圖，其特征樹(shù)的內(nèi)部結(jié)點(diǎn)只有一個(gè)。這時(shí)，按照步驟(Ⅳ)進(jìn)行處理。

(Ⅳ) 輪的處理

(i)如果輪上不存在可擴(kuò)的收縮扇(偽點(diǎn))且不包含偶面，則從某一奇面開(kāi)始，進(jìn)行兩兩配對(duì)，如圖8：①；

(ii)若輪上不存在可擴(kuò)的收縮扇，但包含偶面，則偶面將輪分隔為若干段連續(xù)的奇面，則每一段連續(xù)奇面從左向右兩兩配對(duì)，如圖8：②；

(iii)如果輪上存在收縮扇，則根據(jù)步驟(Ⅰ)對(duì)收縮扇的相鄰奇面進(jìn)行標(biāo)記。對(duì)于每個(gè)“向下可擴(kuò)”奇面，將該奇面與收縮扇中奇面進(jìn)行配對(duì)。這時(shí)，輪中所有偶面和“向下可擴(kuò)”的奇面將輪中的奇面分隔成若干段連續(xù)的奇面，每一段連續(xù)奇面從左到右依次進(jìn)行兩兩配對(duì)，直至不存在相鄰的未配對(duì)奇面，如圖8：③。

圖8 對(duì)輪的處理Fig.8 Wheel handling

(V) 展開(kāi)收縮扇求最大數(shù)目的奇面對(duì)

當(dāng)輪中求出最大數(shù)目的奇面對(duì)后，我們將收縮后的扇逐個(gè)恢復(fù)。

(i)首先將輪中配對(duì)的奇面公共邊標(biāo)記為“轉(zhuǎn)化邊”；

(ii)之后將外圈上表示收縮扇的葉結(jié)點(diǎn)(偽點(diǎn))逐個(gè)展開(kāi)成原來(lái)的扇，將其中配對(duì)的奇面的號(hào)碼對(duì)應(yīng)的邊標(biāo)記為“轉(zhuǎn)化邊”，展開(kāi)收縮扇進(jìn)行“轉(zhuǎn)化邊”標(biāo)記，直至不存在表示收縮扇的偽點(diǎn)。配對(duì)的算法見(jiàn)步驟(Ⅱ)，其中需要指出的是：

a) 若某個(gè)奇面是“向下可擴(kuò)”的，它左邊的葉結(jié)點(diǎn)是向右可擴(kuò)的偽點(diǎn)，它右邊的葉結(jié)點(diǎn)是向左可擴(kuò)的偽點(diǎn)，則將該面與左邊偽點(diǎn)對(duì)應(yīng)的扇的右端未配對(duì)的奇面配對(duì)，如圖9所示。面O1的左右兩個(gè)葉結(jié)點(diǎn)x1及x2均為可擴(kuò)偽點(diǎn)，其中x1′為“右可擴(kuò)”，x2′為左可擴(kuò)，此時(shí)，將奇面O1與左邊偽點(diǎn)x1′對(duì)應(yīng)扇中的O2進(jìn)行配對(duì)。

b) 若本層扇F中某個(gè)奇面對(duì)應(yīng)一個(gè)標(biāo)記“左可擴(kuò)或右可擴(kuò)”的具有2k+1個(gè)奇面的扇F1：如果在本層扇F中，該奇面與左邊的奇面配對(duì)，則F1中最左端的奇面與左側(cè)的奇面配對(duì)，其余2k個(gè)奇面從左到右兩兩配對(duì)；如果在本層扇F中，該奇面與右邊的奇面配對(duì)，則F1中最右端的奇面與右側(cè)的奇面配對(duì)，其余2k個(gè)奇面從左到右兩兩配對(duì)；如果在本層扇F中，該奇面不能與左邊和右邊的奇面配對(duì)，則在F1中從左到右2k個(gè)奇面兩兩配對(duì)，剩下一個(gè)奇面不配對(duì)。

圖9 特殊的情況Fig.9 A special case

1.3 最大切割

從某個(gè)內(nèi)部結(jié)點(diǎn)u出發(fā)(以u(píng)為根)進(jìn)行寬度優(yōu)先遍歷特征樹(shù)T，首先將u劃入集合V1中，若某結(jié)點(diǎn)x的父結(jié)點(diǎn)y已劃入V1(或V2)，且xy邊不是“轉(zhuǎn)化邊”，則x劃入V2(或V1)；若xy是“轉(zhuǎn)化邊”，則x劃入V1(或V2)。寬度優(yōu)先遍歷完T，則所有結(jié)點(diǎn)都已劃入集合V1或V2，這時(shí)得到Halin圖G的最大切割(V1,V2)。

2 算法分析

2.1 算法正確性證明

定理1按1.2節(jié)的算法求出的奇面對(duì)是最大數(shù)目的奇面對(duì)。

證明

(I) 對(duì)輪分情況討論如下：

(i)輪中所有面為奇面，且不存在對(duì)應(yīng)可擴(kuò)的收縮扇的偽點(diǎn)：則從任意一個(gè)奇面開(kāi)始，從左向右進(jìn)行兩兩配對(duì)，此時(shí)輪中取得最大數(shù)目的奇面對(duì)；

(ii)輪中所有面為奇面，且存在k個(gè)具有“向下可擴(kuò)”屬性的奇面。由于任意兩個(gè)“向下可擴(kuò)”奇面之間最多產(chǎn)生1個(gè)未匹配奇面，所以輪中最多有k個(gè)奇面未匹配。若這k個(gè)奇面分別與“向下可擴(kuò)”奇面進(jìn)行配對(duì)，這樣至多增加了k個(gè)奇面對(duì)，而使原來(lái)與“向下可擴(kuò)”奇面配對(duì)的收縮扇中的奇面不再與那些“向下可擴(kuò)”奇面配對(duì)，這樣就減少了k個(gè)奇面對(duì)。其結(jié)果小于等于優(yōu)先選擇“向下可擴(kuò)”的奇面對(duì)數(shù)目。此時(shí)奇面對(duì)數(shù)目不會(huì)大于優(yōu)先進(jìn)行“向下可擴(kuò)”的奇面對(duì)數(shù)目；

(iii)若輪中存在偶面使得奇面串不構(gòu)成環(huán)，則等同于在扇中討論該算法的正確性。

(II) 對(duì)扇的情形討論如下：

在扇中，兩個(gè)偶面之間分隔出一段連續(xù)的奇面，或扇的一端和偶面之間分隔出一段連續(xù)的奇面，或扇的兩端之間是一段連續(xù)的奇面(這時(shí)扇中全是奇面)。

假設(shè)扇的一段連續(xù)奇面串中有k個(gè)具有“向下可擴(kuò)”屬性的奇面，則最多可將該奇面串劃分成k+1段，在第1至第k段中，至多產(chǎn)生k個(gè)未匹配奇面。如果不考慮“向下可擴(kuò)”，則與上面輪的討論結(jié)果相同，奇面對(duì)數(shù)不會(huì)大于優(yōu)先選擇“向下可擴(kuò)”的奇面對(duì)數(shù)，對(duì)于第k+1段的奇面?zhèn)€數(shù)，可以分情況討論如下：

(i)若第k+1段中奇面?zhèn)€數(shù)為偶數(shù)，則可以進(jìn)行完全匹配，在前k段都是奇數(shù)個(gè)奇面(即至多產(chǎn)生k個(gè)未匹配的奇面)的情況下，原奇面串中奇面?zhèn)€數(shù)為偶數(shù)，若不考慮“向下可擴(kuò)”，則該k+1段奇面不可擴(kuò)。若它們就是整個(gè)扇，則可以收縮為“不可擴(kuò)”的收縮扇；若優(yōu)先將“向下可擴(kuò)”奇面與收縮扇中奇面進(jìn)行配對(duì)，則會(huì)在第1段中產(chǎn)生位于最左端的未匹配奇面。若第一段出現(xiàn)在扇的最左端，在不減少奇面對(duì)的情況下，使得該扇收縮后具有“向左可擴(kuò)”屬性，若該扇左側(cè)為奇面，可以在下一輪奇面匹配過(guò)程中，可能增加一個(gè)奇面對(duì)，使得奇面對(duì)數(shù)可能大于不考慮“向下可擴(kuò)”的情況。

(ii)若第k+1段奇面?zhèn)€數(shù)為奇數(shù)，則最后端奇面未被匹配，在前k段都是奇數(shù)個(gè)奇面(即至多產(chǎn)生k個(gè)未匹配的奇面)的情形下，奇面串中奇面?zhèn)€數(shù)為奇數(shù)，不考慮“向下可擴(kuò)”時(shí)，該k+1段奇面“左可擴(kuò)或右可擴(kuò)”。若它們就是整個(gè)扇，則該扇收縮后具有“左可擴(kuò)或右可擴(kuò)”屬性；若優(yōu)先將“向下可擴(kuò)”奇面與收縮扇中奇面進(jìn)行配對(duì)，則會(huì)在第1段和第k+1段中產(chǎn)生未配對(duì)奇面，這兩個(gè)未配對(duì)奇面位于原奇面串的兩端，如果它們就是扇的兩端，可使得該扇收縮后具有“左可擴(kuò)且右可擴(kuò)”屬性。如果該扇左右兩側(cè)均存在奇面，則有可能增加2個(gè)奇面對(duì)，所以優(yōu)先考慮“向下可擴(kuò)”可能取得更大的奇面對(duì)個(gè)數(shù)。

(iii)假設(shè)在一段連續(xù)的奇面F中有k個(gè)“向下可擴(kuò)”的奇面，而最大數(shù)目奇面對(duì)選了其中r個(gè)(r

綜上，在奇面串進(jìn)行配對(duì)時(shí)，優(yōu)先考慮“向下可擴(kuò)”的奇面配對(duì)，可以取得最大的奇面對(duì)數(shù)。

定理2按第1節(jié)的方法可求出Halin圖G=T∪C的最大切割。

證明

G中切割邊最多的情況下，每一偶面所有邊都是切割邊，而每一個(gè)奇面至少有一條非切割邊(因?yàn)樗倪吔缛Φ拈L(zhǎng)度為奇數(shù))。首先按1.1節(jié)的方法可求出Halin圖G的一個(gè)初始劃分(V1,V2)，這時(shí)樹(shù)T中的邊都是切割邊，偶面上的外部邊都是切割邊，奇面上的外部邊都是非切割邊，已達(dá)到切割邊最多的要求，我們將該切割方法稱為初始切割。

要進(jìn)一步增加切割邊數(shù)，只能將兩個(gè)相鄰奇面的公共邊(只有一條)變?yōu)榉乔懈钸叄@兩個(gè)奇面的外部邊(有2條)變?yōu)榍懈钸叀?/p>

任取兩個(gè)奇面f1和f2的公共內(nèi)部邊e1=(t1,t2)，和這兩個(gè)奇面的外部邊e2=(u1,u2)，e3=(v1,v2)，則G-{e1,e2,e3}得到兩個(gè)分支G1和G2，不妨設(shè)t1,u1,v1∈(G1)，t2,u2,v2∈(G2)。由1.1節(jié)的劃分(V1,V2)知，t1和t2分別屬于不同的Vi和Vj(1≤i≠j≤2)。而u1和u2(V1和V2)屬于同一個(gè)Vi(1≤i≤2)(同一個(gè)Vj(1≤j≤2))。我們只需將V(G1)中的V1中的頂點(diǎn)與V2中的頂點(diǎn)互換一下，則在不改變其它面的切割邊的情況下，t1和t2現(xiàn)在屬于同一個(gè)Vi(1≤i≤2)，而u1和u2(同理v1和v2)現(xiàn)在屬于不同的Vi和Vj(1≤i≠j≤2)，外部邊e2和e3成了切割邊，e1變成非切割邊，從而G1增加了一條的切割邊。

下面我們作一個(gè)輔助圖A，以證明在G中求最大數(shù)目的奇面對(duì)后，將每個(gè)奇面對(duì)的公共邊變?yōu)榉乔懈钸?，而它們的外部邊變?yōu)榍懈钸叄傻玫阶畲笄懈睢?/p>

設(shè)f1，f2，…，fr是G的所有內(nèi)部面，以f1，f2，…，fr作為輔助圖A的結(jié)點(diǎn)。設(shè)給定G的某個(gè)最大切割，A中結(jié)點(diǎn)fi和fj之間連一條線，當(dāng)且僅當(dāng)G中的fi和fj的公共邊為非切割邊，最終得到輔助圖A。

對(duì)于圖A中的每一個(gè)孤立點(diǎn)fi，若fi對(duì)應(yīng)G中奇面，則fi包含一條非切割邊(即外部邊)；若fi對(duì)應(yīng)G中一個(gè)偶面，則fi不含非切割邊，即它周界的所有邊都為切割邊。

若圖A中連通分支C的結(jié)點(diǎn)數(shù)大于等于2，則C中至少有|V(C)-1|條邊，這些邊都對(duì)應(yīng)G中的非切割邊，而C的結(jié)點(diǎn)所對(duì)應(yīng)的G中的那些面所包含的非切割邊數(shù)會(huì)大于等于C的邊數(shù)，因?yàn)镚中的面可能還包含作為非切割邊的外部邊。

若C中不存在兩個(gè)相鄰結(jié)點(diǎn)fi和fj，且fi和fj都對(duì)應(yīng)G中的奇面，也就是說(shuō)，C中每個(gè)對(duì)應(yīng)奇面的結(jié)點(diǎn)fi只與對(duì)應(yīng)偶面的結(jié)點(diǎn)fj相鄰，即C中至少有一個(gè)對(duì)應(yīng)偶面的結(jié)點(diǎn)，且C中對(duì)應(yīng)奇面的結(jié)點(diǎn)數(shù)小于等于|V(C)-1|。而在初始切割中，所有偶面不含非切割邊，每個(gè)奇面只有1條外部邊作為非切割邊，故將C中的結(jié)點(diǎn)對(duì)應(yīng)的面恢復(fù)成初始切割，其中的非切割邊數(shù)為奇面數(shù)，小于等于|V(C)-1|，小于等于在G的假定最大切割中C的結(jié)點(diǎn)對(duì)應(yīng)G中的面所包含的非切割邊數(shù)，因此，該假定最大切割中的切割邊數(shù)小于等于初始切割。

若C中存在兩個(gè)相鄰結(jié)點(diǎn)fi和fj，且fi和fj都對(duì)應(yīng)G中的奇面。取fi和fj的公共邊為非切割邊，其余邊是切割邊；C中其它結(jié)點(diǎn)所對(duì)應(yīng)的G中的面fk，若fk是偶面，則該偶面不含非切割邊；若fk是奇面，則fk恰有一個(gè)外部邊是非切割邊。因此，我們?cè)贑的結(jié)點(diǎn)對(duì)應(yīng)的面中找一個(gè)奇面對(duì)，將它們的公共邊轉(zhuǎn)化為非切割邊，可以使得這兩個(gè)奇面的外部邊都變成切割邊，而不對(duì)其它面產(chǎn)生影響，將其它面恢復(fù)成初始切割后，C的結(jié)點(diǎn)對(duì)應(yīng)的G的面的非切割邊數(shù)小于等于|V(C)-1|，小于等于G的假定最大切割中C的結(jié)點(diǎn)對(duì)應(yīng)的G中的面所包含的非切割邊數(shù)，即其切割邊數(shù)大于等于當(dāng)前C對(duì)應(yīng)的面中的切割邊數(shù)。

通過(guò)輔助圖A，我們可以證明，在給定的最大切割中，G中的非切割邊數(shù)大于等于G中取s個(gè)奇面對(duì)的公共邊作為非切割邊，其余奇面取它們包含的外部邊作為非切割邊的非切割邊數(shù)，其中s為A中滿足以下條件的連通分支數(shù)，每個(gè)連通分支含兩個(gè)相鄰的結(jié)點(diǎn)fi和fj，且fi和fj都對(duì)應(yīng)G中的奇面。

由前面的證明可知，在G中找到的奇面對(duì)越多，將其公共邊轉(zhuǎn)化為非切割邊后(其外部邊轉(zhuǎn)化為切割邊)，則G中的切割邊就越多。因此，只要在G中找出最大數(shù)目的相鄰奇面對(duì)，將每一對(duì)奇面的公共內(nèi)部邊(比如e1)變成非切割邊，而將它們的外部邊(如e2和e3)變成切割邊，即可得到最大數(shù)目的切割邊。這也就是在1.3節(jié)中將“轉(zhuǎn)化邊”(對(duì)應(yīng)上述的e1)兩端點(diǎn)劃入同一分類Vi(1≤i≤2)，對(duì)T中非“轉(zhuǎn)化邊”，將T中相鄰的兩點(diǎn)劃分入不同的分類Vi和Vj(i≠j)。因此，1.3節(jié)所得到的分類(V1,V2)是最大切割。

2.2 時(shí)間復(fù)雜度分析

第一步，掃描Halin圖，對(duì)每個(gè)內(nèi)部面使用數(shù)字(1、2、……)進(jìn)行編號(hào)并做好奇偶面的標(biāo)記，兩個(gè)面的公共邊則采用它分隔的兩個(gè)面的號(hào)碼對(duì)進(jìn)行標(biāo)記，例如：奇面1和偶面2的公共邊被標(biāo)記為E(1,2)。其中每條內(nèi)部邊被掃描次數(shù)為2，此時(shí)，時(shí)間復(fù)雜度為2n-1(n為頂點(diǎn)數(shù))；每條外部邊掃描次數(shù)為1，時(shí)間復(fù)雜度小于頂點(diǎn)數(shù)n。所以第一步時(shí)間復(fù)雜度小于3n。

第二步，收縮扇和擴(kuò)展扇，將奇面對(duì)公共邊標(biāo)記為“轉(zhuǎn)化邊”，該過(guò)程遍歷了兩次G中所有的面，由于面數(shù)小于頂點(diǎn)數(shù)，所以該步驟中，時(shí)間復(fù)雜度小于2n。

第三步，寬度優(yōu)先遍歷T中所有頂點(diǎn)，并劃分到割集的兩個(gè)集合中，該步驟時(shí)間復(fù)雜度為n。

綜上，該算法的實(shí)際運(yùn)行時(shí)間為6n，時(shí)間復(fù)雜度為O(n)。