10735 - Euler Circuit
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.
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
1 3 4 2 5 6 5 4 1 No euler circuit exist