ノード・ディスジョイント・パスとは何ですか？

Question

正確にノードが離れているパスについての説明が必要ですか？ 2つのノード間のノード - ディスジョイントパスの最大数を決定する方法有向グラフにおけるソースとシンク（t）。誰でもグラフで説明することはできますか？

Answer 1

パスは、頂点のシーケンスです。s, v_1, .., v_m, tです。任意の有効なiとjに対してv_i != u_jの場合、2つのパスs, v_1, .., v_m, tとs, u_1, ..., u_k, tをノード・ディスジョイントといいます。

この問題は、各頂点（ソースとターゲットを除く）を2つに分割し、最初のコピーから2番目のコピーにエッジを追加し、すべてのエッジをリダイレクトすることで、最大数のエッジ - この頂点で最初のコピーで終わり、2番目のコピーからすべての出て行くエッジ。その後、答えはこのグラフの最大フローです（すべてのエッジは単位容量を持つ必要があります）。