#15060: The empty graph once again
-------------------------------------------------+-------------------------
Reporter: darij | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-5.12
Component: combinatorics | Resolution:
Keywords: graphs, border cases, bitset, | Merged in:
memleak | Reviewers:
Authors: | Work issues:
Report Upstream: N/A | Commit:
Branch: | Stopgaps:
Dependencies: |
-------------------------------------------------+-------------------------
Comment (by kcrisman):
> > As a non graph-theorist... I was wondering whether the empty graph
should be a connected graph with zero connected components. Though one of
the definitions on that math.SX question suggested one connected component
is the definition of connected.
>
> You will also see at a lot of places that a graph is connected if and
only if any two vertices are linked by a path.
>
Well, yes, that was the definition that I (and you) had in mind. Just
because I'm not a graph theorist doesn't mean I'm not fairly conversant
with graph theory ;-)
> Because there are moments when you want them to be connected, other when
you don't want them to be. I just had a look at Diestel's book (page 2,
http://www.math.uni-
hamburg.de/home/diestel/books/graph.theory/preview/Ch1.pdf) :
>
> "For the empty graph (\emptyset,\emptyset) we simply write \emptyset. A
graph of order 0 or 1 is called trivial. Sometimes, e.g. to start an
induction, trivial graphs can be useful; at other times they form silly
counterexamples and become a nuisance. To avoid cluttering the text with
non-triviality conditions, we shall mostly trat the trivial graphs, and
particularly the empty graph \emptyset with generous disregard."
That sounds like a good approach, but one that doesn't work for computers
:(
> > since the empty graph does not have any connected components (which is
not quite the same as a connected graph) - or perhaps I err in thinking a
component has to be non-empty.
>
> Well, if you add nonempty to the definition of connected components
decomposition then everything is fine.
Right, that's what I meant. Otherwise the notion of a connected component
seems less useful. But I suppose it's all a matter of one's favorite
definition, as we all seem to agree. Is the theorem what defines
connectedness, or is the definition what leads to the theorem? That's
sort of what's going on here.
Well, have fun resolving this! I think that leaving it as it is, with a
brief comment we can point to when people complain, is easiest. If it
really is a bug at #14529, that is different, but it probably just means
that patch needs some slight adjustment. After all, changing this could
also lead to unintended consequences in other code that assumed implicitly
that this worked. I suppose it's also an API change in some ways.
--
Ticket URL: <http://trac.sagemath.org/ticket/15060#comment:11>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
