SUO: Graphs and Labelled Graphs
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
Matthew & All,
A more particular point of this example is the concept of isomorphism.
Many mathematical objects are commonly defined as isomorphism classes
of other mathematical objects. The mathematical objects called "graphs"
and "labelled graphs" merely provide us with very concrete and simple,
and very graphic examples of this general theme. The really big idea,
then, is the concept of isomorphism classes, whether our SUO will have
room for this concept and whether it will support a proper grasp of its
standard applications, that is, whether the definitions of the various
concepts that relate to each other by way of isomorphisms will be
represented in the SUO in such a way that it can support their
standard and demanded uses in all of the usual field settings.
Now, don't get me wrong, I am not telling Horatio or anybody that he
should have concepts like "graph" or "labelled graph" in his ontology.
I am simply pointing out what would be obvious to most technical folk,
that you cannot begin to do anything "serious" in the way of generic
faculities for supporting applied or pure research without getting
the definitions of technical concepts like graphs, labeled graphs,
plus their distinctions and their coincidences up to isomorphism,
done right. If you are not going to do it right, then give up
the Ghost and quit trying to pretend that you are using these
words in anything approaching their standard technical sense.
That is just basic "truth in labeling", and a standards body
must insist on it, no matter who may consider that impolite.
That general criterion is the important thing.
So far I do not get the impression that its
importance is the least bit grasped by the
designers of our general info ontologies.
By way of information then, here are the details of this particular example:
Graphs.
Most graph theorists would just start out drawing them like this:
=============================== n = 0 nodes (optional case)
=============================== n = 1 node
o
=============================== n = 2 nodes
o o
-------------------------------
o---o
=============================== n = 3 nodes
o
o o
-------------------------------
o
o---o
-------------------------------
o
/
o---o
-------------------------------
o
/ \
o---o
=============================== n = 4 nodes
...
===============================
These pictures are understood to depict abstract geometric objects,
with points (or nodes) marked as "o" and lines (or edges) marked as
you see them. The number of points or nodes is usually referred to
as the "order" of the graph. So there is 1 graph of order 1, there
are 2 graphs of order 2, there are 4 graphs of order 3, there are
11 graphs of order 4, ..., and so on.
This brings up an interesting point, arising from the enumeration
of structures along the lines of some parameter, like the "order",
or the number of points. One way that discrete mathematicians
from different linguistic sub-communities can pin down what
they are talking about, when the words would otherwise get
in the way, is to say how many of them there are, along
the lines of some well-chosen "invariant" or parameter.
Let us turn to a standard online resource for integer sequences:
http://www.research.att.com/~njas/sequences/Seis.html
http://www.research.att.com/~njas/sequences/index.html
http://www.research.att.com/~njas/sequences/WebCam.html
Here is the enumerating sequence for "Graphs":
Graphs on n points: g_n = 1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, ...
for n = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000088
NB. This starts with g_0 = 1 out of deference to those who count the pointless graph.
Here is the enumerating sequence for "Labeled Graphs":
Labeled Graphs on n points: G_n = 1, 1, 2, 8, 64, 1024, 32768, 2097152, 268435456, ...
for n = 0, 1, 2, 3, 4, 5, 6, 7, 8, ...
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006125
The number G_n of labeled graphs of order n
is given by the formula G_n = 2^(n choose 2),
where (n choose k) is the binomial coefficient
that enumerates "n things taken k at a time",
in this case, (n choose 2) = n(n-1)/2.
Have to break for now ...
Jon Awbrey
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o