tailieunhanh - Lecture Discrete mathematics and its applications (7/e) – Chapter 11: Trees

Lecture Discrete mathematics and its applications (7/e) – Chapter 11: Trees. This chapter presents the following content: Introduction to trees, applications of trees, tree traversal, spanning trees, minimum spanning trees. | 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 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 ). 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 ). 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 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 .