algorithm - 最大流量应用程序 : rearrange matrix

Question

有 M，一个 n x n 矩阵，每个元素等于 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 是可重新排列的。

我知道我必须使用最大流/最小切割范式来解决这个问题，但我找不到将这个问题与最大流问题相关联的方法。

欢迎任何提示!

Answer 1

当且仅当在 S_n 中存在置换 pi 使得 M_{i, pi(i)} = 1 时，可以直接证明矩阵是可重排的对于每个 i.

当 M_ij = 1 时，这样的排列恰好是每行一个顶点、每列一个顶点以及 i 行和 j 列之间的边的二分图中的完美匹配.

使用最大流在二分图中找到最大匹配非常简单；当最大匹配是完美匹配时，您就有了一个可重排的矩阵。