積分定理は、フロー ネットワークのすべての容量が整数である場合、すべての値が整数である最大フローがあることを示しています。
しかし、最も顕著な部分は存在であり、すべての最大フローではありません! つまり、このステートメントは、すべての最大フローが整数値であると主張しているわけではありません
すべての容量が整数の場合、理由がわかりませんが、整数値ではない最大フローが存在します!!
それとも、私に教えようとするこの定理について間違った考えを持っていたのでしょうか?
質問する
7935 次
2 に答える
9
させて
- e = グラフのエッジ。
- c(e) = 与えられたエッジ e の容量
- f(e) = 特定のエッジ e を通過するフローの量
定理は次のように述べています。
グラフ内のすべてのエッジ e の c(e) が整数の場合、すべてのフロー値 f(e) が整数である最大フロー f が存在します。
定理はf(e)に制約を課していないことに注意してください。
c(e)のみが整数でなければなりません。
「c(e) は整数でなければならない」ということは、「f(e) は整数でなければならない」という意味ではありません。
したがって、整数容量を持つ非整数フローを持つことは完全に有効です。
以下は、すべての容量が整数であり、最大フローが整数でないフローを持ついくつかのエッジを持つ例です。
G は、私が使用しているフロー グラフです。N は、最大の整数フローです。N` は、いくつかのエッジを持つ最大フローであり、非整数フローがあります。
エッジのペア番号の形式は「フロー/容量」です。
定理は、f(u,v) の上限が整数であるとだけ述べていることを思い出してください..下限については何も述べていません..したがって、フローは 0 と c(u,v) の間の任意の数になる可能性があります。
于 2015-11-24T05:36:35.540 に答える