[Inquiry] Re: Theme One Program

[Jon Awbrey]

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

TOP.  Expository Note 2

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

2.  Painted And Rooted Cacti And Conifers

Figure 1 depicts a typical example of a "painted and rooted cactus" (PARCA).

    o
a   |       d
o---o       o
 \ /  b c   |
  o----o----o b e
   \       /
    \     /
     \   /
      \ /
       @ a c e

Figure 1.  Painted And Rooted Cactus

The graph itself is a mathematical object and does not inhabit
the page before our eyes, nor must it be confused with any one
picture of it, any more than you would wish someone to confuse
you with a picture of yourself, but it's a fair enough picture,
once you understand the conventions of representation involved.

Let V(G) be the set of nodes in a graph G and let L be a set of identifiers.
We very often find ourselves in situations where we have to consider many
different ways of associating the nodes of G with the identifiers in L.
Various manners of associating nodes with identifiers have been given
conventional names by different schools of graph theorists.  I will
give here one way of describing a few of the most common patterns
of association.

A graph is "painted" if there is a relation between the
set of its nodes and a set of identifiers, in which case
the relation is called a "painting" and the identifiers
are called "paints".

A graph is "colored" if there is a function from the set
of its nodes to a set of identifiers, in which case the
function is called a "coloring" and the identifiers are
called "colors".

A graph is "labeled" if there is a one-to-one mapping
between the set of its nodes and a set of identifiers,
in which case the mapping is called a "labeling" and
the identifiers are called "labels".

A graph is "rooted" if it has a uniquely distinguished node,
in which case the distinguished node is referred to as the
"root" of the graph.  The root node of the above graph is
represented by the "at" sign or the "amphora" symbol "@".

The graph in Figure 1 has eight nodes plus the five paints in
the set {a, b, c, d, e}.  The painting of nodes is depicted by
drawing the paints of each node next to the node that they paint.
Observe that some nodes may be painted with an empty set of paints.

The structure of a "painted and rooted cactus" (PARC)
can be encoded in the form of character string that is
called a "painted and rooted cactus expression" (PARCE).
To facilitate the rest of this discussion let's agree that
the terms "cactus" and "cactus expression" will be used to
mean the painted and rooted varieties.  A cactus expression
is formed on the alphabet that consists of the relevant set
of identifiers, the "paints", plus three punctuation marks,
the left parenthesis, the comma, and the right parenthesis.

Jon Awbrey

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o