SUO: Re: Standard Treatments Of Common Knowledge In Descriptive, Empirical, Research Ontologies
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
STOCKIDERO. Note 12
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
| 1.1. The Number of Ways to Label a Graph (cont.)
|
| A 1-1 map !a! from V(G) to V(G_1) that preserves adjacency is
| naturally called an 'isomorphism'. If G_1 = G, then !a! is an
| 'automorphism' of G. The collection of 'all' automorphisms of G,
| denoted !G!(G), constitutes a group called 'the group of G'. Thus
| the elements of !G!(G) are 'permutations' acting on V. For example,
| the random graph G has exactly four automorphisms, so that !G!(G)
| contains the permutations in the usual cyclic representation:
|
| (v_1)(v_2)(v_3)(v_4), [the permutation that moves no points at all],
|
| (v_1)(v_3)(v_2 v_4), [the permutation that transposes v_2 and v_4],
|
| (v_1 v_3)(v_2)(v_4), [the permutation that transposes v_1 and v_3],
|
| (v_1 v_3)(v_2 v_4), [the permutation that transposes both pairs].
|
| Let s(G) = |!G!(G)|, the order of the group of G, denote the number of
| symmetries of G. Then the ansewr to the labeling problem posed above
| is provided in the following theorem.
|
| Theorem. The number of ways of labeling a given graph G of order p is:
|
| L(G) = p! / s(G). (1.1.3)
|
| The proof is most easily obtained using some of the group theoretic
| results of Chapters 2 and 4, see [HPR1]. To illustrate, we simply
| observe that the random graph G has p!/s(G) = 4!/4 = 6 labelings,
| and the six different labeled graphs displayed in Figure 1.1.3
| complete the verification of (1.1.3) for this graph G.
|
| Although this theorem is stated only for graphs, similar versions of
| it hold for any finite structures with specified automorphism groups,
| such as rooted graphs, directed graphs, other relations of various
| types, simplicial complexes, functions, etc.
|
| Harary & Palmer, 'GE', p. 4.
|
| Harary, F. & Palmer, E.M.,
|'Graphical Enumeration',
| Academic Press, New York, NY, 1973.
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o