邊賦權簡單圖最長圈問題研究

張智微，李 鵬

(重慶理工大學 理學院， 重慶 400054)

密爾頓圈(路)問題是圖論中最熟知的NPC問題之一，而其最自然的推廣就是最長圈(路)問題，即尋找給定圖中所包含頂點個數(shù)(或邊數(shù))最多的簡單圈(路)。最長圈(路)問題是圖論的一個研究熱點之一，圍繞它有大量的工作出現(xiàn)，如研究最長圈(路)的結構性質[1，4，5，8-9，14]，研究最長圈的多項式算法[2，7，12-13]，研究最長圈的近似算法[3，6，15]以及其他相關問題[10-11]等。

弦圖是不包含長度大于等于4的誘導圈的圖，它是圖論很重要的基礎圖類。區(qū)間圖是這樣的圖類：它的頂點可以和數(shù)軸上的區(qū)間一一對應，2個頂點之間有邊當且僅當它們對應的區(qū)間相交。熟知的是區(qū)間圖是弦圖的一個子類。

圖論中一個很重要的猜想是：2連通的弦圖的所有最長圈一定經過同1個頂點。圍繞這個猜想，圖論工作者進行了大量的研究，但始終無法解決這個猜想。與這個猜想緊密相關的另1個猜想是：2連通邊賦權簡單圖(權值為正數(shù))所有最長圈都經過同1個頂點。本文主要研究邊賦權簡單圖(極大團不超過2個的圖)的最長圈性質，證明了該猜想在2連通的邊賦權簡單圖是正確的。

1 預備知識

在圖論中，圖中一條路徑指的是一頂點序列：v1,v2,…,vn。序列中任何相鄰的2頂點都可以在圖中找到對應的邊。一條路徑的長度是這條路徑所包含的邊數(shù)。圈指的是在圖中任選一個頂點，沿著不重復的邊，經過不重復的頂點為途徑，之后又回到起點的閉合途徑。重邊指的是具有一對頂點的多條邊。若一個圖不含圈和重邊，則稱此圖為一個簡單圖。設G是頂點集為V(G)={v1，v2，…，vn}和邊集為E(G)={e1，e2，…，en}的簡單圖。若頂點vi和vj在圖G中相鄰，則記為vivj∈E(G)。圖G中的團就是兩兩之間有邊的頂點集合。若一個團不被其他任意一個團所包含，即它不是其他任一團的真子集，則稱該團為圖G的極大團。

在圖G中，若從頂點vi到頂點vj有路徑相連，則稱vi和vj是連通的。如果圖G中任意2點都是連通的，那么稱圖G為連通圖。假設有簡單圖H，滿足如下條件V(H)?V(G)，E(H)?E(G)且H中邊的頂點的分配和G中邊的頂點的分配一樣，則圖H是圖G的子圖。若去掉圖G中的任意一點后的子圖是連通的，但是去掉某2個點之后的子圖就不是連通圖，則稱圖G為2連通圖。

給圖G中的每1條邊賦予一定的權數(shù)，記為W(vivj)。令W(vivj)=eij且滿足eij≥0，(1≤i

2 只有1個極大團的圖

定理1若簡單圖只有一個極大團，則該圖所有的最長圈都要經過相同的2個頂點。進一步，若E(vi0vj0)是圖G中所賦權值最大的邊，即ei0ej0=max{eij∶1≤i0

證明：假設存在1個最長圈L不經過vi0，vj0這2個點。任取最長圈C上相鄰2點，分別記為vp，vq。用路徑vpvi0vj0vq取代邊vpvq可得到一個新的圈，記為C′，參看圖1。

圖1 一個極大團的示意圖

因為L是最長圈，所以此時有不等式

epi0+ei0j0+ej0q≤epq

(1)

但實際上根據假設有ei0j0≥epq，且epi0>0，eqj0>0故可得出，

epi0+ei0j0+ej0q>epq

(2)

這與不等式(1)矛盾，所以假設不成立。故最長圈不可能同時不經過vi0，vj0這2個點。

因為最長圈只經過vi0，vj02點中的1點，所以可假設存在最長圈Q滿足vi0?Q，在最長圈Q上任意取1個點，記為vm，顯然存在邊E(vmvj0)。用路徑vmvi0vj0取代路徑L可得到1個新的圈，記為Q′。

此時有emi0+ei0j0>emj0，Q′成為最長圈， 這與Q是最長圈矛盾。假設不成立，說明每個最長圈都要經過vi0，vj0這2個點。

綜上所述，當簡單圖只有1個極大團時，圖的每1個最長圈都要經過圖中相同的2個點。

3 2個團的二連通圖

為了方便理解，2個團的二連通圖見圖2。

圖2 2個團的二連通圖的示意圖

這里將2個團分別記為K1，K2，記S為K1與K2的交集，即K1∩K2=S。記P3是長為3的路徑。

定理2在2連通圖L中假設eab>ebc且令max(P3)∩S=?。若max(P3)∩S=?，則圖G的每一個最長圈都要經過vb點。

證明：設2連通圖G存在1個最長圈L不經過vb點，則L也不經過va，vc點。

首先，如果最長圈L經過va點。在L上取1個va的相鄰點記為va′，用路徑vavbva′取代路徑vava′，得到1個新的圈，記為L′，圖形可參看圖3。

圖3 va在最長圈L的示意圖

根據假設有eaa′≥eab+eba′，但是實際上對于路徑vava′vb，有

ea′a+eab≥2eab+eba′>2eab≥eab+ebc

(3)

這與路徑vavbvc是最長P3矛盾，此假設不成立，所以va?L。

其次，假設L經過vc點，在最長圈L上任取一個vc的相鄰點記為vc′，圖形見圖4。

圖4 vc在最長圈L的示意圖

對于路徑vcvc′與路徑vcvbvavc′有：

ecc′≥ecb+eba+eac′>eab+ebc

(4)

這與vavbvc是最長P3矛盾，故此假設不成立，所以最長圈L不經過vc點。綜上所述va，vb，vc?L。

然后，我們可假設?vs1，vs2∈S但是vs1，vs2?L。在最長圈L上任取一點及其相鄰點，分別記為vx，vx1。若用路徑vxvs2vcvbvavs1vx′取代路徑vxvx′，則會得到一個新圈，記為L″，見圖5。

圖5 vs1和vs2不屬于L的示意圖

則顯然有，

exx′≥exs2+es2c+ecb+eba+eas1+es1x′>eab+ebc

(5)

這與路徑vavbvc是最長P3矛盾，故此假設不成立，所以最長圈L最多不經過S中的一個點。

再假設S中存在一個點vs3且vs3?L，但S中的其他點都在最長圈L上。取L上任意一點vs4和它的相鄰點vs5。用路徑vs4vcvbvcvs3vs5取代路徑vavbvc，可得到一個新圈，記為L?，見圖6。

圖6 S存在點不屬于L的示意圖

根據vavbvc是最長圈這一假設，有

es4s5≥es4c+ebc+eab+eas3+es4s5>eab+ebc

(6)

但是這與vavbvc是最長P3矛盾，所以此假設不成立，故最長圈都經過S中的每一個點。

在最長圈L上取4個點分別記為vx，vy，vz，vw且vx，vy，vz，vw∈K2/S。顯然這4個點與va，vb，vc∈K1無邊。以vw為起點和終點，按照圖7箭頭指示歷經vw，vy，vx，vs1，va，vb，vc，vs2，vw這些點。

圖7 以vw為起點和終點的歷程圖

顯然這是一個圈，記為C1。根據歷經的路徑可知，C1比最長圈C少了E(s1y)和E(s2z)但是至少多了E(ab)，E(bc)及E(yz)。故有

es1y+es2z>eyz+eab+ebc

(7)

以vavbvc為起點和終點，按照圖8箭頭指示歷經vz，vx，vw，vy，vs1，va，vb，vc，vs2，vz這些點。

圖8 以vz為起點和終點的歷程圖

顯然這也是一個圈，記為C2。根據歷經的路徑可知，C2比最長圈C少了E(ws2)和E(xs1)，但是至少多了E(xw)，E(ab)及E(bc)，故有

ews2+exs1>exw+eab+ebc

(8)

將不等式(7)(8)相加，可得

exs1+eys1+ezs2+ews2>2(eab+ebc)+

eyz+exw>2(eab+ebc)

(9)

考慮P3∶vxvs1vy，P3：vzvs2vw及最長P3∶vavbvc，有

exs1+eys1≤eab+ebc

(10)

ezs2+ews2≤eab+ebc

(11)

將不等式(10)與不等式式(11)相加，可得

exs1+eys1+ezs2+ews2≤2(eab+ebc)

(12)

這與不等式(9)矛盾，所以圖G的每一個最長圈一定經過vb點。

定理3假設圖G中max(P3)=eab+ebc，eab≥ebc。若max(P3)∩S≠?，vb∈S，則圖G的最長圈都經過vb點。

證明：假設存在最長圈C3不經vb點，則有va?C3。因為若va∈C3，在C3上取va的一個相鄰點記為va1，則根據圖9有，

eaa1≥eab+eba1

(13)

進一步有，

eaa1+eab≥2eab+eba1>2eab≥eab+ebc

(14)

這與vavbvc是最長P3矛盾，故va?C3。

圖9 vb不屬于C3的示意圖

若va∈K1+K2-2(K1∩K2)，則最長圈一定經過va的相鄰點。因為若假設存在最長圈C4不經過va的鄰點，我們可在S中任意選取一點，記為vb1，顯然有vb1?C4。在最長圈C4上任意選取一個點vm及其個鄰點vn，vl，那么根據圖10的插法一，有

emn≥enb1+eb1a+eab+ebm

(15)

圖10 插法一示意圖

根據圖11的插法二，有

eml≥emb1+eb1a+eab+ebl

(16)

圖11 插法二示意圖

將不等式(15)與(16)相加，得

emn+eml>2eab≥eab+ebc

(17)

這與vavbvc是最長P3矛盾，所以假設不成立，故最長圈一定經過va的鄰點。

記vd為最長圈C3上的va的鄰點，vm，vn是C3上vd的2個鄰點，則根據圖12的插法三，有

emd≥eda+eab+ebm

(18)

圖12 插法三示意圖

根據圖13的插法四，有

end≥eda+eab+ebn

(19)

圖13 插法四示意圖

將不等式(18)與(19)相加可得：

emd+end>eab+ebc

(20)

不等式(20)與vavbvc是最長P3矛盾，所以存在最長圈不經過vb這一假設不成立，故圖G的最長圈都經過vb點。

定理4若max(P3)∩S≠?且vb?S，但va∈S，則最長圈都經過va點。

證明：假設存在最長圈C5不經過va點，則有vb?C5。因為若vb∈C5，在C5上取vb的一個鄰點，記為vb′，則根據圖14有，

ebb′≥eba+eab′

(21)

進一步有，

ebb′+eba≥2eab+eab′>2eab>eab+ebc

(22)

這與vavbvc是最長P3矛盾，所以vb?C5。

圖14 vb屬于最長圈C5的示意圖

若vb?K1+K2-2(K1∩K2)，則圖G的最長圈一定經過vb的鄰點。假設圖G存在一個最長圈C6，它不經過vb的鄰點。那我們在S中任取一個點，記為va′，顯然有va′?C6，在C6中任取一個點記為vg及其2個相鄰點分別記為vh，vl。根據圖15的插法五，有

ehg≥eha+eab+eba′+ea′g

(23)

圖15 插法五示意圖

根據圖16的插法六，有

egl≥ega+eab+eba′+eal

(24)

將不等式(23)與(24)相加可得：

ehg+egl>2eab≥eab+ebc

(25)

圖16 插法六示意圖

不等式(25)與vavbvc是最長P3矛盾，所以最長圈不經過vb點這一假設不成立，故最長圈都經過vb的鄰點。

記vp是在最長圈C5上的vb的鄰點，vo，vq是C5上vp的2個鄰點，則根據圖17的插法七，有

eop≥eoa+eab+ebp

(26)

圖17 插法七示意圖

根據圖18的插法八，有

epq≥eqa+eab+ebp

(27)

圖18 插法八示意圖

(28)

不等式(28)與vavbvc是最長P3矛盾，所以最長圈C5不存在vb的鄰點。由此可知存在最長圈C5不經過va點這一假設不成立，即若vb?S，va∈S時，圖G的每一個最長圈都經過va點。

定理5若圖G中的max(P3)=eab+ebc且eab≥ebc。當max(P3)∩S≠?，vb?S，va?S時，圖G的最長圈都經過vc點。

證明：假設存在最長圈C7不經過vc點，則有va，vb?C7。因為對于點vb，若vb∈C7，在最長圈上取一個點記為x1，x1需滿足x1≠a，則根據圖19有，

ebx1≥ebc+ecx2>ebc

(29)

不等式(29)兩邊同時加上eab，有

ebx1+eab≥eab+ebc

(30)

不等式(30)與vavbvc是最長P3矛盾，所以vb∈C7這一假設不成立，故vb?C7。

圖19 最長圈C7的示意圖

對于點va，若va∈C7，則可在最長圈C7上任取一個va的相鄰點，記為vx2。根據圖20構造一個新的路徑vavbvc，有

eax2≥eab+ebc+ecx2>ebc

(31)

圖20 va屬于C7的示意圖

不等式(31)兩邊同時加上eab，有

eax2+eab≥eab+ebc

(32)

不等式(32)與vavbvc是最長P3矛盾，所以vb∈C7這一假設不成立，故vb?C7。

若va∈K1+K2-2(K1∩K2)，則圖G的最長圈一定經過va的鄰點。假設存在最長圈C8不經過va的鄰點，則可在S中任取一點記為vc′，顯然有vc′?C8vavbvc。在最長圈C8上任取一點記為vu以及其相鄰點記為vv。根據圖21有，

euv≥evc+ecb+eba+eac′+euc′>eab+ebc

(33)

此不等式與vavbvc是最長P3矛盾，所以最長圈不經過va的鄰點這一假設不成立，故最長圈經過va的鄰點。

圖21 va不屬于2個團的交集示意圖

記vf是最長圈C7上的va的鄰點，ve，vr∈C7且是vf的鄰點。根據圖22有，

eef≥eaf+eab+ebc+ece>eab+ebc

(34)

圖22 va的鄰點屬于C7的示意圖

所以有，

eef+erf>eef>eab+ebc

(35)

不等式(35)與vavbvc是最長P3矛盾，所以最長圈C7上不存在va的鄰點，故存在最長圈不經過vc點這一假設也不成立。也就是說若va，vb?S，vc∈S時，圖G的每一個最長圈都經過vc點。

4 結論

圖論中1個很重要的猜想是：2連通弦圖的所有最長圈必定經過同1個頂點。文中研究了邊賦權簡單圖(極大團不超過2個的圖)的最長圈性質，證明了2連通邊賦權簡單圖(權值為正數(shù))所有最長圈都經過同1個頂點。后續(xù)工作將進一步研究邊賦權區(qū)間圖的結構性質，為最終解決該猜想提供啟發(fā)和幫助。