algorithm - 减少分拣网络

Question

排序网络是 2 个输入比较器的排列，它可以对 n 个元素的输入序列进行排序。例如，这是一个用于 9 元素输入的排序网络:

每条竖线都是一个2输入比较器，输入序列在左边进入，排序后的序列出现在右边。

我的问题是:如何证明如果我们删除任何有效的 n 输入排序网络的顶部或底部线，我们最终将得到一个有效的排序网络(n-1)输入？删除任何中间线怎么样？

我觉得这可以使用排序网络的图形表示来显示，但我找不到合适的表示。

Answer 1

确实可以删除顶部或底部线。证明这一点的一种方法是使用 Knuth 的 0-1 原则，该原则指出当且仅当每个 0 和 1 序列都被正确排序时，排序网络才是正确的。令 S 为排序网络，令 S' 为 S 并移除顶行。设 x 为 S' 的 0-1 输入。将 0x 传递给 S。通过归纳，我们可以证明 k 阶段后的值是一致的(除了删除的顶线)，因为涉及顶线的所有门都是空操作。由此可见，S' 是一个正确的排序网络。

一般来说，我们不能删除中间线。例如，考虑网络

1 *   *
  |   |
2 * * *
    |
3   *