Due Monday, February 24 at 5:00 PM. Please refer to the homework policy here.
Let be a directed graph. We define a set function by defining, for a set , to be the number of edges leaving :
A set function is submodular if for any two sets ,
Prove that is submodular.
A set function is symmetric if for all . A graph is Eulerian if every vertex has the same number of outgoing edges as incoming edges. Show that is symmetric iff is Eulerian.
A set function is posi-modular if for all sets , we have
Show that if is Eulieran, then is post-modular.
Note that the above properties hold also in capacitated (i.e., weighted) graphs, where we define to be the total capacity of all edges leaving .
Let be a directed capacitated graph. Let be defined by
Prove the following ``triangle inequality'' for cuts: for all distinct ,