algorithm - ネットワークにおけるフロー分解定理

Question

Robert Sedgewick によるアルゴリズムの第 2 巻を読んでいます。このセクションは、ネットワーク フロー アルゴリズムからのものです。

以下に述べるフロー分解定理とその帰結を理解するのに苦労しています。

流れ分解定理: 任意の循環は、最大で E 個の有向エッジのセットに沿った流れとして表すことができます。

系 1: どの st-network にも maxflow があり、非ゼロフロー値によって誘導されるサブグラフは非循環的です。

系 2: 任意の st-network には、s から t への最大 E 個の有向パスのセットに沿ったフローとして表すことができる maxflow があります。

簡単な例で上記の定理と系を理解するのを手伝ってくれるようお願いします ありがとう!

Answer 1

アルゴリズム（の一部）の他の説明にアクセスできる場合は、それらを研究するのに苦労しています。それが気に入らない場合は、コードを書き始めてください。一般に、アルゴリズムを実装すると、アルゴリズムの説明に対する理解が大幅に向上することがわかります。

実際、前の段落の 2 番目の文には同意しません。さらなる研究が必要かどうかにかかわらず、コードを書き始めてください。コーディングせずにアルゴリズムを正しく理解できるとは思えません。傍観者から離れて、ゲームに参加してください。