Cycle decomposition

From Wikipedia, the free encyclopedia

A cycle decomposition in mathematics may refer to one of two related concepts.

• In graph theory, a cycle decomposition is a partitioning of the vertices of a graph into subsets, such that the vertices in each subset lie on a cycle.

• In combinatorics, a cycle decomposition is a way of writing a permutation as a number of disjoint cycles.

[edit] Definition

Let i₁, i₂, ..., i_k be k distinct integers in S = { 1, 2,..., n }. The symbol ( i₁ i₂ ... i_k ) will represent the permutation σ Є S_n, where σ( i₁ ) = i₂ , σ( i₂ ) = i₃ , ... , σ( i_j ) = i_j+1 for j < k, σ( i_k ) = i₁, and σ(s) = s for any s Є S if s is different from i₁ , i₂ ,... , i_k. <Herstein, I.N. (1999). Abstract Algebra, 3^rd edition. John Wiley & Sons, Inc. NJ./>