File:Tree_graph.svg · Wikimedia Commons · See Wikimedia Commons
Key facts
- Vertices
- v
- Edges
- v − 1
- Chromatic number
- 2 if v > 1
via Wikipedia infobox
Wikidata facts
- Subclass of
- block graph
- Named after
- tree
- Image
- Tree graph.svg
- Has use
- tree structure
Show 8 more facts
- Commons category
- Tree diagrams
- topic's main category
- Category:Trees (graph theory)
- different from
- Baum
- derivative work
- tree structure
- does not have part
- cycle
- has characteristic
- chromatic number
- studied by
- graph theory
- Commons gallery
- Tree diagram
Sources (2)
via Wikidata · CC0
~15 min read
Encyclopedic overview
In graph theory, a tree is an undirected graph in which every pair of distinct vertices is 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 directed tree, oriented tree, polytree, 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.
Excerpted from Wikipedia’s “tree” article, available under the CC BY-SA 4.0 licence.