NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/comp/theory/2496

Text File | 1992-11-20 | 3.6 KB | 66 lines

Newsgroups: comp.theory
Path: sparky!uunet!stanford.edu!CSD-NewsHost.Stanford.EDU!Sunburn.Stanford.EDU!pratt
From: [e-mail] (Vaughan R. Pratt)
Subject: Re: Illustraion of graphs.
Message-ID: <[e-mail]>
Sender: [e-mail]
Organization: Computer Science Department,  Stanford University.
References: <[e-mail]> <[e-mail]>
Date: Sat, 21 Nov 1992 01:19:12 GMT
Lines: 54

In article <[e-mail]> [e-mail] (Mark A Biggar) writes:
>In article <[e-mail]> [e-mail] (Hung-Hsien Hubert Chang) writes:
>>Hi! I would like to know if there is any picture books enumerating
>>graphs. (say from number n=4 to n=8)  (showing only the graphs
>>that are not isomorphic.)
>
>This would be rather difficult as ther are an infintie number of graphs with
>just 4 vertices.  You have to put a limit on the number of edges as well
>to make the set finite.  You also need to specify you definition of isomorphic.
>(i.e. are the vertices labeled, the edges, are the graphs directed, etc.)

Presumably he's asking about undirected graphs up to isomorphism or
he'd have been more specific.  These are enumerated by sequence 479 in
Neil Sloane's very handy "A Handbook of Integer Sequences."  I found it
by spending a couple of minutes systematically enumerating all such up
to 4 vertices to yield the sequence 1,2,4,11,....  The book lists 4
sequences starting in this way, the last of which is named "Graphs or
reflexive symmetric relations".  (We can assume "up to isomorphism"
because Sloane follows the usual custom of adding the adjective
"labelled" when they are not so.)  Sloane cites three references for
this sequence including Harary's "Graph Theory".  (I have "computed"
many such citations from Sloane's book over the last 19 years.)

The sequence continues 34,156,1044,12346,...  At say 6x8=48 graphs per
page this would be a 270-page book.  Sloane's book at 206 pages meets a
similar albeit broader need.  The big difference is that such a book of
graphs would be more like a table of logarithms or primes, whereas
Sloane's 2372 sequences were painstaking culled from the literature by
hand, complete with references---no computer program imaginable today
could dream up as useful a set of two thousand sequences, even without
the references!

There is the problem of looking up a graph in such a book.  By
classifying graphs according to vertex degree and alphabetizing
accordingly one would break the back of this problem, and a couple more
heuristics should take care of the remaining large chunks, leaving only
very small blocks of graphs still unseparated by those heuristics.

It is less clear what use such a book, or for that matter a program
generating pages of the book on the screen on demand, could possibly
serve.  As a picture book it would be very misleading, since the
appearance of a graph in general gives very little insight into other
views of the same graph, even if the vertices are normalized to be the
vertices of a regular polygon.  One might specify for each graph its
automorphism group, and flipping through a compilation of these might
be a change of pace from Newsweek.  But it could also serve as simple a
purpose as reducing graph anxiety for the graph-challenged, probably its
largest market niche.

What *would* be very nice would be a single program implementing such a
"picture book" for *every* picturable sequence in Sloane's book.  This
would be a massive project requiring many people over many years.
--
Vaughan Pratt              A fallacy is worth a thousand steps.