Tag Archives: Hamilton Path

Hamilton路与带下界的网络流

QQ群里戴牛提了这样的一个问题:为什么不能用求解带下界的网络流的方法来做Hamilton问题?详细来说,就是把一个图的每个点拆成两个点,在中间加上一条容量上下界都为1的边,求从一点S到另一点T的流,如果可行流存在,则S,T之间存在Hamilton路。

乍一看上去似乎非常合理,当然,我们知道肯定是有哪里出了问题的。因为Hamilton路是经典的NPC,而网络流有无数种多项式做法,如果真的这么把一个NPC解决了,那这几十年以来的计算机科学家们也忒弱了。

问题出在下界的转化那一步。首先来复习一下标准做法:带下界的网络流的求法通常分两步,第一步是判断是否有可行流,然后再求最大流或最小流。这里我们只关心第一步,这一步实际上是把问题转化成了一个点上可以发出或吸收流量的可行环流问题。先形式化一下这个问题(1):

给定网络(V,E),其中每个点i都有一个可正可负的值e[i],每条边(u,v)上有一个容量上界c[u,v]。我们要对每条边[u,v]求一个流量f[u,v],满足f[u,v] <= c[u,v],且Sigma f[u,v] = e[u],这里v取遍u的所有相邻点求和。

也就是说必须满足每个点都可以发出或吸收一定数量的流量,显然要使可行流存在必须有Sigma e[u] = 0,u取遍所有点。对这个问题的求解,我们可以添加一个源S和汇T,S向所有e[u]>0的点连边,容量为e[u]。所有e[u]<0的点向T连边,容量为|e[u]|。求最大流,若最大流能把S发出的边充满,则原问题(1)有解。

然后我们来看下界的转化。设每条边(i,j)有上界U[i,j]和下界L[i,j],流量f[i,j]须满足L[i,j] <= f[i,j] <= U[i,j],我们把它们全减去L[i,j],即0 <= f[i,j] – L[i,j] <= U[i,j] – L[i,j]。可以发现,这样变成了只以(U[i,j] – L[i,j])为上界的边。但是因为流入的量减少了L[i,j],我们必须把它补偿上,也就是说必须强制点j“发出”一份L[i,j]的流量,这个就对应了上面的e[]。同时,强制点i“吸收”一份L[i,j]的流量。

于是转化方法就是,把边的上界变成U[i,j]-L[i,j],然后令e[i] = Sigma L[i,j] – Sigma L[k,i]。这里j取遍所有i指向的点,k取遍所有指向i的点。然后我们添加一条从T指向S,容量为正无穷的边。求此网络是否存在可行环流。这就回到了问题(1)

注意问题(1)里并没有哪两个点是特殊的源或汇,这是一个环流问题,只要满足每个点的e满足要求就行。对于有源汇的问题,就如上面的转化,加一条从汇指向源的边,容量为正无穷即可。这样就可以让所有流量都再流回去了。但是Hamilton的转化也就在这里出了问题,我们经过转化后求的是可行环流,但这个可行环流并不一定是Hamilton路。原因在于这个环流并不保证连通Hamilton路中的两个端点,我们求出的可能是若干个不相连的环,它仍然是可行环流,满足问题(1)里的所有限制条件,但无法从它构造出Hamilton路。见下例,很明显,1和6之间不存在Hamilton路:

hami1

如果按照上述转化,就得到下图:

hami2

这里i和i’间的虚线本来是上下界都为1的,相减之后没有了。6’到1的虚线是容量为正无穷,其余边容量均为1。图比较乱,仔细看会发现S发出的6条边都能充满,比如S->2′->3->T, S->3′->1->T等等。这个图的可行环流存在。但是这个可行环流实际上是不相关的两部分,所以Hamilton并不存在。

有童鞋可能认为可以求出流来,再判断一下这个环流是不是相通了原来的两个端点。但是这并不是充要条件,我们求出的环流不连通并不说明Hamilton路一定不存在,而我们在求环流时无法强制令其连通。