Reducing the Eulerian cycle problem in a mixed graph to a maximum flow problem

396 Views Asked by At

I'm completely stuck on this one. The obvious resemblance between the two that I see is that every vertex needs to have the same amounts going in and out, in the Eulerian cycle problem the amount is just the number of edges, and in the maximum flow problem it's the flow. But I can't figure out what I'm trying to maximize in that case, or what the flow is.

To clarify: a mixed graph is a graph with some directed edges and some undirected.