Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Discrete mathematics and its applications - Lecture 14

This lesson looks at the processors most commonly found in personal computers and describes some of their most important features and distinguishing characteristics. You w ill learn how these CPUs arc typically differentiated from one another and sec how their performance is measured. You also will learn some of the ways you can extend the power of your PC’s processor to other components by using its expansion capabilities. | Trees Chapter 11 Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Chapter Summary Introduction to Trees Applications of Trees (not currently included in overheads) Tree Traversal Spanning Trees Minimum Spanning Trees (not currently included in overheads) Introduction to Trees Section 11.1 Section Summary Introduction to Trees Rooted Trees Trees as Models Properties of Trees Trees Definition: A tree is a connected undirected graph with no simple circuits. Example: Which of these graphs are trees? Solution: G1 and G2 are trees - both are connected and have no simple circuits. Because e, b, a, d, e is a simple circuit, G3 is not a tree. G4 is not a tree because it is not connected. Definition: A forest is a graph that has no simple circuit, but is not connected. Each of the connected components in a forest is a tree. Trees (continued) Theorem: An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices. Proof: Assume that T is a tree. Then T is connected with no simple circuits. Hence, if x and y are distinct vertices of T, there is a simple path between them (by Theorem 1 of Section 10.4). This path must be unique - for if there were a second path, there would be a simple circuit in T (by Exercise 59 of Section 10.4). Hence, there is a unique simple path between any two vertices of a tree. Now assume that there is a unique simple path between any two vertices of a graph T. Then T is connected because there is a path between any two of its vertices. Furthermore, T can have no simple circuits since if there were a simple circuit, there would be two paths between some two vertices. Hence, a graph with a unique simple path between any two vertices is a tree. Trees as Models Trees are used as models in computer science, chemistry, geology, botany, psychology, and many other areas. Trees were introduced by the mathematician . | Trees Chapter 11 Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Chapter Summary Introduction to Trees Applications of Trees (not currently included in overheads) Tree Traversal Spanning Trees Minimum Spanning Trees (not currently included in overheads) Introduction to Trees Section 11.1 Section Summary Introduction to Trees Rooted Trees Trees as Models Properties of Trees Trees Definition: A tree is a connected undirected graph with no simple circuits. Example: Which of these graphs are trees? Solution: G1 and G2 are trees - both are connected and have no simple circuits. Because e, b, a, d, e is a simple circuit, G3 is not a tree. G4 is not a tree because it is not connected. Definition: A forest is a graph that has no simple circuit, but is not connected. Each of the connected components in a forest is a tree. Trees (continued) Theorem: An undirected graph is a tree if and only if .