Difference between revisions of "Tree (graph theory)"
Karl Jones (Talk | contribs) (→See also) |
Karl Jones (Talk | contribs) |
||
| Line 1: | Line 1: | ||
In [[mathematics]], and more specifically in [[graph theory]], a '''tree''' is an [[undirected graph]] in which any two [[vertices]] are connected by exactly one [[path]]. | In [[mathematics]], and more specifically in [[graph theory]], a '''tree''' is an [[undirected graph]] in which any two [[vertices]] are connected by exactly one [[path]]. | ||
| − | |||
| − | |||
== Description == | == Description == | ||
Revision as of 06:52, 4 February 2016
In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path.
Description
In other words, any connected graph without simple cycles is a tree.
A forest is a disjoint union of trees.
Rooted Trees
The various kinds of data structures referred to as trees in computer science have underlying graphs that are trees in graph theory, although such data structures are generally rooted trees, thus in fact being directed graphs, and may also have additional ordering of branches.
Rooted trees in their directed graph form may be called directed rooted trees.
Other terms for this include arborescence, out-arborescence, out-tree, and even branching.
History
The term "tree" was coined in 1857 by the British mathematician Arthur Cayley.
See also
External links
- Tree (graph theory) @ Wikipedia
