“Critical Edge” : The definition of critical edge says that it is a edge where decreasing the capacity causes the decrease of max-flow … We can now say that any edge is a critical edge so that you can decrease the capacity to something less than the current bottleneck edge capacity to reduce the max-flow … Critical edges will hence become bottleneck edges in the graph giving a different min-cut and hence a different max-flow.
A critical edge is one where you can decrease the capacity by a tiny amount (or 1 unit, if you wish), and create a decreased max flow. the intent is not to decrease the capacity by a large amount.
Note also that a bottleneck edge is one where *increasing* by one unit changes the flow.
Can we think of critical edge as an edge whose decrease in capacity decreases maxflow but its increase in capacity will not hurt the max-flow? If this is not the case, reducing the capacity of a bottleneck edge will reduce the maxflow. Hence, every bottleneck edge is also a critical edge …
It’s not clear to me that reducing the capacity of a bottleneck edge reduces the max flow necessarily. It is conceivable that reducing the capacity of a bottleneck edge causes flow to be rerouted somewhere else in order to maintain the same total flow value.
Every augmenting path has a bottleneck edge. This is the edge with minimum capacity. If this value is reduced further, it does not hurt the augmenting path only the flow value … The min-cut still remains the same…
4.4- KT[7.6] : Just to ensure that I understand this problem correctly - to start with, we don’t know the switch which controls a particular light fixture. We are just given n fixtures and n switches, and any switch can be made to control any fixture….
Why I ask this is, because I’m not sure if the example with which the books illustrates this scenario, already assumes that light fixture ‘a’ goes with switch 1, ‘b’ with switch 2.. and so on?
Correct. We don’t know which light controls which fixture and we can control any fixture with any switch, but the line of sight criterion controls what we do
Entries
November 12th, 2007 at 6:26 pm
Why the “!” on 4.d? The “!” is scaring me…
November 12th, 2007 at 7:59 pm
Just wanted to know the HW2 statistics …
November 12th, 2007 at 11:48 pm
Just because it seems surprising to me
November 13th, 2007 at 2:08 am
“Critical Edge” : The definition of critical edge says that it is a edge where decreasing the capacity causes the decrease of max-flow … We can now say that any edge is a critical edge so that you can decrease the capacity to something less than the current bottleneck edge capacity to reduce the max-flow … Critical edges will hence become bottleneck edges in the graph giving a different min-cut and hence a different max-flow.
I think I am missing something …
November 13th, 2007 at 2:11 am
A critical edge is one where you can decrease the capacity by a tiny amount (or 1 unit, if you wish), and create a decreased max flow. the intent is not to decrease the capacity by a large amount.
Note also that a bottleneck edge is one where *increasing* by one unit changes the flow.
November 14th, 2007 at 7:59 pm
Problem 2 is to give an algorithm to find a critical edge in the network. Does it need to find just one critical edge, or does it need to find all?
November 14th, 2007 at 8:25 pm
Finding any critical edge suffices.
November 16th, 2007 at 10:29 pm
Can we think of critical edge as an edge whose decrease in capacity decreases maxflow but its increase in capacity will not hurt the max-flow? If this is not the case, reducing the capacity of a bottleneck edge will reduce the maxflow. Hence, every bottleneck edge is also a critical edge …
November 16th, 2007 at 11:05 pm
It’s not clear to me that reducing the capacity of a bottleneck edge reduces the max flow necessarily. It is conceivable that reducing the capacity of a bottleneck edge causes flow to be rerouted somewhere else in order to maintain the same total flow value.
November 16th, 2007 at 11:10 pm
Every augmenting path has a bottleneck edge. This is the edge with minimum capacity. If this value is reduced further, it does not hurt the augmenting path only the flow value … The min-cut still remains the same…
November 17th, 2007 at 1:10 am
Okay … I get the difference now … A bottleneck edge is not necessarily a critical edge …
November 17th, 2007 at 9:20 pm
btw it is not true that every augmenting path has a bottleneck edge. look at the definition of a bottleneck edge carefully.
November 17th, 2007 at 9:42 pm
Yes. True. At the time I was confused between the textbook’s definition of bottleneck and the homework definition …
November 20th, 2007 at 12:42 pm
4.3.a: Are we to find the actual set of vertices? or just the size of that set?
November 20th, 2007 at 12:52 pm
The set, please.
November 20th, 2007 at 7:26 pm
4.4- KT[7.6] : Just to ensure that I understand this problem correctly - to start with, we don’t know the switch which controls a particular light fixture. We are just given n fixtures and n switches, and any switch can be made to control any fixture….
Why I ask this is, because I’m not sure if the example with which the books illustrates this scenario, already assumes that light fixture ‘a’ goes with switch 1, ‘b’ with switch 2.. and so on?
November 20th, 2007 at 9:28 pm
Correct. We don’t know which light controls which fixture and we can control any fixture with any switch, but the line of sight criterion controls what we do
November 20th, 2007 at 11:49 pm
4.2 (b) Does it ask for just the new MAX FLOW or the entire distribution of flow through the network?
November 20th, 2007 at 11:52 pm
the new max flow, although how you’ll get this without the flow distribution escapes me