为什么很多网络流问题总有整数解——全单模矩阵的性质





以前在Online Judge上遇到过很多问题需要转化为网络流模型,原问题一般是要求有整数解的。但是转化为网络流问题后虽然边上的最大流上限都是整数,其实并没有要求最大流也是整数,可求出来的最大流就是整数。我以前一直迷茫这个现象,并且我是很懒的人,一直没有严谨的想过这个问题或者查过这个问题。我们课题组平时很少讨论整数规划的问题,所以这个其实比较基本的问题我一直都不知道。其实你可以从直观感觉如果有非整数的流,那总应该能再怎么样多流一点变成整数,不过这显然是直观感觉,什么也说明不了。昨天看书看到有讲这些,终于理解了,在这总结一下。
首先说说全单模矩阵的定义:一个矩阵如果任意子方阵的行列式都只等于1,0,-1,那么就说这个矩阵是全单模矩阵。
定理:如果A是全单模矩阵,A是满秩的(行列式不等于0),且b的每个分量都是整数,那么Ax=b的解肯定是整数。
这个定理从克莱姆法则很容易看出来是正确的。忘记克莱姆法则的请自行搜索。
进一步考虑整数规划问题:
\min. c^Tx
s.t. Ax \le b, x \in \mathcal{Z}_+^n
这个问题忽略掉整数约束的话,就变成一般线性规划,如果学过单纯形法,应该知道最优解对应A的一个子矩阵B,也即基矩阵。如果A是全单模的,b的分量都是整数,那么A的每个子矩阵都应该还是一个全单模矩阵,B也是一个全单模矩阵,所以根据上面定理,最优解就是整数解。于是即使去掉整数约束,解仍然是整数。
图论中的许多问题无非就是求解一个最优化问题,只是如何转化而已。常用的办法是关联矩阵。假设图有N个顶点,M条有向边,则对应一个关联矩阵有N行M列,每行对应一个顶点,每列对应一条边。如果边从u指向v,则边对应的列上,u对应的行为-1,v对应的行为1,其余都是0,类似也可以把-1改成1定义无向图的关联矩阵。很多图论经典问题都能转化成和关联矩阵有关的整数规划问题。例如最小费用流问题可以转化为:
\min. c^Tx
s.t. Mx=b, 0 \le x \le h
这里M是关联矩阵,b的每个分量对应顶点上的流需求量(源和汇),h的分量对应每条边上的流限制,c的每个分量对应一条边的费用,x的每个分量对应每条边上的流量。
如果这里M是全单模矩阵,b和h的分量都是整数,那么容易根据上面的结论得出这个问题的解是整数解。对于关联矩阵这个特殊的矩阵有两个很好的结论:

  • 无向图的关联矩阵是全单模的当且仅当是二部图。
  • 有向图的关联矩阵是全单模矩阵。

有了这两个结论我们就可以知道为啥凡是二分图问题或者最大流一类的问题很多都是有多项式解法的,而且不用限制解是整数就都能求到整数解。
这两个定理的证明都不是太简单,都需要使用归纳法还要讨论几种不同情况。不过结论很经典也确实很重要,告诉了我们为什么有些时候整数规划问题是好求解的。

如果你喜欢我的博客,请订阅本博客的RSS以更方便的阅读
欢迎关注我的新浪微博:http://weibo.com/diaorui1987