Utente:Grasso Luigi/sandbox4/Grafo ciclo

In group theory, a subfield of abstract algebra, a group cycle graph illustrates the various cycles of a group and is particularly useful in visualizing the structure of small finite groups.

A cycle is the set of powers of a given group element a, where aⁿ, the n-th power of an element a is defined as the product of a multiplied by itself n times. The element a is said to generate the cycle. In a finite group, some non-zero power of a must be the group identity, e; the lowest such power is the order of the cycle, the number of distinct elements in it. In a cycle graph, the cycle is represented as a polygon, with the vertices representing the group elements, and the connecting lines indicating that all elements in that polygon are members of the same cycle.

Cicli

Cycles can overlap, or they can have no element in common but the identity. The cycle graph displays each interesting cycle as a polygon.

If a generates a cycle of order 6 (or, more shortly, has order 6), then a⁶ = e. Then the set of powers of a², {a², a⁴, e} is a cycle, but this is really no new information. Similarly, a⁵ generates the same cycle as a itself.

So, only the primitive cycles need be considered, namely those that are not subsets of another cycle. Each of these is generated by some primitive element, a. Take one point for each element of the original group. For each primitive element, connect e to a, a to a², ..., aⁿ⁻¹ to aⁿ, etc., until e is reached. The result is the cycle graph.

When a² = e, a has order 2 (is an involution), and is connected to e by two edges. Except when the intent is to emphasize the two edges of the cycle, it is typically drawn as a single line between the two elements.

Proprietà

Dih4 kaleidoscope with red mirror and 4-fold rotational generators

Grafo ciclo per Dih4.

Come esempio di grafo del ciclo di un gruppo, consideriamo il gruppo diedrale Dih₄. La tabella di composizione per questo gruppo è mostrata a sinistra, e il grafo del ciclo è mostrato a destra con e = x⁴ che specifica l'elemento di identità.

o	e	x	x2	x3	y	x2y	xy	x3y
e	e	x	x2	x3	y	x2y	xy	x3y
x	x	x2	x3	x4	xy	x3y	x2y	y
x2	x2	x3	x4	x	x2y	y	x3y	xy
x3	x3	x4	x	x2	x3y	xy	y	x2y
y	y	a3b	e	a	a2	b	ab	a2b
x2y	x2y	a	b	a3b	a2b	e	a3	a2
xy	xy	a2	ab	b	a3b	a	e	a3
x3y	x3y	a3	a2b	ab	b	a2	a	e

Notice the cycle {e, a, a², a³} in the multiplication table, with a⁴ = e. The inverse a⁻¹ = a³ is also a generator of this cycle: (a³)² = a², (a³)³ = a, and (a³)⁴ = e. Similarly, any cycle in any group has at least two generators, and may be traversed in either direction. More generally, the number of generators of a cycle with n elements is given by the Euler φ function of n, and any of these generators may be written as the first node in the cycle (next to the identity e); or more commonly the nodes are left unmarked. Two distinct cycles cannot intersect in a generator.

Cycle graph of the quaternion group Q₈.

Cycles that contain a non-prime number of elements have cyclic subgroups that are not shown in the graph. For the group Dih₄ above, we could draw a line between a² and e since (a²)² = e, but since a² is part of a larger cycle, this is not an edge of the cycle graph.

There can be ambiguity when two cycles share a non-identity element. For example, the 8-element quaternion group has cycle graph shown at right. Each of the elements in the middle row when multiplied by itself gives −1 (where 1 is the identity element). In this case we may use different colors to keep track of the cycles, although symmetry considerations will work as well.

As noted earlier, the two edges of a 2-element cycle are typically represented as a single line.

The inverse of an element is the node symmetric to it in its cycle, with respect to the reflection which fixes the identity.

Storia

Cycle graphs were investigated by the number theorist Daniel Shanks in the early 1950s as a tool to study multiplicative groups of residue classes.Template:Sfn Shanks first published the idea in the 1962 first edition of his book Solved and Unsolved Problems in Number Theory.Template:Sfn In the book, Shanks investigates which groups have isomorphic cycle graphs and when a cycle graph is planar.Template:Sfn In the 1978 second edition, Shanks reflects on his research on class groups and the development of the baby-step giant-step method:Template:Sfn Template:Quotation

Cycle graphs are used as a pedagogical tool in Nathan Carter's 2009 introductory textbook Visual Group Theory.

Grafi cicli di gruppi finiti

Certain group types give typical graphs:

Cyclic groups Z_n, order n, is a single cycle graphed simply as an n-sided polygon with the elements at the vertices:

Z1	Z2 = Dih1	Z3	Z4	Z5	Z6 = Z3×Z2	Z7	Z8
Z9	Z10 = Z5×Z2	Z11	Z12 = Z4×Z3	Z13	Z14 = Z7×Z2	Z15 = Z5×Z3	Z16
Z17	Z18 = Z9×Z2	Z19	Z20 = Z5×Z4	Z21 = Z7×Z3	Z22 = Z11×Z2	Z23	Z24 = Z8×Z3

Z2	Z22 = Dih2	Z23 = Dih2×Dih1	Z24 = Dih22

When n is a prime number, groups of the form (Z_n)^m will have (n^m − 1)/(n − 1) n-element cycles sharing the identity element:

Z22 = Dih2	Z23 = Dih2×Dih1	Z24 = Dih22	Z32

Dihedral groups Dih_n, order 2n consists of an n-element cycle and n 2-element cycles:

Dih1 = Z2	Dih2 = Z22	Dih3 = S3	Dih4	Dih5	Dih6 = Dih3×Z2	Dih7	Dih8	Dih9	Dih10 = Dih5×Z2

Dicyclic groups, Dic_n = Q_4n, order 4n:

Dic2 = Q8	Dic3 = Q12	Dic4 = Q16	Dic5 = Q20	Dic6 = Q24

Other direct products:

Z4×Z2	Z4×Z22	Z6×Z2	Z8×Z2	Z42

Symmetric groups – The symmetric group S_n contains, for any group of order n, a subgroup isomorphic to that group. Thus the cycle graph of every group of order n will be found in the cycle graph of S_n.
See example: Subgroups of S₄

Esempio: Sottogruppi del gruppo ottaedrico achirale

The full octahedral group is the direct product $S_{4}\times Z_{2}$ of the symmetric group S₄ and the cyclic group Z₂.
Its order is 48, and it has subgroups of every order that divides 48.

In the examples below nodes that are related to each other are placed next to each other,
so these are not the simplest possible cycle graphs for these groups (like those on the right).

S4 × Z2 (order 48)	A4 × Z2 (order 24)	Dih4 × Z2 (order 16)	S3 × Z2 = Dih6 (order 12)
S4 (order 24)	A4 (order 12)	Dih4 (order 8)	S3 = Dih3 (order 6)

Like all graphs a cycle graph can be represented in different ways to emphasize different properties. The two representations of the cycle graph of S₄ are an example of that.

Bibliografia

• Skiena, S. (1990). Cycles, Stars, and Wheels. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica (pp. 144-147).
• Daniel Shanks, Solved and Unsolved Problems in Number Theory, Chelsea Publishing Company, 1978.
• Pemmaraju, S., & Skiena, S. (2003). Cycles, Stars, and Wheels. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica (pp. 248-249). Cambridge University Press.

Voci correlate

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su Grasso Luigi/sandbox4/Grafo ciclo
• List of small groups
• Cayley graph

Collegamenti esterni

• (EN) Eric W. Weisstein, Grasso Luigi/sandbox4/Grafo ciclo, in MathWorld, Wolfram Research.