1. Let G = (V, E) be a directed graph. We define a set function f : 2V + R by defining, for a set S CV, f(S) to be the number of edges leaving S: f(S) = \{(u + v) E: u ES, ve T}|| a. A set function g:2V + R is submodular if for any two sets A, B CV, g(A) + g(B) > 9(AUB) + g(An B). Prove that f is submodular. b. A set function g:2V + R is symmetric if g(S) = g(V \S) for all S CV. A graph is Eulerian if every vertex has the same number of outgoing edges as incoming edges. Show that f is symmetric iff G is Eulerian. c. A set function g:2V + R is posi-modular if for all sets A, B C V, we have g(A) + g(B) > 9(B \ A) + g(A | B). Show that if G is Eulieran, then f is post-modular. Note that the above properties hold also in capacitated (i.e., weighted) graphs, where we define f(S) to be the total capacity of all edges leaving S. 1. Let G = (V, E) be a directed graph. We define a set function f : 2V + R by defining, for a set S CV, f(S) to be the number of edges leaving S: f(S) = \{(u + v) E: u ES, ve T}|| a. A set function g:2V + R is submodular if for any two sets A, B CV, g(A) + g(B) > 9(AUB) + g(An B). Prove that f is submodular. b. A set function g:2V + R is symmetric if g(S) = g(V \S) for all S CV. A graph is Eulerian if every vertex has the same number of outgoing edges as incoming edges. Show that f is symmetric iff G is Eulerian. c. A set function g:2V + R is posi-modular if for all sets A, B C V, we have g(A) + g(B) > 9(B \ A) + g(A | B). Show that if G is Eulieran, then f is post-modular. Note that the above properties hold also in capacitated (i.e., weighted) graphs, where we define f(S) to be the total capacity of all edges leaving S