UVa 10735

Summary

Given a graph $G$ , which contains both directed edges and undirected edges, find a closed path in it, in which each edge is included exactly once.

Explanation

Recall, when Euler tour exists in a directed graph: the underlying undirected graph is connected, and the in-degree of each vertex is equal to the out-degree.

In this problem, some of the graph's edges may be undirected. If we can orient them in such a way, that the in-degree of each vertex will be equal to its out-degree, then the problem will be reduced to finding a tour in a directed graph. Such orientation can be found by solving the following bipartite matching problem.

Construct a bipartite graph $H$ . In one partition put all edges (both directed and undirected) of $G$ , and the other partition contains $G$ 's vertices. For every edge we have to know, which of its two endpoints is the head. So, connect every object (edge of $G$ ) in the first partition with its $G$ 's endpoints in the second partition.

We'll be finding a matching in this graph. If an undirected edge $e=(u,v)$ of $G$ will be matched with $v$ , it means, that in the final directed graph, the edge $e$ will go from vertex $u$ to vertex $v$ .

Each matched $H$ 's edge of $(e,v)$ will contribute to the in-degree of vertex $v$ in the directed graph, and unmatched edge $(e,u)$ contributes to the out-degree of $u$ .

Since we want to make the in-degree and out-degree of each vertex equal, each vertex must have an equal number of matched and unmatched edges in $H$ . Additionally, each directed edge has to be matched with its respective head from $G$ .

After finding a matching in $H$ , satisfying the outlined constraints, we can assign direction to each undirected $G$ 's edge and find Euler tour is the resulting directed graph with any standard algorithm. If a matching doesn't exist, there will be no Euler tour in the original graph.

2
6 8
1 3 U
1 4 U
2 4 U
2 5 D
3 4 D
4 5 U
5 6 D
5 6 U
4 4
1 2 D
1 4 D
2 3 U
3 4 U

Output

1 3 4 2 5 6 5 4 1

No euler circuit exist