#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 ncohen):
Yooooooooooooo !!
> 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.
> So... what do the various standard texts say about this? Maybe they are
silent on the question?
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."
After which he defines connectedness by : "A non-empty graph G is called
connected if [..]".
> Perhaps it is better to *document* that we follow a certain convention
(probably the more obvious one, in this case),
We also disagree on the most obvious one I guess `:-P`
We had another battle like that about whether the complete graph and the
empty graph are strongly regular. I was decided that they weren't because
there is a theorem saying that strongly regular graphs have exactly 3
eigenvalues `:-PPPP`
(needless to say I don't agree with that `:-P`)
> and then in documentation for anything about connected components point
it out again. If we really have to.
Come on.. Nobody reads these things before finding a bug in the code,
everybody assumes that his own definition of connectivity is right. To me
any definition is a mistake.
> I don't quite see why there are infinitely many decompositions,
He claims that you can add as many empty graphs to a "connected subgraphs
decomposition" as soon as you assume the empty graph to be connected.
> 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.
> Naturally, this is all just deciding on a definition. But it's not
quite the same as 1 not being a prime number (and note Conway's argument
that 1 and -1 ''do'' count, but as prime ''powers'', not "primes",
whatever those are - perhaps something analogous could work with sets or
graphs, who knows).
It's a word play. It's theology `:-P`
The truth is that we could take any definition and explain at length why
it's the best way to see it. And usually it is to make our favorite
theorems work for the empty graph too `:-P`
We should just raise an exception when an empty graph is created :
{{{ThisThingDoesNotExistException : it's safer to deny the existence of
the empty graph. It really creates a lot of problems if you don't}}} `:-P`
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/15060#comment:10>
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.
