# Cycles

### From charlesreid1

## Contents

## 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.

## Related

Graphs:

Permutations:

## Flags

Combinatorics
Ordinary generating functions
Enumerating Permutations: String Permutations Generating Permutations: Cool
Longest Increasing Subsequence Cards (poker hands with a deck of 52 playing cards)
· Template:CombinatoricsFlag · e |

The Art of Computer ProgrammingArt of Computer Programming
Part of the 2017 CS Study Plan.
Mathematical Foundations: AOCP/Infinite Series AOCP/Harmonic Numbers Puzzles/Exercises:
AOCP/Combinatorics
AOCP/Combinatorial Algorithms AOCP/Five Letter Words AOCP/Generating Permutations and Tuples
· Template:AOCPFlag · e |