1
$\begingroup$

I am trying to solve the following problem about maxflow mincut it seems like my conclusion is incorrect and I am wonder where.

There is no graph just following question.

An edge e can be (x) always full, (y) sometimes full, (z) never full; it can be (x') always crossing, (y') sometimes crossing, (z') never crossing. So there are nine possible combinations: (xx') always full and always crossing, (xy') always full and sometimes crossing, and so on. Or are there? Maybe some possibilities are impossible. Let's draw a table:

enter image description here

Possible answers ---based on my conclusions

  • always full and always crossing. (true based on the image above)
  • always full and sometimes crossing. (true based on the image above and the fact that we may have several crossing edges one of them may be full, all them if all edges in the min cut is 1 and one of the crossing edges is 2)
  • always full and never crossing. (false seems like there always must be a possibility of one of the ways to use edge with less capacity)
  • sometimes full and always crossing. (true if we have all edges in the mincut that are 1 and crossing edge is two)
  • sometimes full and sometimes crossing.( false since if we have many crossing edges that are 1 and one of them is 2 means that we might want to use the edge 2to flow more)
  • sometimes full and never crossing. (true easy to see and edge that sometime full but never crossing in a graph)
  • never full and always crossing. (true if all edges in a mincut is 1 and crossing edge is two)
  • never full and sometimes crossing. (true if we have many 2 crossing edges)
  • never full and never crossing. (true if we have a graph where one edge is 2 in min cut that never crossing)

Have asked this question on /math.stackexchange.com with no luck.

wording used.

The edge is full means in in any way we pump the flow the edge is always going to be full, basically if we have and C---(1)---A------(1)----B and there is no other way to get to B other then going thru a then A is always full. Somewhat full if we can have C---(1)---A------(1)----B and if there is another way to get to b by doing C---(1)---E---(1)----B then edge is only sometime full. never full if we have C---(1)---E---(2)----B then most we can flow is 1 but b takes 2 then it never full. The crossing part if we it can be the crossing edge in the min-cut from the cut to the sink. basically it and edge that connects the cut with the rest of flow.

Thanks.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Your terminology (full, crossing, and so on) is non-standard. Can you explain it? $\endgroup$
    – Yuval Filmus
    Commented Oct 3, 2018 at 5:35
  • $\begingroup$ @YuvalFilmus just updated $\endgroup$
    – COLD TOLD
    Commented Oct 3, 2018 at 5:55
  • $\begingroup$ 1. Your definition of full is circular: you say "an edge is full if ... it is always going to be full". You defined the word full in terms of itself! Can you try a clearer definition? 2. I don't understand your definition of the word "crossing". Can you edit to try to provide a clearer definition of that? And once again, try to avoid using the word in its own definition. You define what it means for an edge to be crossing by talking about if it can be a crossing edge -- sounds circular to me. $\endgroup$
    – D.W. ♦
    Commented Oct 3, 2018 at 7:52
  • $\begingroup$ An accepted answer should illustrate all possible cases with a graph and explanation as well as explain why all other case are impossible in words. $\endgroup$
    – John L.
    Commented Oct 3, 2018 at 14:10

1 Answer 1

Reset to default
0
$\begingroup$

This is the previous question which defines the terms. I hope this helps you solve the question.

enter image description here

Thus question provides these as true:

  • always full and always crossing.
  • always full and sometimes crossing.

We know from the definitions I've provided that the following are also true:

  • sometimes full and never crossing
  • never full and never crossing

This is all. The answer is included in the definitions.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Your post looks like a comment about terminology, not actual answer. Could you elaborate? (I see that in the picture are some answers, but the source is not credited and content not searchable). $\endgroup$
    – Evil
    Commented Jan 3, 2019 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.