Homework 9

Due Monday, February 24 at 5:00 PM. Please refer to the homework policy here.

Problems

  1. Let be a directed graph. We define a set function by defining, for a set , to be the number of edges leaving :

    1. A set function is submodular if for any two sets ,

      Prove that is submodular.

    2. 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.

    3. 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 .

  2. Let be a directed capacitated graph. Let be defined by

    Prove the following ``triangle inequality'' for cuts: for all distinct ,