Problem Set VIII, for Friday, May 29

Mathematics 61

Spanning Trees:

• Exercise 18.   Support your answer.   (Here the phrase "under what conditions" is open-ended.   You want to produce a criterion that does not mention spanning trees.)

Minimal Spanning Trees:

• Exercise 2.   Start at 1.   Also give the total weight of the minimal spanning tree constructed, and list the vertices (starting with 1) that Prim's algorithm adds to the minimal spanning tree, in the order in which the algorithm adds them.
• Exercise 3.   Start at 1.   Also give the total weight of the minimal spanning tree constructed, and list the vertices (starting with 1) that Prim's algorithm adds to the minimal spanning tree, in the order in which the algorithm adds them.

Basic Principles (for Counting):

• Exercise 58.   Suggestion: How many arrangements are there in which the art books are together?   Compare Exercise 57, which has an answer in the book.
• Exercise 59.
• Exercise 67.   As the book says, Exercise 65 gives the general rule being applied here.   The problem asks for strings that start with 1 or end with 1 or both.

Click here for answers in .pdf format.