グラフ理論

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

No.2 ベストアンサー 回答者： Tacosan 回答日時： 2009/09/07 02:17

フローは普通「物資の流れ」で説明するかな.

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

この回答へのお礼

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

お礼日時：2009/09/07 12:27

No.1 回答者： Tacosan 回答日時： 2009/09/07 00:09

質問の内容がよくわからないんですが....

「最小カット」とか「最大フロー」の意味がわからない?
「カット」や「フロー」はわかる?

この回答への補足

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

補足日時：2009/09/07 00:27