SUO: Re: Graphs and Labelled Graphs
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
See also the advanced search page at the Online EIS:
http://www.research.att.com/~njas/sequences/index2.html
Use the boolean search on "Knuth AND Graph" --
the "Knuth" has already been entered for you! --
and you will get a full page of references.
Jon Awbrey
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
Jon Awbrey wrote:
>
> o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
>
> Patrick Cassidy wrote:
> >
> > Yes, sorting does make use of things like trees.
> > But I looked through the index of that Knuth volume
> > and can't find a reference to the term "graph" there.
> > Of course, there are things in the volume that
> > a mathematician would call a "graph" but Knuth
> > doesn't call them by that term -- not that
> > I can find.
>
> Try Volume 1, 'Fundamental Algorithms'.
>
> Jon
>
> > I'm not trying to be a contentious smart-ass here.
> > I have a fairly specific purpose in mind -- where in my
> > ontology should I put labeled graphs and unlabeled graphs,
> > and the distinction between them?
> > I can imagine certain places they would likely show up --
> > in a "MathematicalThing" class, for example. Under that
> > class I would have a subclass of
> > "MathematicalModelsOfPhysicalPhenomena" which would include
> > concepts like those used in statistical mechanics, and
> > quantum mechanics. Some subclasses of differential equations
> > would show up here, too.
> > When such mathematical models are used for certain
> > purposes, I would have a relation. For example, I would
> > have a class of "Acceleration" as a subclass of "PhysicalProcess".
> > Then there would be a relation (this is abbreviated, there
> > would be more axioms):
> >
> > (hasMentalRepresentation Acceleration NewtonsLaw1)
> >
> > where NewtonsLaw1 is the Mental concept corresponding to
> > the equation "F=ma" (this would not exclude other representations).
> > There may well be some physical phenomena represented by
> > unlabeled graphs, and others represented by labeled graphs.
> > That would not, in an ontology structured this way, require
> > that the distinction itself appear anywhere other than in
> > the mathematical section. There should be no argument
> > that it would be useful there.
> >
> > The question I am genuinely curious about is whether this
> > distinction of labeled and unlabeled graph has some structural
> > expression (as a class or relation) somewhere in the ontology
> > content other than in the section on mathematics. Since I know
> > absolutely nothing about graph theory I am relying on those
> > who do to suggest places where it might need to be more
> > directly represented other than by some relation to
> > mathematical structures that make the distinction. This
> > question came up because of an assertion on the list that
> > the distinction is somehow central to an understanding of
> > scientific concepts. I'm an open-minded person and I would
> > be fascinated to discover just where, other than in a few
> > mathematical models (as in statistical mechanics), the
> > distinction shows up.
> > If a computational process is abstracted to create a
> > mathematical model that is useful for suggesting efficient
> > computational methods, that to me is still a mathematical
> > thing. Yes, I do consider mathematical models of things
> > that are manipulated in a computational process to be distinct
> > from the programs that use those models, and even from the
> > computational process itself. This may not be a legitimate
> > distinction, and it may be worth exploring (in a different
> > thread).
> > The IFF structure as used for relating ontologies is for
> > me distinct from the content of the ontologies themselves.
> > I would imagine that labeled and unlabeled graphs are important
> > there, too. IFF theory itself would, in my ontology, fall
> > within the mathematics section.
> > All of business uses arithmetic, for example. But I'm
> > skeptical that the rules of arithmetic need to be represented
> > more than once, specifically in the mathematical section
> > of the ontology.
> > "MathematicalModelsOfPhysicalPhenomena" is a very
> > important class, no question. But it is only one of
> > a rather large number of classes in an upper ontology.
> >
> > Pat
> >
> > =========================================
> >
> > Chris Menzel wrote:
> > > 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
> > --
> > =============================================
> > 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
> > =============================================
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o