SUO: Re: Graphs and Labelled Graphs
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