边赋权简单图最长圈问题研究

张智微，李 鹏

(重庆理工大学 理学院， 重庆 400054)

密尔顿圈(路)问题是图论中最熟知的NPC问题之一，而其最自然的推广就是最长圈(路)问题，即寻找给定图中所包含顶点个数(或边数)最多的简单圈(路)。最长圈(路)问题是图论的一个研究热点之一，围绕它有大量的工作出现，如研究最长圈(路)的结构性质[1，4，5，8-9，14]，研究最长圈的多项式算法[2，7，12-13]，研究最长圈的近似算法[3，6，15]以及其他相关问题[10-11]等。

弦图是不包含长度大于等于4的诱导圈的图，它是图论很重要的基础图类。区间图是这样的图类：它的顶点可以和数轴上的区间一一对应，2个顶点之间有边当且仅当它们对应的区间相交。熟知的是区间图是弦图的一个子类。

图论中一个很重要的猜想是：2连通的弦图的所有最长圈一定经过同1个顶点。围绕这个猜想，图论工作者进行了大量的研究，但始终无法解决这个猜想。与这个猜想紧密相关的另1个猜想是：2连通边赋权简单图(权值为正数)所有最长圈都经过同1个顶点。本文主要研究边赋权简单图(极大团不超过2个的图)的最长圈性质，证明了该猜想在2连通的边赋权简单图是正确的。

1 预备知识

在图论中，图中一条路径指的是一顶点序列：v1,v2,…,vn。序列中任何相邻的2顶点都可以在图中找到对应的边。一条路径的长度是这条路径所包含的边数。圈指的是在图中任选一个顶点，沿着不重复的边，经过不重复的顶点为途径，之后又回到起点的闭合途径。重边指的是具有一对顶点的多条边。若一个图不含圈和重边，则称此图为一个简单图。设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条边赋予一定的权数，记为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连通边赋权简单图(权值为正数)所有最长圈都经过同1个顶点。后续工作将进一步研究边赋权区间图的结构性质，为最终解决该猜想提供启发和帮助。