[ 掲示板に戻る ]
記事No.66738に関するスレッドです
★ 最小費用流問題について / ケビン
現在大学二年生でグラフ理論について勉強しているものです。
最小費用流問題の制約条件について質問があります。下記画像のような制約条件があったのですが、これは(ノードから出ていくフロー)ー(ノードに入ってくるフロー)＝𝑏𝑖 という意味だと思うのですが、この制約条件にΣが必要な理由がわかりません。例えばノードBにおいて出ていくフロー2-入ってくるフロー2=0=biとなっており制約条件は満たしていますよね？これにΣは必要なのでしょうか。わたくしの認識に間違いがあればご指摘宜しくお願いします。
No.66738 - 2020/06/12(Fri) 21:05:26
☆ Re: 最小費用流問題について / X
Bについては確かに出入りのフローの項数がそれぞれ1
ですので、Σがなくても同じ表現になりますが、
他のノード、例えばAについて考えると
出ていくノードの数が2ですので、その意味で
Σが使われています。

ご質問の式は飽くまで全てのノードに対して
一つの式で表現するためにΣが使われています。
(項数が1でもΣを使うこと自体に問題はありません)
No.66739 - 2020/06/12(Fri) 21:23:17
☆ Re: 最小費用流問題について / ケビン
X様回答ありがとうございます。
確認なのですが、ノードAにおいて出ていくフロー(2+1)-入ってくるフロー0=3の2+1のこの+の部分がΣに相当していると考えてよいということでしょうか？
よろしければ回答よろしくお願い致します。
No.66740 - 2020/06/12(Fri) 21:43:13
☆ Re: 最小費用流問題について / X
その通りです。
No.66741 - 2020/06/12(Fri) 22:01:11
☆ Re: 最小費用流問題について / ケビン
ありがとうございます。助かりました。
No.66787 - 2020/06/13(Sat) 20:31:51