Math 314 Homework

Mathematics 314 Homework

All model solutions have now been transferred to WebCT.

Section	Exercise	Due date
1.1	12,14,19,25,29
1.2	17,20,28,29,35
1.3	12, 20, 25
2.1	18,39,44,46,64,70
2.2	5,20,31,extra	MATLAB file for 2.2.5
2.3	program Kruskal's algorithm
4.1	3,6,11(8,14)
4.3	(1,4,8,14,19) 2,13	Thu 4/15
5.1	31	Thu 4/15
5.1	7,8,12	Tuesday 4/27

Notes on the homework.

Latest homework model solution on WebCT is for problems on 5.1.

Note extension for latest homework to Tuesday.

Optional assignment - program Ford-Fulkerson. Revise the relevant sections of the textbook, the notes, and do the examples by hand first! Hand in by Thursday 4/22.

Extra exercises on 2.2, due 3/4.

Find a graceful labeling of the graph 'Y' given as an example of a tree which is not a caterpillar (next to definition of caterpillar in textbook).
Read the basic information on MATLAB. It was written for a linear algebra course, so you see how to create a matrix. Can you write a tiny program that calculates the degree of a vertex in a graph, given its adjacency matrix? Check out my program for computing the incidence matrix and test it using eg this adjacency matrix.
Email your program to me - not the output, only the program! Text-only format, please.
Here is a model solution.

Old extra exercise on 2.2.

Please calculate the Prufer code (the list of n-2 integers between 1,...,n) for the trees K_1,n-1 (the star on n vertices) assuming the special vertex is labeled 1.
Calculate the trees associated to the codes [12345] and [322176].

Only problems in boldface are to be handed in. If you have questions about some of the others, ask in class or come to my office hour.

The textbook has hints on some exercises in Appendix C. Exercises marked (!) are particularly instructive, useful or entertaining. Those marked (-) are easier, and those marked (+) harder than average. It is a good idea to do a few of the (-)-ones as warm-up and to see that you really are on top of the material. Even before that, you should look through the examples of the relevant section - many exercises are along the lines of some example worked out in the text.