Re: SUO: Re: Graphs and Labelled Graphs
On Sun, Jun 29, 2003 at 01:08:26AM -0400, Patrick Cassidy wrote:
> I will repeat my original request with a slight
> modification so as not to be misunderstood:
>
> > Jon,
> > Could you tell us which field of *experimental*
> ? science or engineering (not mathematics) uses the
> > distinction of "graph" and "labeled graph",
> > and provide a specific example of how such a
> > distinction is used? I have never run into that
> > in my readings on scientific topics.
> ...
> Please note:
> (1) I excluded mathematics from the fields
> I am curious about that might use the distinction.
> Theory of computation is for this purpose a branch of
> mathematics. Actual computational practice -- say,
> C++ or JAVA standard classes in some commercial
> compiler that make such a distinction -- would be
> a legitimate example of an engineering use.
Hi Patrick. I guess I don't see quite the same clear divide between
the theory of computation and actual computational practice that you
seem to be presupposing here. Often the data we actually process
computationally takes the form of a labeled (or colored, or whatever)
graph. When you think about how to search or otherwise process such a
structure, however, you will typically abstract away from the labels and
consider the structure of the graph itself -- a binary tree, say -- in
order to identify the most efficient search algorithm for graphs with
that structure (an algorithm typically identified in a book like Knuth's
AoCP volume on sorting and searching).
By my admittedly weak lights, that sort of seems like an "engineering
use" of the distinction between labeled (colored, etc) graphs and graphs
per se to me.
Chris Menzel