SUO: Re: Standard Treatments Of Common Knowledge In Descriptive, Empirical, Research Ontologies
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
STOCKIDERO. Note 11
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
| 1.1. The Number of Ways to Label a Graph (cont.)
|
| Two natural questions now arise. The first asks: How many labeled graphs
| of order p are there? The second is: How many graphs of order p are there?
| The first question is so easy that we deal with it next. The second is much
| more difficult and will be treated in Chapter 4.
|
| We shall answer the easier question by generalizing the problem ever so slightly
| to that of finding the number of labeled graphs with a given number of points
| 'and' lines. Let G_p (x) be that polynomial which has as the coefficient of
| x^k, the number of labeled graphs of order p which have exactly k lines.
| Such a polynomial is ordinarily called the "ordinary generating function"
| for labeled graphs with a given number of points and lines. If V is a set
| of p points, there are (p choose 2) distinct unordered pairs of these points.
| In any labeled graph with point set V, each pair of points are either adjacent
| or not adjacent. The number of labeled graphs with precisely k lines is therefore
| ((p choose 2) choose k).
|
| Theorem. The ordinary generating function G_p (x)
| for labeled graphs of order p is given by:
|
| G_p (x) = Sum_(k = 0 to m) (m choose k) x^k
|
| = (1 + x)^m
|
| where m = (p choose 2). (1.1.1)
|
| Since G_p (x) = (1 + x)^m and the number G_p
| of labeled graphs of order p is G_p (1), we
| see that:
|
| G_p = 2^(p choose 2). (1.1.2)
|
| For p = 3, this formula is vividly illustrated in Figure 1.1.4. Thus there are
| eight labeled graphs of order 3 but only four graphs of order 3; and there are
| 64 labeled graphs of order 4, but only 11 graphs of order 4. The question then
| arises: In how many ways can a given graph be labeled? To provide an answer,
| we must consider the symmetries or automorphisms of a graph.
|
| +---------+---------+---------+---------+
| | | | | |
| | 1 | 1 | 1 | 1 |
| | o | o | o | o |
| | | | / | \ |
| | o o | o---o | o o | o o |
| | 2 3 | 2 3 | 2 3 | 2 3 |
| | | | | |
| +---------+---------+---------+---------+
| | | | | |
| | 1 | 1 | 1 | 1 |
| | o | o | o | o |
| | / \ | / | \ | / \ |
| | o o | o---o | o---o | o---o |
| | 2 3 | 2 3 | 2 3 | 2 3 |
| | | | | |
| +---------+---------+---------+---------+
| Figure 1.1.4. The 8 labeled graphs of order 3
|
| Harary & Palmer, 'GE', pp. 3-4.
|
| Harary, F. & Palmer, E.M.,
|'Graphical Enumeration',
| Academic Press, New York, NY, 1973.
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o