Difference between revisions of "Tree (graph theory)"
Scrabbler94 (talk | contribs) (more complete description of a tree) |
Scrabbler94 (talk | contribs) |
||
| Line 1: | Line 1: | ||
| − | A '''tree''' is an undirected graph which is both connected and acyclic. Equivalently, a tree is a graph <math>G=(V,E)</math> such that for any two vertices <math>u, v \in V</math> with <math>u \neq v</math>, there is exactly one path connecting <math>u</math> and <math>v</math> in <math>G</math>. Every tree on <math>|V|=n</math> vertices has exactly <math>n-1</math> edges. | + | A '''tree''' is an undirected [[Graph (graph theory)|graph]] which is both connected and acyclic. Equivalently, a tree is a graph <math>G=(V,E)</math> such that for any two vertices <math>u, v \in V</math> with <math>u \neq v</math>, there is exactly one path connecting <math>u</math> and <math>v</math> in <math>G</math>. Every tree on <math>|V|=n</math> vertices has exactly <math>n-1</math> edges. |
Revision as of 15:51, 2 November 2020
A tree is an undirected graph which is both connected and acyclic. Equivalently, a tree is a graph 
such that for any two vertices 
with 
, there is exactly one path connecting 
and 
in 
. Every tree on 
vertices has exactly 
edges.
