SUO: Re: Graphs and Labelled Graphs
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
I draw some more pictures of graphs, and continue
with the pictures of the first few labeled graphs.
From now on I will ignore the pointless graphs.
Graphs.
+=========+========================================
| |
| o |
| |
+=========+=========+============================== g_1 = 1
| | |
| o o | o---o |
| | |
+=========+=========+=========+=========+========== g_2 = 2
| | | | |
| o | o | o | o |
| | | / | / \ |
| o o | o---o | o---o | o---o |
| | | | |
+=========+=========+=========+=========+========== g_3 = 4
| | | | |
| o | o | o | o |
| | | \ | |
| o o | o o | o o | o o |
| | \ | \ | \ / |
| o | o | o | o |
| | | | |
+---------+---------+---------+---------+
| | | | |
| o | o | o | |
| \ | | | | |
| o o | o | o | o---o | |
| \ / | \|/ | \ / | |
| o | o | o | |
| | | | |
+---------+---------+---------+---------+
| | | | |
| o | o | o | o |
| \ | / \ | / \ | /|\ |
| o---o | o o | o---o | o-|-o |
| \ / | \ / | \ / | \|/ |
| o | o | o | o |
| | | | |
+=========+=========+=========+=========+========== g_4 = 11
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.
Labeled Graphs.
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.
Here are the pictures of the first few Labeled Graphs:
+=========+========================================
| |
| 1 |
| o |
| |
+=========+=========+============================== G_1 = 1
| | |
| 1 2 | 1 2 |
| o o | o---o |
| | |
+=========+=========+=========+=========+========== G_2 = 2
| | | | |
| 1 | 1 | 1 | 1 |
| o | o | o | o |
| | / | \ | |
| o o | o o | o o | o---o |
| 2 3 | 2 3 | 2 3 | 2 3 |
| | | | |
+---------+---------+---------+---------+
| | | | |
| 1 | 1 | 1 | 1 |
| o | o | o | o |
| / \ | \ | / | / \ |
| o---o | o---o | o---o | o o |
| 2 3 | 2 3 | 2 3 | 2 3 |
| | | | |
+=========+=========+=========+=========+========== G_3 = 8
Jon Awbrey
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o