Cycle graph

from Wikipedia, the free encyclopedia

In group theory , a branch of abstract algebra , the cycle graph represents the various cycles of a group and is particularly useful for visualizing the structure of small, finite groups , but does not play an important role in group theory.

Cycle

A cycle of a group is the set of powers of a given group element , where the n-th power of an element is defined as the n-fold product of itself. In a finite group, a positive power of must result in the neutral element , the smallest power for which this occurs is the number of different elements of the cycle and is called its order . In a cycle graph, the cycles are shown as polygons, the corners of the graph stand for the group elements and edges indicate that the corners of the polygon connected by them belong to the same cycle.

Cycles can overlap or, with the exception of the neutral element, have no element in common. The cycle graph shows each cycle of interest as a polygon.

If generates a cycle of order 6 (or in short: has order 6), then is . The set of powers of is the cycle , but does not represent new information because it is contained in the cycle generated by . creates the same cycle as .

Therefore only so-called primitive cycles need to be considered, that is, those that are not a subset of another. Each of these cycles is generated by one or more primitive elements . The cycle graph is created by taking the group elements as corners , dragging an edge to a primitive element for each primitive cycle and then connecting them with , with , ... until you get back to the neutral element.

If , that is, it has order 2, i.e. is an involution , then this element is connected via two edges . If this is not to be emphasized, only one edge is typically drawn.

Examples

Cycle graph of the dihedral group

As an example of a cycle graph we consider the dihedral group . The link table is on the left, on the right is the cycle graph with the neutral element :

O e b a a 2 a 3 from a 2 b a 3 b
e e b a a 2 a 3 from a 2 b a 3 b
b b e a 3 b a 2 b from a 3 a 2 a
a a from a 2 a 3 e a 2 b a 3 b b
a 2 a 2 a 2 b a 3 e a a 3 b b from
a 3 a 3 a 3 b e a a 2 b from a 2 b
from from a b a 3 b a 2 b e a 3 a 2
a 2 b a 2 b a 2 from b a 3 b a e a 3
a 3 b a 3 b a 3 a 2 b from b a 2 a e

Look at the cycle . The successive powers of can be taken from the link table . The reverse order is also possible, that is, it applies and finally . This applies to all cycles of each group, a cycle can be run through in any direction.

Cycle graph of the quaternion group

Cycles with a non- prime number of elements always have sub-cycles that are not shown in the cycle graph. One might be tempted to draw an edge between and in the cycle graph of group D 4 , but this does not happen because the cycle of order 2 generated by is part of the larger cycle of order 4 generated by .

As already stated above, two-element cycles are usually only represented by an edge.

If two cycles have a different corner in common, there may be ambiguities about the course of the cycle. To do this, consider the quaternion group , the cycle graph of which is shown opposite. The square of the element in the middle row is −1, where 1 stands for the neutral element in . Here, as shown in the drawing, you can mark cycles with different colors.

The inverse of an element can be found in the cycle graph by finding the element in the cycle to which this element belongs that is just as far away from the neutral element when the cycle is reversed.

history

Cycle graphs were studied in the early 1950s by number theorist Daniel Shanks as a means of studying prime residual class groups. Shanks first published this idea in 1962 in the first edition of his book Solved and Unsolved Problems in Number Theory . In this book, Shanks examines which groups have isomorphic cycle graphs and which cycle graphs are planar . In the second edition published in 1978, Shanks writes about his investigation of ideal class groups and the development of the baby step-giant step method :

The cycle graphs have proved to be useful when working with finite Abelian groups; and I have used them frequently in finding my way around an intricate structure, in obtaining a wanted multiplicative relation, or in isolating some wanted subgroup.
German: The cycle graphs have proven useful when working with Abelian groups; and I have often used them to find my way around intricate structures, to maintain sought-after multiplicative relationships, or to isolate some sought-after subgroups.

In Nathan Carter's introductory textbook Visual Group Theory , published in 2009, Zykel groups were used as an educational tool.

Graph properties of certain group families

Certain types of groups have typical cycle graphs:

The cycle graphs of the cyclic groups of the order are -sided regular polygons , each corner stands for a group element.

GroupDiagramMiniC1.svg GroupDiagramMiniC2.svg GroupDiagramMiniC3.svg GroupDiagramMiniC4.svg GroupDiagramMiniC5.svg GroupDiagramMiniC6.svg GroupDiagramMiniC7.svg GroupDiagramMiniC8.svg
Z 1 Z 2 = D 1 Z 3 Z 4 Z 5 Z 6 = Z 3 × Z 2 Z 7 Z 8
GroupDiagramMiniC9.svg GroupDiagramMiniC10.svg GroupDiagramMiniC11.svg GroupDiagramMiniC12.svg GroupDiagramMiniC13.svg GroupDiagramMiniC14.svg GroupDiagramMiniC15.svg GroupDiagramMiniC16.svg
No. 9 Z 10 = Z 5 × Z 2 No. 11 Z 12 = Z 4 × Z 3 Z 13 Z 14 = Z 7 × Z 2 Z 15 = Z 5 × Z 3 Z 16
GroupDiagramMiniC17.svg GroupDiagramMiniC18.svg GroupDiagramMiniC19.svg GroupDiagramMiniC20.svg GroupDiagramMiniC21.svg GroupDiagramMiniC22.svg GroupDiagramMiniC23.svg GroupDiagramMiniC24.svg
Z 17 Z 18 = Z 9 × Z 2 Z 19 Z 20 = Z 5 × Z 4 Z 21 = Z 7 × Z 3 Z 22 = Z 11 × Z 2 Z 23 Z 24 = Z 8 × Z 3

Direct products from :

GroupDiagramMiniC2.svg GroupDiagramMiniD4.svg GroupDiagramMiniC2x3.svg GroupDiagramMiniC2x4.svg
Z 2 Z 2 2 = D 2 Z 2 3 = D 2 × D 1 Z 2 4 = D 2 2

If a prime number , then the cycle graphs of the groups consist of cycles of the order that have the neutral element in common:

GroupDiagramMiniD4.svg GroupDiagramMiniC2x3.svg GroupDiagramMiniC2x4.svg GroupDiagramMiniC3x2.svg
Z 2 2 = D 2 Z 2 3 = D 2 × D 1 Z 2 4 = D 2 2 Z 3 2

The cycle graphs of the dihedral groups of the order have an n -element cycle and n 2-element cycle :

GroupDiagramMiniC2.svg GroupDiagramMiniD4.svg GroupDiagramMiniD6.svg GroupDiagramMiniD8.svg GroupDiagramMiniD10.svg GroupDiagramMiniD12.svg GroupDiagramMiniD14.svg GroupDiagramMiniD16.svg GroupDiagramMiniD18.png GroupDiagramMiniD20.png
D 1 = Z 2 D 2 = Z 2 2 D 3 D 4 D 5 D 6 = D 3 × Z 2 D 7 D 8 D 9 D 10 = D 5 × Z 2

The dicyclic groups of the order have the following cycle graphs:

GroupDiagramMiniQ8.svg GroupDiagramMiniX12.svg GroupDiagramMiniQ16.svg GroupDiagramMiniQ20.png GroupDiagramMiniQ24.png
Dic 2 = Q 8 Dic 3 = Q 12 Dic 4 = Q 16 Dic 5 = Q 20 Dic 6 = Q 24

Cycles graphs of other direct products:

GroupDiagramMiniC2C4.svg GroupDiagramMiniC2x2C4.svg GroupDiagramMiniC2C6.svg GroupDiagramMiniC2C8.svg GroupDiagramMiniC4x2.svg
Z 4 × Z 2 Z 4 × Z 2 2 Z 6 × Z 2 Z 8 × Z 2 Z 4 2

Every group of the order is isomorphic to a subgroup of the symmetric group , its cycle graph can therefore be found in the cycle graph of , see the following examples for the .

GroupDiagramMiniA4xC2.png
A 4 × Z 2
Symmetric group 3;  cycle graph.svg
S 3 = D 3
Symmetric group 4;  cycle graph.svg
S 4
Dihedral group of order 8;  cycle graph;  subgroup of S4 (elements 1,6 ...). svg
One of the three D 4 in S 4
identical toGroupDiagramMiniD8.svg

See also

literature

  • S. Skiena: Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica 1990, §4.2.3 Cycles, Stars, and Wheels , pages 144-147
  • Daniel Shanks: Solved and Unsolved Problems in Number Theory , Chelsea Publishing Company (1978), ISBN 0-8284-0297-3
  • S. Pemmaraju, S. Skiena: Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematics Cambridge, England: Cambridge University Press, 2003, §6.2.4 Cycles, Stars, and Wheels pages 248-249

Web links

Individual evidence

  1. ^ Sarah Perkins: Commuting Involution Graphs for A˜n, Section 2.2, page 3, first figure . School of Economics, Mathematics and Statistics. 2000. Retrieved January 31, 2016.
  2. Shanks 1978, p. 246
  3. Shanks 1978, p. Xii
  4. Shanks 1978, pp. 83-98, 206-208
  5. ^ Nathan Carter (2009): Visual Group Theory , Mathematical Association of America, Classroom Resource Materials ISBN 978-0-88385-757-1