given weighted directed graph, want find globally minimal cut - is, set of edges if removed separate graph in 2 halves , have minimal amount of total weight compared other such cut.
now, although following seems work, i've been told reasoning wrong. quite frankly, don't see how , i'm not sure how was:
consider sets of nodes u,v separated globally minimal cut (i.e. s-t-cut, s in u, t in v). note: don't care edges v u.
for u in u, v in vm u-v-cut cannot smaller s-t-cut, otherwise, s-t-cut not (globally) minimal. same reason, no cut between 2 vertices in u or 2 vertices in v can smaller.
on other hand, u-v-cut cannot greater either, otherwise, need include edges u->v not part of s-t-cut, means s-t-cut no cut @ all.
it sufficient, therefore, fix s arbitrarily , iterate on other vertices x. s either in u, s-x-cut corresponds global minimum if x in v, or x-s-cut if s in v , x in u. if both part of same set, cut @ least great (but possibly greater) global minimum.
therefore, find global minimum calculating both, , keeping track of minimum cut encountered far.
it seemed make sense me. wrong? , if so, why?
my interpretation you're asking following question:
can find global minimum cut fixing arbitrary vertex s , computing s-t , t-s min cuts vertices t != s?
the answer yes, , it's easy prove: consider global min-cut (u, v) value c. either s in u or s in v.
case 1: s in u. definition of minimum cut have v != {}, there vertex t in v. (u, v) valid s-t cut, minimum s-t cut have value @ c
case 2: s in v. there exists vertex t in u , same argument above holds minimum t-s cut
this algorithm described example in chapter 6.4 of these mit lecture notes.
Comments
Post a Comment