Graph cuts and removal of edges

53 views Asked by At

I am trying to understand some code from Vladimir Kolmogorov's excellent Graph cut library and I have a question regarding graph construction. Say I have a system of binary variables and I need to represent the following cut costs

E(0, 0)  E(0, 1)
E(1, 0)  E(1, 1)

Furthermore assume these energies are:

A        A
0        0

and the two variables are x and y and the source and sink nodes are represented by s and t:

Now, as I see it for E(0, 0), I will need an edge from x to t and from y to t. They have the capacity A. So if both these edges are cut, both x and y belong to the source node (associated with label 0). So something like:

         s


    x         y               
     \       /  
      \     /
       \   /
        \ /
         t

Now for E(0, 1), I will need another edge going from s to y also with capacity A, so now the Graph looks something like:

         s
          \
           \
            \
             \
    x         y               
     \       /  
      \     /
       \   /
        \ /
         t

Now my question is since s->y has capacity A and y->t has capacity A, can I remove these two edges without changing the minimum cut on this graph? The reason I ask is that this construction is indeed given by a single edge from x to t (in the source code from Kolmogorov's library) and I cannot understand this construction.

0

There are 0 answers