整数の容量を持つフローグラフは、その最大フローに非整数フローを持つエッジを持つことができますか？

問題を少し修正する：我々は、整数の容量を持つフローグラフGを持っています。最大の流れを見つけることができますか？エッジの少なくとも1つについて、e、f（e）が非整数に等しいか？整数の容量を持つフローグラフは、その最大フローに非整数フローを持つエッジを持つことができますか？

私はこれを最初に試してみましたが、これは一貫性定理に違反し、それが偽であると思っていましたが、それを注意深く読んでも何の規則も破らないことが明らかになりました。どうやらそれは本当です。

私はビジュアライゼーションを得るための簡単な例を描こうとしてきましたが、何も出てこないようです。誰でも私にこのフローグラフの例を示すことができますか？

あなたはhttps://en.wikipedia.org/wiki/Max-flow_min-cut_theoremを知っていますか？ –

待って、そのようなフローが存在するかどうか尋ねていますか？もちろん、頂点から複数の出力エッジがあり、それらの合計容量が入力容量より大きい場合は、任意の方法でフローを分割できます。しかし、非整数フローを使う必要はありません。 –

ああああ、それは今明らかです。ありがとうございました。 –

はい、maxflowには、すべての積分容量を持つグラフを持つエッジで非積分フローを持つことができます。画像を参照してください。ボックス内の値はフローであり、ボックスなしの数値は容量です。

PS：不可欠な能力を持つグラフは常に整数maxflow値を持っていることを覚えておいてください。しかし、エッジ上に非整数フローを持つ最大フローの可能性を排除するものではありません。

2016-11-23 23:34:20 foo

@ Maximus Hermius、もしこれが正しい答えだと思うなら、それを受け入れることができますか？ – foo

Ford Fulkersonアルゴリズムを適用すると、すべてのフロー値とすべての残存容量が実行中に整数のままです。これは、少なくとも1つの整数要素のみのフローが存在することを意味します。

2017-04-12 16:44:03

答えて