邊賦權(quán)簡單圖最長圈問題研究

張智微，李 鵬

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

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

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

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

1 預(yù)備知識(shí)

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

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

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

2 只有1個(gè)極大團(tuán)的圖

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

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

圖1 一個(gè)極大團(tuán)的示意圖

因?yàn)長是最長圈，所以此時(shí)有不等式

epi0+ei0j0+ej0q≤epq

(1)

但實(shí)際上根據(jù)假設(shè)有ei0j0≥epq，且epi0>0，eqj0>0故可得出，

epi0+ei0j0+ej0q>epq

(2)

這與不等式(1)矛盾，所以假設(shè)不成立。故最長圈不可能同時(shí)不經(jīng)過vi0，vj0這2個(gè)點(diǎn)。

因?yàn)樽铋L圈只經(jīng)過vi0，vj02點(diǎn)中的1點(diǎn)，所以可假設(shè)存在最長圈Q滿足vi0?Q，在最長圈Q上任意取1個(gè)點(diǎn)，記為vm，顯然存在邊E(vmvj0)。用路徑vmvi0vj0取代路徑L可得到1個(gè)新的圈，記為Q′。

此時(shí)有emi0+ei0j0>emj0，Q′成為最長圈， 這與Q是最長圈矛盾。假設(shè)不成立，說明每個(gè)最長圈都要經(jīng)過vi0，vj0這2個(gè)點(diǎn)。

綜上所述，當(dāng)簡單圖只有1個(gè)極大團(tuán)時(shí)，圖的每1個(gè)最長圈都要經(jīng)過圖中相同的2個(gè)點(diǎn)。

3 2個(gè)團(tuán)的二連通圖

為了方便理解，2個(gè)團(tuán)的二連通圖見圖2。

圖2 2個(gè)團(tuán)的二連通圖的示意圖

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

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

證明：設(shè)2連通圖G存在1個(gè)最長圈L不經(jīng)過vb點(diǎn)，則L也不經(jīng)過va，vc點(diǎn)。

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

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

根據(jù)假設(shè)有eaa′≥eab+eba′，但是實(shí)際上對(duì)于路徑vava′vb，有

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

(3)

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

其次，假設(shè)L經(jīng)過vc點(diǎn)，在最長圈L上任取一個(gè)vc的相鄰點(diǎn)記為vc′，圖形見圖4。

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

對(duì)于路徑vcvc′與路徑vcvbvavc′有：

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

(4)

這與vavbvc是最長P3矛盾，故此假設(shè)不成立，所以最長圈L不經(jīng)過vc點(diǎn)。綜上所述va，vb，vc?L。

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

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

則顯然有，

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

(5)

這與路徑vavbvc是最長P3矛盾，故此假設(shè)不成立，所以最長圈L最多不經(jīng)過S中的一個(gè)點(diǎn)。

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

圖6 S存在點(diǎn)不屬于L的示意圖

根據(jù)vavbvc是最長圈這一假設(shè)，有

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

(6)

但是這與vavbvc是最長P3矛盾，所以此假設(shè)不成立，故最長圈都經(jīng)過S中的每一個(gè)點(diǎn)。

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

圖7 以vw為起點(diǎn)和終點(diǎn)的歷程圖

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

es1y+es2z>eyz+eab+ebc

(7)

以vavbvc為起點(diǎn)和終點(diǎn)，按照圖8箭頭指示歷經(jīng)vz，vx，vw，vy，vs1，va，vb，vc，vs2，vz這些點(diǎn)。

圖8 以vz為起點(diǎn)和終點(diǎn)的歷程圖

顯然這也是一個(gè)圈，記為C2。根據(jù)歷經(jīng)的路徑可知，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的每一個(gè)最長圈一定經(jīng)過vb點(diǎn)。

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

證明：假設(shè)存在最長圈C3不經(jīng)vb點(diǎn)，則有va?C3。因?yàn)槿魐a∈C3，在C3上取va的一個(gè)相鄰點(diǎn)記為va1，則根據(jù)圖9有，

eaa1≥eab+eba1

(13)

進(jìn)一步有，

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

(14)

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

圖9 vb不屬于C3的示意圖

若va∈K1+K2-2(K1∩K2)，則最長圈一定經(jīng)過va的相鄰點(diǎn)。因?yàn)槿艏僭O(shè)存在最長圈C4不經(jīng)過va的鄰點(diǎn)，我們可在S中任意選取一點(diǎn)，記為vb1，顯然有vb1?C4。在最長圈C4上任意選取一個(gè)點(diǎn)vm及其個(gè)鄰點(diǎn)vn，vl，那么根據(jù)圖10的插法一，有

emn≥enb1+eb1a+eab+ebm

(15)

圖10 插法一示意圖

根據(jù)圖11的插法二，有

eml≥emb1+eb1a+eab+ebl

(16)

圖11 插法二示意圖

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

emn+eml>2eab≥eab+ebc

(17)

這與vavbvc是最長P3矛盾，所以假設(shè)不成立，故最長圈一定經(jīng)過va的鄰點(diǎn)。

記vd為最長圈C3上的va的鄰點(diǎn)，vm，vn是C3上vd的2個(gè)鄰點(diǎn)，則根據(jù)圖12的插法三，有

emd≥eda+eab+ebm

(18)

圖12 插法三示意圖

根據(jù)圖13的插法四，有

end≥eda+eab+ebn

(19)

圖13 插法四示意圖

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

emd+end>eab+ebc

(20)

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

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

證明：假設(shè)存在最長圈C5不經(jīng)過va點(diǎn)，則有vb?C5。因?yàn)槿魐b∈C5，在C5上取vb的一個(gè)鄰點(diǎn)，記為vb′，則根據(jù)圖14有，

ebb′≥eba+eab′

(21)

進(jìn)一步有，

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

(22)

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

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

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

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

(23)

圖15 插法五示意圖

根據(jù)圖16的插法六，有

egl≥ega+eab+eba′+eal

(24)

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

ehg+egl>2eab≥eab+ebc

(25)

圖16 插法六示意圖

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

記vp是在最長圈C5上的vb的鄰點(diǎn)，vo，vq是C5上vp的2個(gè)鄰點(diǎn)，則根據(jù)圖17的插法七，有

eop≥eoa+eab+ebp

(26)

圖17 插法七示意圖

根據(jù)圖18的插法八，有

epq≥eqa+eab+ebp

(27)

圖18 插法八示意圖

(28)

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

定理5若圖G中的max(P3)=eab+ebc且eab≥ebc。當(dāng)max(P3)∩S≠?，vb?S，va?S時(shí)，圖G的最長圈都經(jīng)過vc點(diǎn)。

證明：假設(shè)存在最長圈C7不經(jīng)過vc點(diǎn)，則有va，vb?C7。因?yàn)閷?duì)于點(diǎn)vb，若vb∈C7，在最長圈上取一個(gè)點(diǎn)記為x1，x1需滿足x1≠a，則根據(jù)圖19有，

ebx1≥ebc+ecx2>ebc

(29)

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

ebx1+eab≥eab+ebc

(30)

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

圖19 最長圈C7的示意圖

對(duì)于點(diǎn)va，若va∈C7，則可在最長圈C7上任取一個(gè)va的相鄰點(diǎn)，記為vx2。根據(jù)圖20構(gòu)造一個(gè)新的路徑vavbvc，有

eax2≥eab+ebc+ecx2>ebc

(31)

圖20 va屬于C7的示意圖

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

eax2+eab≥eab+ebc

(32)

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

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

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

(33)

此不等式與vavbvc是最長P3矛盾，所以最長圈不經(jīng)過va的鄰點(diǎn)這一假設(shè)不成立，故最長圈經(jīng)過va的鄰點(diǎn)。

圖21 va不屬于2個(gè)團(tuán)的交集示意圖

記vf是最長圈C7上的va的鄰點(diǎn)，ve，vr∈C7且是vf的鄰點(diǎn)。根據(jù)圖22有，

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

(34)

圖22 va的鄰點(diǎn)屬于C7的示意圖

所以有，

eef+erf>eef>eab+ebc

(35)

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

4 結(jié)論

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