《离散数学100课件》由会员分享，可在线阅读，更多相关《离散数学100课件（68页珍藏版）》请在金锄头文库上搜索。
1、Trees can be used to model procedures carried out using a sequence of decisions. Constructing these models can help determine the computational complexity of algorithms based on a sequence of decisions, such a sorting algorithms.,Tree,An Example of a Tree,The Bernoulli Family of Mathematicians,A tre
2、e is a connected undirected graph with no simple circuits. A tree cannot have a simple circuit, so a tree cannot contain multiple edges or loops. Any tree must be a simple graph.,Trees,Example: Trees,G1 and G2 are trees. Both are connected graph with no simple circuits.,Example: Not Trees,G3 is not
3、a tree G4 is not a tree.,Theorem: Let G be a graph with n nodes and e edges 1.G is a tree (connected, acyclic) 2. G is acyclic and e = n - 1 3.G is connected and e = n - 1 4.G is acyclic and if any two non-adjacent points are joined by an edge, the resulting graph has exactly one cycle 5. G is conne
4、cted, but if any edge is deleted, it will be non-connected 6. Every two nodes of G are joined by a unique path Theorem: there exists at least two nodes of degree one for every tree.,Forest,A graph containing no simple circuits that are not necessarily connected. A Forest : a graph with the property
5、that each of their connected components is a tree.,Example: Forest,One graph with three connected components,In many applications of trees, a particular vertex of a tree is designated as the root. Once we specify a root, we can assign a direction to each edge as follows: direct each edge away from t
6、he root. Thus, a tree together with its root produces a directed graph called a rooted tree.,A Rooted Tree,We can change an unrooted tree into a rooted tree by choosing any vertex as the root. Different choices of the root produce different trees.,Rooted Trees,The rooted trees formed by designating
7、a to be the root and c to be the root, respectively, in the tree T.,Example: Rooted Trees,Suppose that T is a rooted tree. If v is a vertex in T other than the root. The parent of v is the unique vertex u such that there is a directed edge from u to v.,The Terminology for Trees,When u is the parent
8、of v, v is called a child of u. Vertices with the same parent are called siblings.,The Terminology for Trees,The ancestors of a vertex other than the root are the vertices in the path from the root to this vertex, excluding the vertex itself and including the root. The descendants of a vertex v are
9、those that have v as an ancestor.,The Terminology for Trees,A vertex of a tree is called a leaf if it has no children. Vertices that have children are called internal vertices.,The Terminology for Trees,If a is a vertex in a tree, the subtree with a as its root is the subgraph of the tree consisting
10、 of a and its descendants and all edges incident to these descendant.,The Terminology for Trees,T is a rooted tree with root a. The parent of vertex c is b. The children of g are h, i, and j.,Example: Using Terminology,The siblings of h are i and j. The ancestors of e are c, b, and a. The descendant
11、 of b are c, d, and e.,Example: Using Terminology,The internal vertices are a, b, c, g, h, and j. The leaves are d, e, f, i, k, l, and m.,Example: Using Terminology,The subtree rooted at g is,Example: Using Terminology,A rooted tree is called an m-ary tree if every internal vertex has no more than m
12、 children. The tree is called a full m-ary tree if every internal vertex has exactly m children. An m-ary tree with m = 2 is called a binary tree.,m-ary Tree,T1 is a full binary tree. Each of its internal vertices has two children,Example of m-ary tree,T2 is a full 3-ary tree. Each of its internal v
13、ertices has three children,Example of m-ary tree,T4 is not a full m-ary tree for any m. Some of its internal vertices has 2 children and others have 3.,Example of m-ary tree,An ordered rooted tree is a rooted tree where the children of each internal vertex are ordered. In an ordered binary tree, if
14、an internal vertex has two children, the first child is called the left child and the second child is called the right child. The tree rooted at the left child of a vertex is called the left subtree of this vertex, and the tree rooted at the right child of a vertex is called the right subtree of the
15、 vertex.,Ordered Rooted Tree,Example,The left child of d is f and the right child is g. The left and right subtrees of c are,A rooted m-ary tree of height is balanced if all leaves are at levels h or h 1.,T1 is balanced. All its leaves are at levels 3 and 4.,T2 is not balanced. It has leaves at leve
16、ls 2, 3, and 4.,T3 is balanced. All its leaves are at level 3.,Properties of Trees,A full m-ary tree with i internal vertices contains n = mi+1 vertices.,Theorem 4: A full m-ary tree with 1) n vertices has i = (n-1)/m internal vertices and l = (m-1)n+1/m leaves 2) i internal vertices has n = mi + 1 vertices and l = (m-1)i+1 leaves 3) l leaves has n = (ml-1)/(m-1) vertices and i = (l-1)/(m-1) internal vertices,Tree Property 4,Proof for 1) l: Number of leaves k: Number of internal vertice
