Solutions for some Classroom Problems.

1. Given an undirected graph and for each vertex v, two non-negative integers
d_{in}(v) and d_{out}(v), is it possible to assign directions to the edges
such that vertex v has d_{in}(v) edges entering it and d_{out}(v) edges
leaving it?

First, there are some simple necessary conditions. For every vertex v,
d_{in}(v) + d_{out}(v) = d(v), the degree of the vertex in the undirected
graph. Also, sum_v d_{in}(v) = sum_v d_{out}(v) = number of edges in the
undirected graph, as edge contributes 1 to both sums.


Now construct a network as follows. Replace each undirected edge by two 
oppositely directed edges of capacity 1. For each vertex v, assign a demand
d(v) = d_{in}(v) - d_{out}(v). Now the claim is that it is possible to
assign directions iff there exists a feasible flow in the network.


If it is possible to assign directions, simply send 1 unit of flow along
each edge in the direction assigned to the edge, and 0 in the opposite
direction. This flow meets the demand constraint at each vertex.

Conversely, suppose there exists a feasible flow. We may assume the flow 
is 0 or 1 in each edge, and for any oppositely directed pair of edges, it
is 0 in at least one of them. (If it is 1 in both, we can make it 0 in both,
and still get a feasible flow). For edges which have flow 1, assign a direction
in the direction of the flow. This will assign directions to some of the
edges, but some edges may not have any flow.
For any vertex v, the number of edges assigned direction into v - number
of edges assigned direction out of v = d_{in}(v)-d_{out}(v) by the demand
constraint. This implies that the number of undirected edges incident with v
that remain must be even. Therefore, in the graph formed by the edges
remaining undirected, every vertex has even degree, and hence each component
has an Eulerian cycle. Assign directions to these edges in the direction of
traversal of the Eulerian cycle. This adds the same value to the indegree
and outdegree of each vertex, and preserves their difference. Thus, finally,
for every vertex v, indegree = d_{in}(v) and outdegree = d_{out}(v).


2. Given a directed acyclic graph, find the minimum number of paths such
that every vertex is contained in at least one path.


Since the paths are allowed to overlap, we may assume each path starts with
a vertex of indegree 0 and ends with a vertex of outdegree 0.
Add a dummy source and edges from the source to vertices of indegree 0.
Add a sink and edges from vertices of outdegree 0 to the sink.
Split every vertex v in the original graph into two vertices v_{in}, v_{out},
such that edges entering v, enter v_{in} and edges leaving v leave from
v_{out}. Add an edge from v_{in} to v_{out} and assign a lower bound of 1
on the flow through this edge. All other edges have lower bound 0. The upper
bound is large (n) for every edge. Add another edge from the dummy sink to
the dummy source, with capacity k. 

Now, the claim is there exist k paths in the acyclic graph that cover all
vertices if and only if there exists a feasible flow in the network.
If there exist k paths, we can assume each path starts with a vertex of
indegree 0 and end with a vertex of outdegree 0. Send 1 unit of flow along 
each path from source to sink. The lower bound constraint is satisfied
since every vertex is in at least one path.

Conversely, suppose there exists a feasible flow. There must exist a path
from the source to sink with all edges having flow > 0. Take any edge of
the form v_{in}v_{out} for some vertex v. By the lower bound constraint it
must have a flow of at least one unit. By flow conservation, if a vertex
has an incoming edge with non-zero flow, it must have an outgoing edge with
non-zero flow. So we can start with v_{out} and keep taking an outgoing
edge with non-zero flow. By acyclicity, we can keep doing this till we
reach the sink. Similarly, we can go back from v_{in} to the source.
This gives a source to sink path. We reduce the flow by 1 for edges in this
path. If there are other edges remaining with non-zero flow, we repeat
this process, each time getting a source to sink path. Repeat till the flow
is reduced to 0 in all edges. The paths obtained must cover all edges of
the form v_{in}v_{out}, and hence all vertices in the original graph.
The number of paths is at most k, since each path gives 1 unit of flow 
entering the sink, and there can be at most k units leaving the sink, and
hence at most k units entering the sink.


This will fail if there are cycles in the directed graph, because we may get
a cycle with edges of non-zero flow.