SUO: Re: Standard Treatments Of Common Knowledge In Descriptive, EmpiricaL, Research Ontologies
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
STOCKIDERO. Note 10
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
| 1.1. The Number of Ways to Label a Graph (cont.)
|
| In a 'labeled graph' of order p, the integers from
| 1 through p are assigned to its points. For example,
| the random graph (of Figure 1.1.1) can be labeled in
| the six different ways indicated in Figure 1.1.3.
|
| +-----------+-----------+-----------+-----------+-----------+-----------+
| | | | | | | |
| | 4 | 4 | 3 | 4 | 3 | 2 |
| | o | o | o | o | o | o |
| | / \ | / \ | / \ | / \ | / \ | / \ |
| | 1 o---o 2 | 1 o---o 3 | 1 o---o 4 | 2 o---o 3 | 2 o---o 4 | 3 o---o 4 |
| | \ / | \ / | \ / | \ / | \ / | \ / |
| | o | o | o | o | o | o |
| | 3 | 2 | 2 | 1 | 1 | 1 |
| | | | | | | |
| +-----------+-----------+-----------+-----------+-----------+-----------+
| Figure 1.1.3. The six different labelings of a graph
|
| Thus two labeled graphs G_1 and G_2 are considered the same and called
| 'isomorphic' if and only if there is a 1-1 map from V(G_1) onto V(G_2)
| which preserves not only adjacency but also the labeling. One can
| easily see then, that 'all' of the different labelings are displayed
| in Figure 1.1.3.
|
| Harary & Palmer, 'GE', p. 2.
|
| Harary, F. & Palmer, E.M.,
|'Graphical Enumeration',
| Academic Press, New York, NY, 1973.
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o