HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Decomposing a closed walk in a directed graph into cycles

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#53493, answer score: 2

Revisions (0)

No revisions yet.