Math 12

Discrete Mathematics

Readings Check section 12.2

Read Section 12.2

Type in the answers below each question and email the completed document to me, or print out the document and fill it out by hand and email a scan or photo of it to me.

1) In a rooted tree, if r is the root, what is the numerical value of id(r)? [Where id(x) is the "in degree" of vertex x, which is the number of vertices pointing toward x and adjacent to x.]

2) In a rooted tree, if v is a vertex other than the root, what is the numerical value of id(v)?

3) In a rooted tree, if v is a vertex with od(v) = 0, what is v called? [Where od(v) is the "out degree" of vertex v, which is the number of vertices that v points to.]

4) In the tree in figure 12.12, what are the children of vertex 1?

5) In the tree in figure 12.12, what is the level of vertex 1.2.3?

6) What type of rooted tree has od(v) = 0 or 2 for all vertices?

7) When converting a mathematical expression into Polish (prefix) notation, what symbols are removed from the original expression?

8) In a preorder traversal, what is visited first, the root or the subtrees?

9) In a postorder traversal, what is visited first, the root or the subtrees?

10) In an inorder traversal, three things are visited: root, left subtree, and right subtree. What is the order in which these three are visited?

11) With regard to a graph G = (V, E), what exactly is the depth first search used to find?

12) What type of tree has od(v) = 0 or 5 for all vertices?

13) If T is a complete 3-ary tree with 31 vertices, how many internal vertices does T have? [Theorem 12.6]

14) What is the height of the tree in figure 12.23(c)? [definition 12.6]

15) Using corollary 12.1, what is the height of a balanced complete 4-ary tree with 1025 leaves?

After submitting this form, go on to watch the videos, read the notes, and start the homework assignment for section 12.2. Ask any questions that arise at any point in the process. When the homework assignment is done, and you feel that you have a solid understanding of the homework and the section, then take the quiz for section 12.2.