Further questions

I referred to two things in class today as good candidates for questions on the next homework.

The first was about finding the minimum mean cycle. Suppose you modify edge costs by subtracting a constant from each. If the constant is just right (exactly the minimum mean cycle cost), then the minimum mean cycle will now have cost 0. If the constant is just a bit larger, the same cycle will have cost that is just a bit negative. How can you set the constant so that you are sure only the minimum mean cycle(s) will have negative cost?

The second question relates to what I claimed about flow-equivalent trees in undirected graphs. I claimed that there was always a flow equivalent path. Think about building a flow-equivalent tree (there are simpler algorithms than the one we discussed in class because you don't have to worry about cut equivalence) and see what you could do to make the algorithm build a path.