UVa 10735

From Algorithmist
Jump to navigation Jump to search

10735 - Euler Circuit[edit]


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


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 . In one partition put all edges (both directed and undirected) of , and the other partition contains 's vertices. For every edge we have to know, which of its two endpoints is the head. So, connect every object (edge of ) in the first partition with its 's endpoints in the second partition.

We'll be finding a matching in this graph. If an undirected edge of will be matched with , it means, that in the final directed graph, the edge will go from vertex to vertex .

Each matched 's edge of will contribute to the in-degree of vertex in the directed graph, and unmatched edge contributes to the out-degree of .

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 . Additionally, each directed edge has to be matched with its respective head from .

After finding a matching in , satisfying the outlined constraints, we can assign direction to each undirected '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.


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


1 3 4 2 5 6 5 4 1

No euler circuit exist