Reference no: EM132296524

We are given an undirected graph G=(V,E) and integer values p(v) for every vertex v ?∈(V)? . We would like to know if we can orient the edges of G such that the directed graph we obtain has at most p(v) arcs incoming to v (the "indegree requirements"). In other words, for each edge {u, v}, we have to decide whether to orient it as (u,v) or (v,u), and we would like at most p(v) acrs oriented towards v.

(a) Formulate the problem of deciding whether an orientation exists, as a bipartite matching problem on a graph H = (A ?∪? B, F), where one side (say A) of the bipartition corresponds to E and the other side (say B) will have ?∑v?p(v)? vertices.  Specify what the edges of this graph H are, and also what the existence (or nonexistence) of an orientation meeting the indegree requirements means in terms of bipartite matchings in this graph. Briefly justify your answer.

(b) Derive from Hall's theorem on this bipartite graph H a necessary and sufficient condition for the existence of an orientation of G satisfying the indegree requirements.