Instance of Ford Fulkerson violating property
Somehow I created this graph which seems to violate one of the properties that the value of flow is upper bounded by the capacity of min cut.
Here's the graph:
Max flow that the algorithm finds is 7. (sending 3 on s-a-c-t, 3 on s-b-t and 1 on s-a-t)
While the min-cut in the graph is {s,b} , {a,c,t} with capacity 5.
I'm not sure where I'm going wrong in this. Can someone please correct this?
The value of a cut is the sum of the capacities of the edges that are "cut".
In the case with cutting the graph into {s,b} and {a,c,t}, the edges are s-a, b-t, (and you can count a-b if you want), which means the value is 8 (11 if you count a-b), not 5.
As far as I can tell, the min cut would include the edges a-t, b-t, and c-t, which has a value of 7, which is consistent with Ford-Fulkerson.
- Smallest number that cannot be formed from sum of numbers from array
- What's a fast way to identify all overlapping sets?
- minimax losing only in one case of tic-tac-toe
- Is the inorder predecessor of a node with no left subtree and being the left child of its parent always its grandparent?
- (a * b) / c MulDiv and dealing with overflow from intermediate multiplication
- What is the fastest way to compute sin and cos together?
- How to find optimum combination for Cutting Stock Problem using Knapsack
- How fast can you detect if two rows in an n by n binary matrix have (at least) two bits in a common position?
- MaxCounters (lesson 4 in codility) - 100% correctness but 60% on efficiency, why?
- How to calculate rounded corners for a polygon?
- Is the Inorder Predecessor of a Node with a Left Subtree Always a Leaf Node in a Binary Search Tree?
- Codility Leader Algorithm in JavaScript
- Tricky Google interview question
- Java problem time limit exceeded issue
- Can we get a better complexity than O(n) for cumulative sum while using multithreading?
- Fastest method to define whether a number is a triangular number
- What is a plain English explanation of "Big O" notation?
- How can I get the length of repeating decimal?
- Splitting dag dependencies in python
- How to find the time comlexity when comparing sublists?
- Clarification on `length = prefixTable[length - 1]` vs. `length = length - 1` in the KMP Algorithm
- Swapping two numbers using only two variables
- Fastest way to fill an array with a single value
- Algorithm for minimizing the amount of lines to draw?
- Convert Excel Column Number to Column Name in Matlab
- Find n-element in sequence. How to speed up the programm (time) for n > 10^6?
- O(n log n) algorithm to find number of large inversions
- Algorithm for drawing lines with 90-degree angles
- Depth First Search v.s. Greedy Best First Search
- How to improve pandas DF processing time on different combinations of calculated data