有一个M,一个nxn矩阵,每个条目等于0或1. m ij 表示第i行和第j列的条目.对角线条目是某些i 的形式m ii之一.交换矩阵M的行i和j表示以下动作:我们将值m ik和m jk交换为k = 1,2 ..... n.类似地定义交换两列.我们说M是可重排的,如果可以交换一些行对和一些列对(以任何顺序),这样,在所有交换之后,M的所有对角线条目都等于1.
我需要找到一个多项式时间算法,确定具有0-1个条目的矩阵M是否可重排.
我知道我必须使用max-flow/min-cut范例来解决这个问题,但我找不到将这个问题与最大流量问题联系起来的方法.
任何暗示都是受欢迎的!
很简单地表明矩阵是可重排的,当且仅当在S n中存在置换pi时,对于每个i ,M i,pi(i) = 1.
这种置换只是二分图中的完美匹配,其具有每行的顶点,每列的顶点,以及当i i = 1 时恰好在行i和列j之间的边缘.
使用max-flow在二分图中找到最大匹配是非常简单的; 当最大匹配是完美匹配时,你有一个可重排的矩阵.