SUO: Re: Graphs, Labels, Isomorphisms
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
GLI. Note 15
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
While I have my graph coloring palette out, I might as well show you
an example of a graph coloring problem, one that can be regarded as
a constraint satisfaction problem in propositional calculus, and so
expressed in the form of a zeroth order declarative program, to be
solved through the agency of a zeroth order interpreter or modeler
like my old Theme One program, while memory serves, =< 640 Kb.
I borrow this Example from Herbert S. Wilf, 'Algorithms and Complexity',
Prentice-Hall, Englewood Cliffs, NJ, 1986, page 196. Curiously enough,
we meet up with another avatar of our old friend, Harary and Palmer's
favorite example of a random graph.
One is given three colors, say, orange, silver, indigo,
and a graph on four nodes that has the following shape:
1
o
/ \
/ \
4 o-----o 2
\ /
\ /
o
3
Figure 1. G, a Graph to Color
The problem to be solved is to color the nodes of the graph
in such a way that no pair of nodes adjacent in the graph,
that is, linked by an edge, get the same color.
The objective situation that is to be achieved can be represented
in a so-called "declarative" fashion, in effect, by employing the
cactus language as a very simple sort of declarative programming
language, and depicting the prospective solutions to the problem
as the models of a proposition, or a "zeroth order theory" (ZOT).
To do this, begin by declaring the following set of
twelve boolean variables or "zeroth order features":
!A! = {1_orange, 1_silver, 1_indigo,
2_orange, 2_silver, 2_indigo,
3_orange, 3_silver, 3_indigo,
4_orange, 4_silver, 4_indigo}
The interpretation to keep in mind will be such that
the feature name of the form "<node i>_<color j>"
says that the node i is assigned the color j.
A proposition that defines the problem is given in Table 2.
Table 2. Proper Colorings of G, Described by a Proposition
o----------------------------------------------------------------------o
| |
| (( 1_orange ),( 1_silver ),( 1_indigo )) |
| (( 2_orange ),( 2_silver ),( 2_indigo )) |
| (( 3_orange ),( 3_silver ),( 3_indigo )) |
| (( 4_orange ),( 4_silver ),( 4_indigo )) |
| |
| ( 1_orange 2_orange )( 1_silver 2_silver )( 1_indigo 2_indigo ) |
| ( 1_orange 4_orange )( 1_silver 4_silver )( 1_indigo 4_indigo ) |
| ( 2_orange 3_orange )( 2_silver 3_silver )( 2_indigo 3_indigo ) |
| ( 2_orange 4_orange )( 2_silver 4_silver )( 2_indigo 4_indigo ) |
| ( 3_orange 4_orange )( 3_silver 4_silver )( 3_indigo 4_indigo ) |
| |
o----------------------------------------------------------------------o
The first set of clauses says that every node is assigned just one color.
The second set of clauses says that no adjacent nodes get the same color.
Every satisfying interpretation of the proposition corresponds
to what graffitists call a "proper coloring" of the graph G.
The Model function of the Theme One program, when set to work
on the above proposition, or zeroth order theory, will output
in outline form a specification of all six proper colorings
of the graph G, as shown in Table 3.
Table 3. Proper Colorings of G
o-----------------------------o
| |
| 1_orange |
| 2_silver |
| 3_orange |
| 4_indigo |
| 2_indigo |
| 3_orange |
| 4_silver |
| 1_silver |
| 2_orange |
| 3_silver |
| 4_indigo |
| 2_indigo |
| 3_silver |
| 4_orange |
| 1_indigo |
| 2_orange |
| 3_indigo |
| 4_silver |
| 2_silver |
| 3_indigo |
| 4_orange |
| |
o-----------------------------o
| Reference
|
| Wilf, Herbert S.,
|'Algorithms and Complexity',
| Prentice-Hall, Englewood Cliffs, NJ, 1986.
|
| Nota Bene. In some printings of this book
| there is a mismatch between the Figure and
| the Example as it is described in the text.
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o