# directed tree

usmerjeno drevo

Trees | |
---|---|

A labeled tree with 6 vertices and 5 edges. | |

Vertices | v |

Edges | v − 1 |

Chromatic number | 2 if v > 1 |

Table of graphs and parameters |

In graph theory, a **tree** is an undirected graph in which any two vertices are connected by *exactly one* path, or equivalently a connected acyclic undirected graph. A **forest** is an undirected graph in which any two vertices are connected by *at most one* path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.

A **polytree** (or **directed tree** or **oriented tree** or **singly connected network**) is a directed acyclic graph (DAG) whose underlying undirected graph is a tree. A **polyforest** (or **directed forest** or **oriented forest**) is a directed acyclic graph whose underlying undirected graph is a forest.

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**. A rooted tree may be directed, called a **directed rooted tree**, either making all its edges point away from the root—in which case it is called an **arborescence** or **out-tree**—or making all its edges point towards the root—in which case it is called an **anti-arborescence** or **in-tree**. A rooted tree itself has been defined by some authors as a directed graph. A **rooted forest** is a disjoint union of rooted trees. A rooted forest may be directed, called a **directed rooted forest**, either making all its edges point away from the root in each rooted tree—in which case it is called a **branching** or **out-forest**—or making all its edges point towards the root in each rooted tree—in which case it is called an **anti-branching** or **in-forest**.

The term "tree" was coined in 1857 by the British mathematician Arthur Cayley.