Re: SUO: Re: Graphs and Labelled Graphs
Jon,
Could you tell us which field of science or engineering
(not mathematics) uses the distinction of "graph" and
"labeled graph"? I have never run into that in my
readings on scientific topics.
Pat
======================================
Jon Awbrey wrote:
> 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
>
--
=============================================
Patrick Cassidy
MICRA, Inc. || (908) 561-3416
735 Belvidere Ave. || (908) 668-5252 (if no answer)
Plainfield, NJ 07062-2054 || (908) 668-5904 (fax)
internet: cassidy@micra.com
=============================================