Information about Tree (graph Theory)

Tree
A labeled tree with 6 vertices and 5 edges
Vertices	v
Edges	v - 1
Chromatic number	2

In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. Alternatively, any connected graph with no cycles is a tree. A forest is a disjoint union of trees. Trees are widely used in computer science data structures such as binary search trees, heaps, tries, etc.

Definitions

A tree is an undirected simple graph G that satisfies any of the following equivalent conditions:

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

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

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. 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. A 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 . 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 structureIn a context where trees are supposed to have a root, a tree without any designated root is called a free tree.

A polytree has at most one undirected path between any two vertices. In other words, a polytree is a directed acyclic graph (DAG) for which there are no undirected cycles either.

A labeled 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.

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

An ordered tree is a tree for which an ordering is specified for the children of each node.

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. Every connected graph even admits a normal spanning tree .
• Every non-null tree has at least one leaf, or vertex of degree 1 (If it has a vertex, it has a leaf).

Enumeration

Given n labeled vertices, there are nⁿ⁻² different ways to connect them to make a tree. This result is called Cayley's formula. It can be proved by first showing that the number of trees with n vertices of degree d₁,d₂,...,d_n is the multinomial coefficient

Counting the number of unlabeled trees is a harder problem. No closed formula for the number t(n) of trees with n vertices up to graph isomorphism is known. proved that

with C = 0.53495… and α = 2.95576… (here, f ∼ g means that lim f/g = 1).

Types of trees

See List of graph theory topics: Trees.

See also

• Tree structure
• Tree data structure
• Binary tree
• Pseudoforest

References

• id="CITEREFDiestel2005">Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4, <[1].
  • id="CITEREFOtter1948">Otter, Richard (1948), "The Number of Trees", Annals of Mathematics, Second Series 49 (3): 583–599, DOI 10.2307/1969046.
    vertex (plural vertices) or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered
    ..... Click the link for more information.
    graph theory is the study of graphs; mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges
    ..... Click the link for more information.
    vertex (plural vertices) or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered
    ..... Click the link for more information.
    In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. The first vertex is called the start vertex and the last vertex is called the end vertex.
    ..... Click the link for more information.
    connectedness is used to refer to various properties meaning, in some sense, "all one piece". When a mathematical object has such a property, we say it is connected; otherwise it is disconnected.
    ..... Click the link for more information.
    Cycle in graph theory and computer science has several meanings:

    • A closed walk, with repeated vertices allowed. See path (graph theory). (This usage is common in computer science. In graph theory it is more often called a closed walk.

    
    ..... Click the link for more information.
    In set theory, a disjoint union (or discriminated union) is a modified union operation which indexes the elements according to which set they originated in.
    
    Formally, let be a family of sets indexed by I.
    ..... Click the link for more information.
    Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems.
    ..... Click the link for more information.
    data structure is a way of storing data in a computer so that it can be used efficiently. Often a carefully chosen data structure will allow the most efficient algorithm to be used. The choice of the data structure often begins from the choice of an abstract data type.
    ..... Click the link for more information.
    binary search tree (BST) is a binary tree data structure which has the following properties:

    • Each node has a value.
    • A total order is defined on these values.
    • The left subtree of a node contains only values less than the node's value.

    
    ..... Click the link for more information.
    Heap may refer to:
    
    In computer science:

    • heap (data structure), a tree-like data structure
    • The heap (or free store) is the area of memory used for dynamic memory allocation

    In mathematics:

    • a heap (mathematics) is a generalization of a group.

    
    ..... Click the link for more information.
    trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree shows what key
    ..... Click the link for more information.
    See also Equivalence
    
    The Equivalent was a sum negotiated at £398,000 paid to Scotland by the English Government under the terms of the Acts of Union 1707. Proposals for it first emerged in the course of abortive Union negotiations in 1702/03.
    ..... Click the link for more information.
    In mathematics and computer science, connectivity is one of the basic concepts of graph theory. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its robustness as a network.
    ..... Click the link for more information.
    In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. The first vertex is called the start vertex and the last vertex is called the end vertex.
    ..... Click the link for more information.
    In the mathematical field of graph theory, a complete graph is a simple graph where an edge connects every pair of distinct vertices. The complete graph on vertices has vertices and edges, and is denoted by . It is a regular graph of degree .
    ..... Click the link for more information.
    minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. Edge contraction is the process of removing an edge and combining its two endpoints into a single node (since the edge is first
    ..... Click the link for more information.
    In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. The first vertex is called the start vertex and the last vertex is called the end vertex.
    ..... Click the link for more information.
    partially ordered set (or poset) formalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that describes, for certain pairs of elements in the set, the requirement that one
    ..... Click the link for more information.
    tree is a widely-used data structure that emulates a tree structure with a set of linked nodes.

    Nodes

    A node may contain a value or a condition or represents a separate data structure or a tree of its own.
    ..... Click the link for more information.
    In graph theory, a polytree is a graph with at most one undirected path between any two vertices. In other words, a polytree is a directed acyclic graph (DAG) for which there are no undirected cycles either.
    ..... Click the link for more information.
    directed acyclic graph, also called a dag or DAG, is a directed graph# with no directed cycles#; that is, for any vertex v, there is no nonempty directed path that starts and ends on
    ..... Click the link for more information.
    bipartite graph is a graph whose vertices can be divided into two disjoint sets and such that every edge connects a vertex in and one in ; that is, there is no edge between two vertices in the same set.
    ..... Click the link for more information.
    countable set is a set with the same cardinality (i.e., number of elements) as some subset of the set of natural numbers. The term was originated by Georg Cantor; it stems from the fact that the natural numbers are often called counting numbers.
    ..... Click the link for more information.
    In graph theory, a planar graph is a graph that can be drawn so that no edges intersect (or that can be embedded) in the plane. A nonplanar graph cannot be drawn in the plane without edge intersections.
    ..... Click the link for more information.
    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 is a selection of edges of G that form a tree spanning
    ..... Click the link for more information.
    Cayley's formula is a result in graph theory named after Arthur Cayley. It states that if n is an integer bigger than 1, the number of trees on n labeled vertices is
    
    

    
    
    It is a particular case of Kirchhoff's theorem.
    ..... Click the link for more information.
    In mathematics, the multinomial theorem is an expression of a power of a sum in terms of powers of the addends. For any positive integer m and any nonnegative integer n, the multinomial formula is
    
    

    
    ..... Click the link for more information.
    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. "xxxx" describes a property or process which transforms an element into one from the same equivalence class, i.e.
    ..... Click the link for more information.
    In graph theory, a graph isomorphism is a bijection (a one-to-one and onto mapping) between the vertices of two graphs G and H

    with the property that any two vertices u and v from G are adjacent if and only if
    ..... Click the link for more information.