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

以前在Online Judge上遇到过很多问题需要转化为网络流模型,原问题一般是要求有整数解的。但是转化为网络流问题后虽然边上的最大流上限都是整数,其实并没有要求最大流也是整数,可求出来的最大流就是整数。我以前一直迷茫这个现象,并且我是很懒的人,一直没有严谨的想过这个问题或者查过这个问题。我们课题组平时很少讨论整数规划的问题,所以这个其实比较基本的问题我一直都不知道。其实你可以从直观感觉如果有非整数的流,那总应该能再怎么样多流一点变成整数,不过这显然是直观感觉,什么也说明不了。昨天看书看到有讲这些,终于理解了,在这总结一下。

Continue reading »