ソートネットワークの削減

Question

ソートネットワークは、2つの入力コンパレータの配列で、n個の要素の入力シーケンスをソートできます。 は、例えば、ここでソーティングネットワークは、9素子の入力のための：

縦線のそれぞれが、2入力比較器であり、入力シーケンスは、左側に入り、ソート順序が右側に表示されます。

私の質問は、有効なn入力ソートネットワークのトップラインまたはボトムラインを削除すると、（n-1）個の入力に対して有効なソートネットワークが完成することを証明する方法ですか？中間線の削除はどうですか？

これはソートネットワークのグラフ表示を使用して表示できると感じましたが、適切な表現が見つかりません。

Answer 1

本当にトップラインまたはボトムラインを削除できます。これを証明する1つの方法は、0と1のすべてのシーケンスが正しくソートされている場合にのみソートネットワークが正しいことを示すKnuthの0-1原則を使用することです。 Sをソートネットワークとし、S'をSとし、一番上の行を削除します。 xをS'の0-1入力とします。 0xをSに渡します。誘導によって、kステージ以降の値が一致することがわかります（削除されたトップラインを除いて）。トップラインを含むすべてのゲートがno-opsです。したがって、S'は正しいソートネットワークです。

一般に、中間行は削除できません。例えば、ネットワークを考えてみてください。