0
$\begingroup$

This question already has an answer here:

There are possibly several min-cuts for the source and target nodes of a graph. I think I can determine the same min-cut for the same graph by putting the following restriction

"if there are several min-cuts, then I select the min-cut consisting of edges closer to the source atom. By saying close to source atom, I mean you start to travel from the source to the target, then an edge, which is in a min-cut you first encounter"

a,b and c are nodes, A, B and C are edges. The most left node is the source and the most right node is the target.

Example (1)

a --A--> b --B--> c

two sets: {A} and {B}. we chose {A}.

Example (2)

a --A--> b --B--> c

a --C--> d --D--> c

Four sets: {A, C}, {A,D},{C,B} and {B,D}. we chose {A, C}.

Example (3)

a --A--> b --B--> c

a --C--> b --D--> c

Two sets: {A,C} and {B,D}, we choose {A,C}.

We can keep trying, but I think all other graphs are combinations of these 3 examples (I may be missing some cases).

(1) So, I want to prove that by doing that way, I alway find a same min-cut for the same graph if I run the algorithm many times.

If I am right, how can I prove (1)?

or I am thinking too much about a very obvious fact? (^&^)

$\endgroup$

marked as duplicate by D.W. algorithms Mar 26 '17 at 23:05

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Try to define "the min-cut consisting of edges closer to the source atom" more formally, as the minimum cut minimizing (or maximizing) some objective function. Then you can try to prove that this minimum (or maximum) is unique. $\endgroup$ – Yuval Filmus Mar 26 '17 at 6:18
  • $\begingroup$ @YuvalFilmus Now is it more formal? $\endgroup$ – alim Mar 26 '17 at 6:25
  • $\begingroup$ No. A more formal statement would be "the minimum cut minimizing the sum of distances of the cut edges from the source", if that's what you mean. $\endgroup$ – Yuval Filmus Mar 26 '17 at 7:55
  • $\begingroup$ @YuvalFilmus I see what you mean. thank you. $\endgroup$ – alim Mar 26 '17 at 17:26