Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (oldest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Some mistakes | Reply
I've found some small mistakes with the figures in the article.

In Section 1:

...Let's color in yellow, like in the figure above, every vertex that is reachable by a path that starts from the source and consists of non-full forward edges and of non-empty backward edges...

Shouldn't it be like in the figure below?

In Section 2:

...Now suppose we add 1 to the capacity of each edge. Is a minimum cut in the original network a minimum cut in this one? The answer is no, as we can see in Figure 8 shown below, if we take T = 2.

Shouldn't it be Figure 9?

Regarding to the article, I would like to know why are there at most N*M/2 steps in the max flow algorithm when using BFS to find augmenting paths, how can it be proved?

Thanks in advance :)