グラフ理論

質問

添付ファイルの問題でいう，最小カットと最大フローとは何を示すのですか？

回答No.2

Tacosan · ベストアンサー

フローは普通「物資の流れ」で説明するかな.
A点から B点まで物資を輸送することを考えます. このとき,
・A点と B点以外では物資の増減はない
・どの辺も指定された容量を越えて物資を送ることはできない
という制約を与えます. この制約を満たす「物資の送り方」はいろいろあるわけですが, これらを「フロー」と呼びます. 数学的には各辺に対して輸送量を定める関数として定義するのが普通.
で, カットのうち「カットに含まれる辺の容量の和が最小のもの」を「最小カット」と呼び, フローのうち「輸送する物資の量が最大となるもの」を「最大フロー」と呼びます.

お礼

ご回答ありがとうございます。

回答No.1

Tacosan

質問の内容がよくわからないんですが....
「最小カット」とか「最大フロー」の意味がわからない?
「カット」や「フロー」はわかる?

補足

そうです。最小カットや最大フローの意味がわかりません。
カットの意味はわかりますが，フローはわかりません。