A labeled tree with 6 vertices and 5 edges

In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. A forest is a graph in which any two vertices are connected by at most one path. An equivalent definition is that a forest is a disjoint union of trees (hence the name). Trees are widely used in Computer Science data structures such as binary search trees, heaps, tries, etc. Image File history File links Tree_graph. ... A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ... In geometry, a vertex (Latin: whirl, whirlpool; plural vertices) is a corner of a polygon (where two sides meet) or of a polyhedron (where three or more faces and an equal number of edges meet). ... In set theory, a disjoint union (or discriminated union) is a union of a collection of sets whose members are pairwise disjoint. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... A binary tree, a simple type of branching linked data structure. ... A binary search tree of size 9 and depth 3, with root 7 and leaves 1, 4, 7 and 13. ... In [[computer Fibonacci heap Leftist heap Soft heap 2-3 heap Treap See also Heaps at Wikiversity External links Priority Queues by Lee Killough Categories: ‪Data structures‬ | ‪Trees (structure)‬ ... A trie for keys to, tea, ten, i, in, and inn. In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are strings. ...

Definitions

A tree is an undirected simple graph G that satisfies any of the following equivalent conditions: In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i. ...

• G is connected and has no simple cycles.
• G has no simple cycles, and a simple cycle is formed if any edge is added to G.
• G is connected, and it is not connected anymore if any edge is removed from G.
• G is connected and the 3-vertex complete graph K₃ is not a minor of G.
• Any two vertices in G can be connected by a unique simple path.

If G has finitely many vertices, say n of them, then the above statements are also equivalent to any of the following conditions: In mathematics and computer science, graph theory studies the properties of graphs. ... Cycle in graph theory and computer science has several meanings: A closed walk, with repeated vertices allowed. ... This article just presents the basic definitions. ... In the mathematical field of graph theory a complete graph is a simple graph where an edge connects every pair of vertices. ... In graph theory, a graph H is called a minor of the graph G if H is isomorphic to a graph that results from a subgraph of G by zero or more edge contractions. ... In mathematics, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the successor vertex. ...

• G is connected and has n − 1 edges.
• G has no simple cycles and has n − 1 edges.

An undirected simple graph G is called a forest if it has no simple cycles.

A directed tree is a directed graph which would be a tree if the directions on the edges were ignored. Some authors restrict the phrase to the case where the edges are all directed towards a particular vertex, or all directed away from a particular vertex. This article just presents the basic definitions. ...

A tree is called a rooted tree if one vertex has been designated the root, in which case the edges have a natural orientation, towards or away from the root. 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. A tree without any designated root is called a free tree. In computer science, a tree is a widely-used computer data structure that emulates a tree structure with a set of linked nodes. ...

A labeled tree (or plane tree) is a tree in which each vertex is given a unique label. The vertices of a labeled tree on n vertices are typically given the labels 1, 2, …, n.

A regular (or homogeneous) tree is a tree in which every vertex has the same degree. See regular graph. In graph theory, the degree (or valency) of a vertex is the number of edges incident to the vertex. ... In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i. ...

An irreducible (or series-reduced) tree is a tree in which there is no vertex of degree 2.

Example

The example tree shown to the right has 6 vertices and 6 − 1 = 5 edges. The unique simple path connecting the vertices 2 and 6 is 2-4-5-6.

Facts

• Every tree is a bipartite graph. Every tree with only countably many vertices is a planar graph.

• 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.

• Given n labeled vertices, there are nⁿ⁻² different ways to connect them to make a tree. This result is called Cayley's formula.

• The number of trees with n vertices of degree d₁,d₂,...,d_n is

which is a multinomial coefficient.

• No closed formula for the number t(n) of trees with n vertices up to graph isomorphism is known. However, the asymptotic behavior of t(n) is known: there are numbers α ≈ 3 and β ≈ 0.5 such that

In the mathematical field of graph theory, a bipartite graph is a special graph where the set of vertices can be divided into two disjoint sets and such that no edge has both end-points in the same set. ... In mathematics, a countable set is a set with the same cardinality (i. ... // In graph theory, a planar graph is a graph that can be drawn (mathematicians say can be embedded in the plane) so that no edges intersect. ... A spanning tree (red) of a graph (black), superimposed In the mathematical field of graph theory, a spanning tree T of a connected, undirected graph G is a tree composed of all the vertices and some (or perhaps all) of the edges of G. Informally, a spanning tree of G... In mathematics, Cayleys formula is a result in graph theory. ... In mathematics, the multinomial formula is an expression of a power of a sum in terms of powers of the addends. ... Look up Up to on Wiktionary, the free dictionary In mathematics, the phrase up to xxxx indicates that members of an equivalence class are to be regarded as a single entity for some purpose. ... A graph isomorphism is a bijection between the vertices of two graphs and : with the property that any two vertices and from are adjacent if and only if and are adjacent in . ... In mathematics and applications, particularly the analysis of algorithms, asymptotic analysis is a method of classifying limiting behaviour, by concentrating on some trend. ...

Types of trees

See List of graph theory topics: Trees. This is a list of graph theory topics, by Wikipedia page. ...

See also

• Tree structure
• Tree data structure
• Binary tree

A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. ... In computer science, a tree is a widely-used computer data structure that emulates a tree structure with a set of linked nodes. ... In computer science, a binary tree is a tree data structure in which each node has at most two children. ...

References