(逃逸问题) n
n的网格是由n行和n列结点所构成的无向图，如下图所示。我们将位于第i行和第j列的结点表示为(i,j)。除了位于边界的结点外，网络中其他所有结点都有刚好4个邻结点。边界结点指的是满足i=1、i=n、j=1或j=n的结点(i, j)。
在这样的网格里给定m≤n2个起始结点(x1, y1)，(X2， y2)，..., (xm, ym)，逃逸问题要做的事情是判断是否存在从这些起始结点到任意m个不同的边界结点之间的m条结点分离的路径(每条路径之间没有共同结点)。例如，在下图所示的网格中有一个逃逸线路，但下图的网格则没有逃逸线路。
在这样的网格里给定m≤n2个起始结点(x1, y1)，(X2， y2)，..., (xm, ym)，逃逸问题要做的事情是判断是否存在从这些起始结点到任意m个不同的边界结点之间的m条结点分离的路径(每条路径之间没有共同结点)。例如，在下图所示的网格中有一个逃逸线路，但下图的网格则没有逃逸线路。
a.考虑一个结点和边都有容量限制的流网络。也就是说，进人任何给定结点的正流都要受到容量的限制。证明:在一个结点和边都有容量的流网络中确定最大流的问题可以归约为同等规模流网络中的普通最大流问题。
b.给出一个有效的算法来解央逃逸问题， 并分析算法的运行时间。
b.给出一个有效的算法来解央逃逸问题， 并分析算法的运行时间。
