How do you find a sub-digraph in a digraph such that the in degree and out degree of each vertex is 1. My professor told in the class that an algorithm can be build for it using bipartite matching but I have not able to do so. I am just looking for hints on how to proceed because I am kind of stuck on where to start.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Any simple cycle satisfies the conditions, so you can use any standard algorithm for finding cycles in a directed graph.
For example: decompose into strongly connected components. Pick one component. Start following an arbitrary walk through vertices within that component. As soon as you hit a vertex the second time, you can construct a cycle.
-
$\begingroup$ Yeah that makes sense. I was stuck on finding the solution through a bipartite matching that I didn’t think of anything else. Just out of curiosity, how will bipartite matching come into the picture? $\endgroup$– BajruCommented Apr 17, 2020 at 10:51