Cycles: Difference between revisions

Latest revision as of 22:28, 26 April 2019

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

@@ Line 1: / Line 1: @@
-A cycle is an important concept to [[Permutations]] and [[Combinatorics]].
+==What is a cycle==
-A cycle is a way of writing a unique permutation in a unique way. (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.)
+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:
+. All vertices with nonzero degree belong to a single strongly connected component.
+. 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|Graphs/Connected Components}}
+The Kosaraju algorithm is an algorithm for finding connected components on a graph.
 ==Related==
+Graphs:
+* [[Graphs/Cycles]]
+* [[Graphs/Euler Tour]]
+Permutations:
 * [[Inversions]]
@@ Line 14: / Line 51: @@
 {{CombinatoricsFlag}}
+{{AOCPFlag}}