patternMinor
Is a "tree" with $0$ vertices, $0$ edges or $1$ vertex, $0$ edges considered a valid tree?
Viewed 0 times
edgesvertexwithconsideredvalidverticestree
Problem
For the following $2$ cases:
(1) $V = \emptyset, E = \emptyset $ (i.e. nothing at all)
(2) $V = \{v_0\}, E = \emptyset $ (i.e. only 1 root node $v_0$)
Are they considered a valid tree? It seems like different literature have different definitions.
I recall that I have read a data structures and algorithms book that defines "A tree is a set of nodes that either: is empty or has a designated node, called the root ...". According to this definition, (1) and (2) are both valid trees. I don't have the book on hand, but I am sure if you search the quoted sentence above in Google, you can get lots of results, as quite a lot of lecture notes follow this definition.
However, another definition of trees often met is defined in terms of graphs:
A tree is "a connected graph without a cycle".
Using this definition, my question is transformed to another question: "Is an empty graph a connected graph?" But the answer to the latter question is debatable according to here:
Is the empty graph connected?
My question is, which one is the more accepted definition?
(1) $V = \emptyset, E = \emptyset $ (i.e. nothing at all)
(2) $V = \{v_0\}, E = \emptyset $ (i.e. only 1 root node $v_0$)
Are they considered a valid tree? It seems like different literature have different definitions.
I recall that I have read a data structures and algorithms book that defines "A tree is a set of nodes that either: is empty or has a designated node, called the root ...". According to this definition, (1) and (2) are both valid trees. I don't have the book on hand, but I am sure if you search the quoted sentence above in Google, you can get lots of results, as quite a lot of lecture notes follow this definition.
However, another definition of trees often met is defined in terms of graphs:
A tree is "a connected graph without a cycle".
Using this definition, my question is transformed to another question: "Is an empty graph a connected graph?" But the answer to the latter question is debatable according to here:
Is the empty graph connected?
My question is, which one is the more accepted definition?
Solution
Here are a few properties of trees which can be relevant:
-
A tree on $n$ vertices has $n-1$ edges. Works for (2) but not for (1).
-
A graph has no cycles iff it is a disjoint union of trees. Works for both (1) and (2), unless you require the decomposition into trees to be unique, in which case it works for (2) but not for (1).
-
A tree is either a single vertex or a bunch of disjoint trees connected to a common vertex. Works for (2) but not for (1).
These examples suggest that the commonsense definition of tree should include (2) but not (1). Indeed, oftentimes it seems that the graph on no vertices is a pointless concept; see the classical discussion of Harary and Read, who present arguments for both sides of the issue.
Practically speaking, you should probably assume that (1) is not a legal graph, unless it makes sense in your application, and then you should explicitly mention the fact.
-
A tree on $n$ vertices has $n-1$ edges. Works for (2) but not for (1).
-
A graph has no cycles iff it is a disjoint union of trees. Works for both (1) and (2), unless you require the decomposition into trees to be unique, in which case it works for (2) but not for (1).
-
A tree is either a single vertex or a bunch of disjoint trees connected to a common vertex. Works for (2) but not for (1).
These examples suggest that the commonsense definition of tree should include (2) but not (1). Indeed, oftentimes it seems that the graph on no vertices is a pointless concept; see the classical discussion of Harary and Read, who present arguments for both sides of the issue.
Practically speaking, you should probably assume that (1) is not a legal graph, unless it makes sense in your application, and then you should explicitly mention the fact.
Context
StackExchange Computer Science Q#40329, answer score: 5
Revisions (0)
No revisions yet.