CompSci 10217.1Today’s topics••Instant InsanityInstant Insanity••TreesTrees––PropertiesProperties––ApplicationsApplications••Reading: Sections Reading: Sections 9.1-9.29.1-9.2CompSci 10217.2Instant Insanity••Given four cubes, how can we stack theGiven four cubes, how can we stack thecubes, so that whether the cubes are viewedcubes, so that whether the cubes are viewedfrom the front, back, left or right, one seesfrom the front, back, left or right, one seesall four colorsall four colorsCompSci 10217.3Cubes 1 & 2CompSci 10217.4Cubes 3 & 4CompSci 10217.5Creating graph formulation••Create multigraphCreate multigraph––Four vertices represent four colors of facesFour vertices represent four colors of faces––Connect vertices with edges when they areConnect vertices with edges when they areopposite from each otheropposite from each other––Label cubesLabel cubes••SolvingSolving––Find subgraphs with certain propertiesFind subgraphs with certain properties––What properties?What properties?CompSci 10217.6SummaryGraph-theoretic Formulation of Instant Insanity: Find two edge-disjoint labeled factors in the graph of theInstant Insanity puzzle, one for left-right sides and one forfront-back sides Use the clockwise traversal procedure to determine theleft-right and front-back arrangements of each cube.CompSci 10217.7Try it out:Find all Instant Insanity solution to the game with the multigraph:123411223344CompSci 10217.8Answer:12341234andCompSci 10217.9§9.1: Introduction to Trees••A A treetree is a connected undirected graph that is a connected undirected graph thatcontains no circuits.contains no circuits.––Theorem: Theorem: There is a unique simple path between anyThere is a unique simple path between anytwo of its nodes.two of its nodes.••A (not-necessarily-connected) undirected graphA (not-necessarily-connected) undirected graphwithout simple circuits is called a without simple circuits is called a forestforest..––You can think of it as a set of trees having disjoint setsYou can think of it as a set of trees having disjoint setsof nodes.of nodes.••A A leafleaf node in a tree or forest is any pendant or node in a tree or forest is any pendant orisolated vertex. An isolated vertex. An internalinternal node is any non-leaf node is any non-leafvertex (thus it has degree vertex (thus it has degree ___ ) ___ )..CompSci 10217.10Tree and Forest Examples••A Tree:A Tree:••A Forest:A Forest:Leaves in green, internal nodes in brown.CompSci 10217.11Rooted Trees••A A rooted treerooted tree is a tree in which one node is a tree in which one nodehas been designated the has been designated the rootroot..––Every edge is (implicitly or explicitly) directedEvery edge is (implicitly or explicitly) directedaway from the root.away from the root.••You should know the following termsYou should know the following termsabout rooted trees:about rooted trees:––Parent, child, siblings, ancestors, descendents,Parent, child, siblings, ancestors, descendents,leaf, internal node, leaf, internal node, subtreesubtree..CompSci 10217.12Rooted Tree Examples••Note that a given Note that a given unrootedunrooted tree with tree with nnnodes yields nodes yields nn different rooted trees. different rooted trees.rootrootSame tree exceptfor choiceof rootCompSci 10217.13Rooted-Tree Terminology Exercise••Find the parent,Find the parent,children, siblings,children, siblings,ancestors, &ancestors, &descendantsdescendantsof node f.of node f.abcdefghij klmnopqrrootCompSci 10217.14n-ary trees••A rooted tree is called A rooted tree is called nn-ary-ary if every vertex if every vertexhas no more than has no more than nn children. children.––It is called It is called fullfull if every internal (non-leaf) if every internal (non-leaf)vertex has vertex has exactlyexactly nn children. children.••A 2-ary tree is called a A 2-ary tree is called a binary treebinary tree..––These are handy for describing sequences ofThese are handy for describing sequences ofyes-no decisions.yes-no decisions.••Example: Example: Comparisons in binary search algorithm.Comparisons in binary search algorithm.CompSci 10217.15Which Tree is Binary?••Theorem:Theorem: A given rooted tree is a binary tree A given rooted tree is a binary tree iffiffevery node other than the root has degree every node other than the root has degree ___, ___,and the root has degree and the root has degree ___. ___.CompSci 10217.16Ordered Rooted Tree••This is just a rooted tree in which theThis is just a rooted tree in which thechildren of each internal node are ordered.children of each internal node are ordered.••In ordered binary trees, we can define:In ordered binary trees, we can define:––left child, right childleft child, right child––left left subtreesubtree, right , right subtreesubtree••For For nn-ary-ary trees with trees with nn>2>2, can use terms like, can use terms like““leftmostleftmost””, , ““rightmost,rightmost,”” etc.etc.CompSci 10217.17Trees as Models••Can use trees to model the following:Can use trees to model the following:––Saturated hydrocarbonsSaturated hydrocarbons––Organizational structuresOrganizational structures––Computer file systemsComputer file systems••In each case, would you use a rooted or aIn each case, would you use a rooted or anon-rooted tree?non-rooted tree?CompSci 10217.18Some Tree Theorems••Any tree with Any tree with nn nodes has nodes has ee = = nn11 edges. edges.––Proof:Proof: Consider removing leaves. Consider removing leaves.••A full A full mm-ary-ary tree with tree with ii internal nodes has internal nodes has nn==mimi+1+1nodes, and nodes, and ll=(=(mm11))ii+1+1 leaves. leaves.––Proof:Proof: There are There are mimi children of internal nodes, children of internal nodes, plus the root. And, plus the root. And, ll = = nnii = ( = (mm11))ii+1+1. . ••Thus, when Thus, when mm is known and the tree is full, we is known and the tree is full, wecan compute all four of the values can compute all four of the values ee, , ii, , nn, and , and ll,,given any one of them.given any one of them.CompSci 10217.19Some More Tree Theorems••Definition:Definition: The The levellevel of a node is the length of the simple of a node is the length of the simplepath from the root to the node.path from the
View Full Document
Unlocking...