patternMinor
Decomposing a closed walk in a directed graph into cycles
Viewed 0 times
decomposinggraphintocloseddirectedwalkcycles
Problem
Let's say I have a closed walk $W$ in a directed graph $D$. Represent $W$ as a list of arcs $(a_1, a_2, \dots, a_k)$. Since it's a closed walk, there may be repeated edges, but the source vertex of $a_1$ must equal the target vertex of $a_k$. My claim is that the multiset of arcs $W'=\{a_1, a_2, \dots, a_k\}$ can be partitioned into sets (not multisets) $W'_1, W'_2, \dots, W'_m$ such that the arcs in each $W'_i$ form a simple cycle.
There is a simple algorithm to output these cycles. Travel along $W$ until you visit a vertex $v$ for the second time. Output the arcs between the two occurrences of $v$ (which form a cycle). Repeat this process until the walk is empty.
I'm using this "walk decomposition" lemma in a paper, and it seems like something that should be easy to find in the literature, but I can't find it anywhere. Can anyone point me in the right direction?
There is a simple algorithm to output these cycles. Travel along $W$ until you visit a vertex $v$ for the second time. Output the arcs between the two occurrences of $v$ (which form a cycle). Repeat this process until the walk is empty.
I'm using this "walk decomposition" lemma in a paper, and it seems like something that should be easy to find in the literature, but I can't find it anywhere. Can anyone point me in the right direction?
Solution
The problem stated in the question is also presented in the exercise of the book.
If you are writing a research paper, due to the is simplicity of the solution, you may even skip the explanation.
If you are writing a research paper, due to the is simplicity of the solution, you may even skip the explanation.
Context
StackExchange Computer Science Q#53493, answer score: 2
Revisions (0)
No revisions yet.