離散數(shù)學(xué)課件----trees

1、Trees,Lecture 8Discrete Mathematical Structures,Rooted Tree,Let A be a set, and let T be a relation on A. T is a rooted tree if there is a vertex v0 in A with the property that there exists a unique path in T from v0 to

2、 every other vertex in A, but no path from v0 to v0.,,,,Properties of Rooted Tree,Let (T, v0) be a rooted tree. Then(a) There are no cycles in T.(b) v0 is the only root of T.(c) Each vertex other than the root has in-

3、degree one, and the root has in-degree 0,,v0,,,v,p,,c,More than one path from v0 to v.,(a),,,v0,v0’,,,A cycle from v0 to v0,(b),,,,,,v0,,vk,w1,,?,More path to w1,,,,?,(c),Drawing a Rooted Tree by Levels,,,,,,,,,,,,,,,,,

4、,,,,,,,,,,,Root,Inner node,Branching node,Leaf,Level 0,Level 1,Level 2,Level 3,,,,,Height=3,,Rooted Tree and Family Relations,It is easy to describe the family relations，and on the other hand, terms about family relation

5、s are used in rooted trees.,,,John,,,,,,,,,,,,,,,,,,,,,,,,John's child,John's parent,,,,,,,,,John's ancestors,John's descendants,,,John’s siblings,,Some Terms about Rooted Tree,Ordered tree: the ordering

6、is assumed on vertices in each level;n-tree: every vertex has at most n offspring;Complete n-tree: every vertes, other than leaves, has exactly n offspringBinary tree: 2-tree,Subtree of a Rooted Tree,If (T,v0) is a ro

7、oted tree and v?T. Let T(v) be the set of v and all its descendants, then T(v) and all edges with their two ends in T(v) is a tree, with v as its root.(It is called a subtree of (T,v0) )Proof:There is a path from v to

8、 any other vertex in T(v) since they are all the descendants of v;There cannot be more than one path from v to any other vertex w in T(v) , otherwise, in (T,v0), there are more than one path from v0 to w, both through v

9、There cannot be any cycle in T(v), since any cycle in T(v) is also in (T,v0),Subtrees of Binary Tree,In a ordered binary tree, a subtree is a left subtree or a right subtree. Even if a vertex has only one

10、offspring, its subtree can be identified as left or right by its location in the digraph.,Labeled Tree: an Example,Using rooted tree to represent a arithmetic expressions: branching vertices corresponding o

11、peratorsleaves corresponding operands,Example: (a*(b+c)+d*(e*f))/(g+(h-i)*j),,Positional Trees,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2,2,2,2,3,3,3,3,3,1,1,1,,,,,,,,,,,,,,,,L,L,L,L,L,L,L,L,,,R,R,R,R,R,R,R,R,,,,,,,,,,,,,,,,,Po

12、sitional Binary Tree,Ordered Binary Tree,Any ordered tree can be converted into a ordered binary tree.,,Computer Representation,,,,,,,,,,,,,,,,,,,(3-(2?x))+((x-2)-(3+x)) as a doubly linked list,1,2,4,5,6,7,9,12,8,3,11,1

13、0,14,13,3 arrays:LEFT DATA RIGHT,,,,,,,,Tree Searching,Tree recursive algorithm to search all vertices:Inorder: left, root, righth, d, i, b, e, a, f, c, gPreorder: root, left, righta, b, d, h, i, e, c, f, gPost

14、 order: left, right, rooth, i, d, e, b, f, g, c, a,,,,,,,,,,,,,,,,,,g,f,e,i,h,c,a,b,d,,Reverse Polish Notation,Example: (a*(b+c)+d*(e*f))/(g+(h-i)*j)Searching in postorder: abc+*def**+ghi-j*+/It is called reverse

15、 Polish notation,,No parenthesis are needed!,Undirected Tree,An undirected tree is the symmetric closure of a tree.An undirected tree is represented by its graph, which has a single line without arrows connecting ver

16、tices a and b.The set {a,b}, where (a,b) and (b,a) are in T, is called an undirected edge, and a and b are called adjacent vertices.,,Undirected Tree: Examples,Different undirected trees with six vertices:,,,,,,,,,,,,,,

17、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,Symmetric closure,Path and Cycle in a Tree,Let p: v1,v2,...,vn be path in a symmetric relation R, then p is simple if no two edges of p correspond to the

18、same undirected edge. In above, if v1 is equal to vn , then p is a simple cycle.A symmetric relation R is acyclic if it contains no simple cycles.A symmetric relation R is connected if there is a path in R from any ve

19、rtex to any other vertex.,Properties of an Undirected Tree,Let R be a symmetric relation on a set A. R is an undirected tree if and only if R is connected and acyclic.Proof:? Let R is the symmetric closure of some tree

20、 T. Suppose that R has a simple cycle p: v1,v2,...,vn, v1. Then there is a figure of edges as the following in T. However, all possible orientation of the edges results a cycle in T.,,Unique Path,If T is an undirected t

21、ree, then for any vertices u, v, there is a unique uv-path in T. Proof: We know that T is connected, so, there is at least one uv-path in T. Suppose that there are two different uv-paths P,Q in T. Without loss

22、of generality, there exists an edge e=(x,y) satisfying e?P, and x is nearer to u on P than y, but e?Q. Let T*=T-{e}, then T* contains Q. Note that xu-segment on P +Q+vy-segment on P is an xy-path in T*. However, this pat

23、h plus e is a cycle in T. Contradiction.,No Edge Can Be Removed,Let T is an undirected tree, e is any edge in T, then T-{e} is no longer connected.Proof: We have know that for any vertices v,w, there is a unique vw-pat

24、h. Let e=(x,y), then e is the unique path between x and y. So, there is no xy-path in T-{e}, which means that T-{e} is no longer connected.,Adding One Edge Means Cycle,Let T is an undirected tree, u,v are two vertices no

25、t adjecent to each other, then T+(u,v) must contain a cycle.Proof: Since T is a undirected tree, there must be a uv-path in T. Let it be P, then P+(u,v) is a cycle in T+(u,v).In fact, we can prove that there is only

26、one cycle in T+(u,v).,Number of Vertices and Edges,A tree with n vertices has n-1 edgesProof:There are at least n-1 edges to connect n vertices.Suppose that there are more than n-1 edges. So, the sum of in-degree of

27、all vertices must be more than n-1. However, the in-degree of the root is zero, and in-degree of any of the other n-1 vertices is 1, which mean the sum is n-1. Contradiction.,Spanning Tree,If R is a symmetric, connected

28、relation on A, a tree T on A is a spanning tree of R if T is a tree with exactly the same vertices as R.An undirected spanning tree is the symmetric closure of a spanning tree.Note that an undirected spanning tree can

29、always obtained by remove some edges from a symmetric, connected relation R.,,,,,,,Spanning Tree: Examples,Different spanning tree are obtained from a symmetric, connected relation:,,Breaking cycles,Breadth first,Depth f

30、irst,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,1,2,3,4,5,6,7,8,9,10,11,12,,Merging Two Vertices,,,Matrix Operation for Merging,v0 v1 v2

31、 v3 v4 v5 v6,v0 v1 v2 v3 v4 v5 v6,,,,Constructing a Spanning Tree,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,a,b,c,d,a,a,a,b,b,b,c,c,c,d,d,d,0. Let a be the starting vertex, selecting edges one by one in original

32、R1. Merging a and c into a’({a,c}), selecting (a,c)2. Merging a’ and b into a”({a,c,b}), selecting (c,b)3. Merging a” and d into a”’({a,c,b,d}), selecting (a,d) or (d,b)Ending, as only one vertex left,(0),(1),(2),(3)

33、,Weighted Graph and MST,A weighted graph,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,27,26,42,21,21,53,25,33,28,36,18,17,34,29,22,A,I,H,J,E,C,B,G,F,D,16,21,25,The nearest neighbor of vertex I is H,The nearest neighbor of shaded

34、 subset of vertex is G,,Weighted Graph and MST,,,,,,,,,,,,,,,,,,,,,,,,,,,,,27,26,42,21,21,53,25,33,28,36,18,17,34,29,22,A,I,H,J,E,C,B,G,F,D,16,,,,,,,,,,,,,,,,,,,,,,,,,,,,,27,26,42,21,21,53,25,33,28,36,18,17,34,29,22,A,I

35、,H,J,E,C,B,G,F,D,16,,,,,,,,,,,,,,,,,,,,,,,,,,,,,27,26,42,21,21,53,25,33,28,36,18,17,34,29,22,A,I,H,J,E,C,B,G,F,D,16,21,21,21,25,25,25,A Spanning Tree: W(T)=257,A MST: W(T)=190,Algorithms for Minimal Spanning Tree,Greedy

36、algorithms for minimal spanning treeInput: a symmetric, connected relation R, with a non-negative weight on each edgeOutput: a minimal spanning tree of RProcedure: (Prim’s and Kruskal’s),,,,Prim’s Algorithm for MST,,,

37、,,,,,,,,,,,,,,,,,,,,,,,,,,27,26(9),42,21(4),21(8),53,25(6),33,28,36,18(2),17(3),34,29,22,A,I,H,J,E,C,B,G,F,D,16(7),21(5),25(1),Step 1: V={A}, E={}Step 2: Select the nearest neighbor of V, u, add the edge connect

38、ing u and some vertex in V into EStep 3: Repeat step 2 until E contains n-1 edgesEnd of Algorithm,Kruskal’s Algorithm for MST,,,,,,,,,,,,,,,,,,,,,,,,,,,,,27,26(9),42,21(4),21(7),53,25(9),33,28,36,18(3),17(2),34

39、,29,22,A,I,H,J,E,C,B,G,F,D,16(1),21(6),25(8),Step 1: E={}Step 2: Select the edge with the least weight, and not making a cycle with members of EStep 3: Repeat step 2 until E contains n-1 edgesEnd of