最大流を辺容量 c : E → ℝ˲₌₀ で考えると容量無限大の辺を使いたいときに困りそう

[kmyk]

related #125 #124

競プロではよく「容量無限大の辺を張れば、……」のようなことを言うと思うんですが、いまの書かれ方 (https://dic.kimiyuki.net/dinic など) だとこのことと相性がよくありません。
c : E → ℝ˲₌₀ ∪{∞} に修正する (解の存在性が常には言えなくなるけど) か、なにか注意 (十分大きな定数 c を使えばよい) を書いておいた方がよさそうです。

参考として、ウィルソン グラフ理論入門では明確に「容量と呼ばれる非負実数 Ψ(a) が定められている」とあり、またアルゴリズムイントロダクションでも無限どうこうの話はしていなさそうに見えます。

[MiSawa]

僕もよく言いますが、それは「容量無限大の辺を張れば〜」と言っている側の問題だという認識です。
正確には「入力の他の部分に依存する充分大きな数が取れて、それを使えば云々」と言うか、「容量無限を許容するインスタンスは容量有限のインスタンスに線形時間で還元できるので云々」と言うべきであって、定義やアルゴリズムの解説側でハンドルするべき問題ではないと思っています。
もしア辞典で注意したいならば、最大流のページでまとめてやるとか、もしくは典型テクのページで無限大(や無限小)の扱い方のようなページにするとよいと思います。

(ちなみに、めちゃくちゃ真面目にやるならば、一次式のフローだと思えば無限を無限と思ったまま色々出来はしますが、そうする必要はあまり無いでしょう。)

[MiSawa]

あ、ちなみに一応書いておくと、容量スケーリング法を使う場合など、有限に帰着するより無限を特殊扱いした方がよい可能性があります。(例えば log nU と log U の差が出るとか)
特に最小費用流の文脈だと容量無限を直接扱う話もあって、「任意の容量有限のインスタンスは、全辺の容量が無限のインスタンスに変換出来る」と「全辺の容量無限の場合に対するアルゴリズム」で話を進める場合もあります。