Tree (graph theory)

From Wikipedia for FEVERv2
Jump to navigation Jump to search

Tree (graph theory)_table_infobox_0

TreesTree (graph theory)_header_cell_0_0_0
VerticesTree (graph theory)_header_cell_0_1_0 vTree (graph theory)_cell_0_1_1
EdgesTree (graph theory)_header_cell_0_2_0 v − 1Tree (graph theory)_cell_0_2_1
Chromatic numberTree (graph theory)_header_cell_0_3_0 2 if v > 1Tree (graph theory)_cell_0_3_1

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. Tree (graph theory)_sentence_0

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. Tree (graph theory)_sentence_1

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. Tree (graph theory)_sentence_2

A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest. Tree (graph theory)_sentence_3

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. Tree (graph theory)_sentence_4

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. Tree (graph theory)_sentence_5

A rooted tree itself has been defined by some authors as a directed graph. Tree (graph theory)_sentence_6

A rooted forest is a disjoint union of rooted trees. Tree (graph theory)_sentence_7

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. Tree (graph theory)_sentence_8

The term "tree" was coined in 1857 by the British mathematician Arthur Cayley. Tree (graph theory)_sentence_9

Definitions Tree (graph theory)_section_0

Tree Tree (graph theory)_section_1

A tree is an undirected graph G that satisfies any of the following equivalent conditions: Tree (graph theory)_sentence_10

Tree (graph theory)_unordered_list_0

  • G is connected and acyclic (contains no cycles).Tree (graph theory)_item_0_0
  • G is acyclic, and a simple cycle is formed if any edge is added to G.Tree (graph theory)_item_0_1
  • G is connected, but would become disconnected if any single edge is removed from G.Tree (graph theory)_item_0_2
  • G is connected and the 3-vertex complete graph K3 is not a minor of G.Tree (graph theory)_item_0_3
  • Any two vertices in G can be connected by a unique simple path.Tree (graph theory)_item_0_4

If G has finitely many vertices, say n of them, then the above statements are also equivalent to any of the following conditions: Tree (graph theory)_sentence_11

Tree (graph theory)_unordered_list_1

  • G is connected and has n − 1 edges.Tree (graph theory)_item_1_5
  • G is connected, and every subgraph of G includes at least one vertex with zero or one incident edges. (That is, G is connected and 1-degenerate.)Tree (graph theory)_item_1_6
  • G has no simple cycles and has n − 1 edges.Tree (graph theory)_item_1_7

As elsewhere in graph theory, the order-zero graph (graph with no vertices) is generally not considered to be a tree: while it is vacuously connected as a graph (any two vertices can be connected by a path), it is not 0-connected (or even (−1)-connected) in algebraic topology, unlike non-empty trees, and violates the "one more vertex than edges" relation. Tree (graph theory)_sentence_12

It may, however, be considered as a forest consisting of zero trees. Tree (graph theory)_sentence_13

An internal vertex (or inner vertex or branch vertex) is a vertex of degree at least 2. Tree (graph theory)_sentence_14

Similarly, an external vertex (or outer vertex, terminal vertex or leaf) is a vertex of degree 1. Tree (graph theory)_sentence_15

An irreducible tree (or series-reduced tree) is a tree in which there is no vertex of degree 2 (enumerated at sequence in the OEIS). Tree (graph theory)_sentence_16

Forest Tree (graph theory)_section_2

A forest is an undirected graph in which any two vertices are connected by at most one path. Tree (graph theory)_sentence_17

Equivalently, a forest is an undirected acyclic graph. Tree (graph theory)_sentence_18

Equivalently, a forest is an undirected graph, all of whose connected components are trees; in other words, the graph consists of a disjoint union of trees. Tree (graph theory)_sentence_19

As special cases, the order-zero graph (a forest consisting of zero trees), a single tree, and an edgeless graph, are examples of forests. Tree (graph theory)_sentence_20

Since for every tree V − E = 1, we can easily count the number of trees that are within a forest by subtracting the difference between total vertices and total edges. Tree (graph theory)_sentence_21

TV − TE = number of trees in a forest. Tree (graph theory)_sentence_22

Polytree Tree (graph theory)_section_3

Main article: Polytree Tree (graph theory)_sentence_23

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. Tree (graph theory)_sentence_24

In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is both connected and acyclic. Tree (graph theory)_sentence_25

Some authors restrict the phrase "directed tree" to the case where the edges are all directed towards a particular vertex, or all directed away from a particular vertex (see arborescence). Tree (graph theory)_sentence_26

Polyforest Tree (graph theory)_section_4

A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest. Tree (graph theory)_sentence_27

In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is acyclic. Tree (graph theory)_sentence_28

Some authors restrict the phrase "directed forest" to the case where the edges of each connected component are all directed towards a particular vertex, or all directed away from a particular vertex (see branching). Tree (graph theory)_sentence_29

Rooted tree Tree (graph theory)_section_5

A rooted tree is a tree in which one vertex has been designated the root. Tree (graph theory)_sentence_30

The edges of a rooted tree can be assigned a natural orientation, either away from or towards the root, in which case the structure becomes a directed rooted tree. Tree (graph theory)_sentence_31

When a directed rooted tree has an orientation away from the root, it is called an arborescence or out-tree; when it has an orientation towards the root, it is called an anti-arborescence or in-tree. Tree (graph theory)_sentence_32

The tree-order is the partial ordering on the vertices of a tree with u < v if and only if the unique path from the root to v passes through u. Tree (graph theory)_sentence_33

A rooted tree which is a subgraph of some graph G is a normal tree if the ends of every edge in G are comparable in this tree-order whenever those ends are vertices of the tree (, p. 15). Tree (graph theory)_sentence_34

Rooted trees, often with additional structure such as ordering of the neighbors at each vertex, are a key data structure in computer science; see tree data structure. Tree (graph theory)_sentence_35

In a context where trees are supposed to have a root, a tree without any designated root is called a free tree. Tree (graph theory)_sentence_36

A labeled tree is a tree in which each vertex is given a unique label. Tree (graph theory)_sentence_37

The vertices of a labeled tree on n vertices are typically given the labels 1, 2, ..., n. A recursive tree is a labeled rooted tree where the vertex labels respect the tree order (i.e., if u < v for two vertices u and v, then the label of u is smaller than the label of v). Tree (graph theory)_sentence_38

In a rooted tree, the parent of a vertex v is the vertex connected to v on the path to the root; every vertex has a unique parent except the root which has no parent. Tree (graph theory)_sentence_39

A child of a vertex v is a vertex of which v is the parent. Tree (graph theory)_sentence_40

An ascendant of a vertex v is any vertex which is either the parent of v or is (recursively) the ascendant of the parent of v. A descendant of a vertex v is any vertex which is either the child of v or is (recursively) the descendant of any of the children of v. A sibling to a vertex v is any other vertex on the tree which has the same parent as v. A leaf is a vertex with no children. Tree (graph theory)_sentence_41

An internal vertex is a vertex that is not a leaf. Tree (graph theory)_sentence_42

The height of a vertex in a rooted tree is the length of the longest downward path to a leaf from that vertex. Tree (graph theory)_sentence_43

The height of the tree is the height of the root. Tree (graph theory)_sentence_44

The depth of a vertex is the length of the path to its root (root path). Tree (graph theory)_sentence_45

This is commonly needed in the manipulation of the various self-balancing trees, AVL trees in particular. Tree (graph theory)_sentence_46

The root has depth zero, leaves have height zero, and a tree with only a single vertex (hence both a root and leaf) has depth and height zero. Tree (graph theory)_sentence_47

Conventionally, an empty tree (a tree with no vertices, if such are allowed) has depth and height −1. Tree (graph theory)_sentence_48

A k-ary tree is a rooted tree in which each vertex has at most k children. Tree (graph theory)_sentence_49

2-ary trees are often called binary trees, while 3-ary trees are sometimes called ternary trees. Tree (graph theory)_sentence_50

Ordered tree Tree (graph theory)_section_6

An ordered tree (or plane tree) is a rooted tree in which an ordering is specified for the children of each vertex. Tree (graph theory)_sentence_51

This is called a "plane tree" because an ordering of the children is equivalent to an embedding of the tree in the plane, with the root at the top and the children of each vertex lower than that vertex. Tree (graph theory)_sentence_52

Given an embedding of a rooted tree in the plane, if one fixes a direction of children, say left to right, then an embedding gives an ordering of the children. Tree (graph theory)_sentence_53

Conversely, given an ordered tree, and conventionally drawing the root at the top, then the child vertices in an ordered tree can be drawn left-to-right, yielding an essentially unique planar embedding. Tree (graph theory)_sentence_54

Properties Tree (graph theory)_section_7

Tree (graph theory)_unordered_list_2

  • Every tree is a bipartite graph. A graph is bipartite if and only if it contains no cycles of odd length. Since a tree contains no cycles at all, it is bipartite.Tree (graph theory)_item_2_8
  • Every tree is a median graph.Tree (graph theory)_item_2_9
  • Every tree with only countably many vertices is a planar graph.Tree (graph theory)_item_2_10
  • Every connected graph G admits a spanning tree, which is a tree that contains every vertex of G and whose edges are edges of G.Tree (graph theory)_item_2_11
  • Every connected graph with only countably many vertices admits a normal spanning tree (, Prop. 8.2.4).Tree (graph theory)_item_2_12
  • There exist connected graphs with uncountably many vertices which do not admit a normal spanning tree (, Prop. 8.5.2).Tree (graph theory)_item_2_13
  • Every finite tree with n vertices, with n > 1, has at least two terminal vertices (leaves). This minimal number of leaves is characteristic of path graphs; the maximal number, n − 1, is attained only by star graphs. The number of leaves is at least the maximal vertex degree.Tree (graph theory)_item_2_14
  • For any three vertices in a tree, the three paths between them have exactly one vertex in common (this vertex is called the median of these three vertices).Tree (graph theory)_item_2_15
  • Every tree has a center consisting of one vertex or two adjacent vertices. The center is the middle vertex or middle two vertices in every longest path. Similarly, every n-vertex tree has a centroid consisting of one vertex or two adjacent vertices. In the first case removal of the vertex splits the tree into subtrees of fewer than n/2 vertices. In the second case, removal of the edge between the two centroidal vertices splits the tree into two subtrees of exactly n/2 vertices.Tree (graph theory)_item_2_16

Enumeration Tree (graph theory)_section_8

Labeled trees Tree (graph theory)_section_9

Cayley's formula states that there are n trees on n labeled vertices. Tree (graph theory)_sentence_55

A classic proof uses Prüfer sequences, which naturally show a stronger result: the number of trees with vertices 1, 2, ..., n of degrees d1, d2, ..., dn respectively, is the multinomial coefficient Tree (graph theory)_sentence_56

A more general problem is to count spanning trees in an undirected graph, which is addressed by the matrix tree theorem. Tree (graph theory)_sentence_57

(Cayley's formula is the special case of spanning trees in a complete graph.) Tree (graph theory)_sentence_58

The similar problem of counting all the subtrees regardless of size is #P-complete in the general case (). Tree (graph theory)_sentence_59

Unlabeled trees Tree (graph theory)_section_10

Counting the number of unlabeled free trees is a harder problem. Tree (graph theory)_sentence_60

No closed formula for the number t(n) of trees with n vertices up to graph isomorphism is known. Tree (graph theory)_sentence_61

The first few values of t(n) are Tree (graph theory)_sentence_62

Tree (graph theory)_description_list_3

  • 1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … (sequence in the OEIS).Tree (graph theory)_item_3_17

proved the asymptotic estimate Tree (graph theory)_sentence_63

with the values C and α known to be approximately 0.534949606... and 2.95576528565... (sequence in the OEIS), respectively. Tree (graph theory)_sentence_64

(Here, f ~ g means that limn→∞ f /g = 1.) Tree (graph theory)_sentence_65

This is a consequence of his asymptotic estimate for the number r(n) of unlabeled rooted trees with n vertices: Tree (graph theory)_sentence_66

with D around 0.43992401257... and the same α as above (cf. Tree (graph theory)_sentence_67

, chap. Tree (graph theory)_sentence_68

2.3.4.4 and , chap. Tree (graph theory)_sentence_69

VII.5, p. 475). Tree (graph theory)_sentence_70

The first few values of r(n) are Tree (graph theory)_sentence_71

Tree (graph theory)_description_list_4

  • 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, … (sequence in the OEIS)Tree (graph theory)_item_4_18

Types of trees Tree (graph theory)_section_11

Tree (graph theory)_unordered_list_5

  • A path graph (or linear graph) consists of n vertices arranged in a line, so that vertices i and i+1 are connected by an edge for i=1,...,n−1.Tree (graph theory)_item_5_19
  • A starlike tree consists of a central vertex called root and several path graphs attached to it. More formally, a tree is starlike if it has exactly one vertex of degree greater than 2.Tree (graph theory)_item_5_20
  • A star tree is a tree which consists of a single internal vertex (and n−1 leaves). In other words, a star tree of order n is a tree of order n with as many leaves as possible.Tree (graph theory)_item_5_21
  • A caterpillar tree is a tree in which all vertices are within distance 1 of a central path subgraph.Tree (graph theory)_item_5_22
  • A lobster tree is a tree in which all vertices are within distance 2 of a central path subgraph.Tree (graph theory)_item_5_23
  • A regular tree of degree d is the infinite tree with d edges at each vertex. These arise as the Cayley graphs of free groups, and in the theory of Tits buildings.Tree (graph theory)_item_5_24

See also Tree (graph theory)_section_12

Tree (graph theory)_unordered_list_6


Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Tree (graph theory).