[ 掲示板に戻る ]
記事No.66788に関するスレッドです
★ 最小費用流問題について / ケビン
大学二年でグラフ理論を学んでいるものです。
最小費用流問題の制約条件で下記画像のようなものがあるのですが、これは（ノードiからノードjに出ていくフロー）-（ノードjからノードiに入ってくるフロー）だと考えています。
ここで疑問があります。下記画像のノードBに注目した場合（ノードBからノードDに出ていくフロー）2-（ノードDからノードBに入ってくるフロー）0=2となりませんか？それとも、私の考え方が間違っているのでしょうか。
No.66788 - 2020/06/13(Sat) 20:39:50
☆ Re: 最小費用流問題について / ケビン
つまり何が言いたいのかというと、A->Bに入ってくるフローを考慮できていないのではないかということです。
No.66790 - 2020/06/13(Sat) 22:45:26
☆ Re: 最小費用流問題について / X
間違えています。
制約条件のΣの下の条件である
(i,j)∈E,(j,i)∈E (A)
において、Eはノードの始点と終点の組
を要素とする集合を指しています。

よって、(A)においてi=B
としているのであれば
(B,D),(D,B)
の他にも
(B,A),(A,B)
についても考える必要があります。
No.66797 - 2020/06/14(Sun) 00:19:48
☆ Re: 最小費用流問題について / ケビン
> (i,j)∈E,(j,i)∈E (A)
> において、Eはノードの始点と終点の組
> を要素とする集合を指しています。

X様　回答ありがとうございます。
ここで言っているノードの始点と終点とはどこのことでしょうか。i=Bとしたとき始点がA、終点がDになるんでしょうか？
No.66868 - 2020/06/14(Sun) 22:23:01