Cycles

What is a cycle

There are actually two definitions of cycles - one applies to problems involving permutations and combinatorics, while the other applies to graphs.

Combinatorics

In combinatorics, a cycle is a way to write a given permutation in a unique way using one-line notation.

(Permutations can also be written using two-line notation, where the first row consists of all items in their natural order, and the second row consists of the items in the order specified by the permutation, but the two-row representation is not unique.)

Graphs

On a graph, an Euler Path is a path through the graph that traverses every edge of the graph exactly once.

An Euler Cycle is slightly more restrictive - it is a path through the graph that visits every edge of the graph exactly once, and it starts and ends on the same node of the graph.

Finding Cycles on a Directed Graph

Conditions

For an Euler Cycle to exist on a graph, the following must be true:

1. All vertices with nonzero degree belong to a single strongly connected component.

2. In degree and out degree of every vertex is same.

If these conditions are met, we can use the Kosaraju algorithm to find the Euler cycle.

Kosaraju Pseudocode for Finding Connected Components

Main article: Graphs/Connected Components

The Kosaraju algorithm is an algorithm for finding connected components on a graph.

Flags