Math 12
mzlkha
WeeklySummary121.docWeekly Summary, Week 8, Chapter 12 Name:
Due on Saturday, October 20, by midnight.
Type your answers under the questions given below, or, print out this sheet, use pen or pencil to fill it out, and email a scan or photo of it to the instructor.
1) How many different (though some may be isomorphic) spanning trees can be found for a labeled K6 graph?
[Hint: Use Cayley's Formula.]
2) Suppose that a tree T has 500 vertices. How many edges are in the (complement of T) graph
T
?3) Evaluate the following expression, which is given in Polish notation:
+ ( 2 ^ + 6 4 3 ( ( 9 6 + 3 ( 8 5
4) Suppose that a balanced complete ternary (3(ary) tree with height 10 has 21683 leaves. How many internal vertices does it have at level 9? [Hint: use the result of 12.2, #20.]
5) The following is called an adjacency matrix for a graph G. The vertices of the graph are labeled 0, 1, 2, … , 9. They are listed on the left side of the rows and at the top of the columns. If two vertices x and y are adjacent, then a 1 will appear where column x meets row y. So for example, vertex 6 is adjacent to vertices 0, 1, and 2. Vertex 8 is adjacent to vertices 0, 3, and 7. Answer the questions below.
a) Does this graph contain any loops?
b) What is the significance of adding the sum of the numbers in a particular column (or row)?
c) How many edges are in the graph?
d) Is the graph G a connected graph? [Hint: you might use the method of example 12.12.]
