TEMPLE CIS 166 - Discrete Mathematics and Its Applications

Unformatted text preview:

Discrete Mathematics – CIS166Section 10.1Definition:Slide 4Tournament TreesA Family TreeAncestor TreeForestTheoremRooted TreesSlide 11Slide 12Slide 13Slide 14m-ary treesSlide 16Ordered Rooted TreeProperties of TreesSlide 19Slide 20ProofSlide 22Slide 23Slide 24Slide 25Slide 26Slide 27Discrete Mathematics – CIS166TextDiscrete Mathematics and Its Applications (6th Edition)Kenneth H. RosenChapter 10: TreesBy Chuck AllisonModified by Longin Jan Latecki,Temple UniversitySection 10.1Introduction to TreesDefinition:A tree is a connected undirected graph with no simple circuits.Recall: A circuit is a path of length >=1 that begins and ends a the same vertex.ddTournament TreesA common form of tree used in everyday life is the tournament tree, used to describe the outcome of a series of games, such as a tennis tournament.AliceAntoniaAnitaAbigailAmyAgnesAngelaAudreyAliceAbigailAgnesAngelaAliceAngelaAliceA Family TreeMuch of the tree terminology derives from family trees.GaeaCronusPhoebeOceanZeus Poseidon Demeter Pluto Leto IapetusPersephoneApolloAtlas PrometheusAncestor TreeAn inverted family tree. Important point - it is a binary tree.IphigeniaClytemnestra AgamemnonLeda Tyndareus Aerope AtreusCatreusForestGraphs containing no simple circuits that are not connected, but each connected component is a tree.TheoremAn undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.Rooted TreesOnce a vertex of a tree has been designated as the root of the tree, it is possible to assign direction to each of the edges.Rooted Treesabcde fgabcdefgroot nodeabcd e f gh iparent of gsiblingsleafinternal vertexabcd e f gh iancestors of h and iabcd e f gh isubtree with b as its rootsubtree with c as its rootm-ary treesA rooted tree is called an m-ary tree if every internal vertex has no more than m 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.Ordered Rooted TreeAn ordered rooted tree is a rooted tree where the children of each internal vertex are ordered. Ordered trees are drawn so that the children of each internal vertex are shown in order from left to right.Properties of TreesA tree with n vertices has n-1 edges.Properties of TreesA full m-ary tree with i internal vertices contains n = mi+1 vertices.Properties of TreesA full m-ary tree with(i) n vertices has i = (n-1)/m internal vertices and l = [(m-1)n+1]/m leaves.(ii) i internal vertices has n = mi + 1 vertices and l = (m-1)i + 1 leaves.(iii) l leaves has n = (ml - 1)/(m-1) vertices and i = (l-1)/(m-1) internal vertices.ProofWe know n = mi+1 (previous theorem) and n = l+i,n – no. verticesi – no. internal verticesl – no. leavesFor example, i = (n-1)/mProperties of TreesThe level of a vertex v in a rooted tree is the length of the unique path from the root to this vertex.level 2level 3Properties of TreesThe height of a rooted tree is the maximum of the levels of vertices.Properties of TreesA rooted m-ary tree of height h is called balanced if all leaves are at levels h or h-1.Properties of TreesThere are at most mh leaves in an m-ary tree of height h.Properties of TreesIf an m-ary tree of height h has l leaves, then h lml o gProofFrom previous theorem:  hlhlmlmmh


View Full Document
Download Discrete Mathematics and Its Applications
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Discrete Mathematics and Its Applications and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Discrete Mathematics and Its Applications 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?