SPRING SEMESTER 2009
MATH 475 - Graph Theory and Combinatorics
HOMEWORK ASSIGNMENTS.

Text Alan Tucker Applied Combinatorics

Section Problems Due
1.1 Graph models 4, 7, 18 Feb. 12
1.2. Isomorphisms 6(a)-(e), 11 Feb. 12
1.3 Edge counting 8, 10, 14 Feb. 12
1.4 Planar Graphs 6, 11, 12 (a), (b) Feb. 19
2.1 Euler cycles 2, 5, 9 Feb. 19
2.2 Hamilton Circuits 2, 4 (a)-(d) Mar. 5
2.3. Graph Coloring 1 (a)-(d), 2 (a)-(b), 10 Mar. 5
2.4. Coloring Theorems 6, 14 Mar. 5
3.1 Properties of trees 1(a)-(b), 14, 24, 28 Mar. 24
3.2 Search trees and spanning trees 2, 4, 7, 11 Mar. 24
4.1 Shortest path 3, 4 Apr. 2
4.2 Minimum spanning trees 5, 11 Apr. 2
4.3 Network flows 2 (a)-(b), 8 Apr. 2
4.4 Algorithmic Matching 2, 16 Apr. 2
4.5 Transportation problem 4, 8 Apr. 2
5.1 Basic counting principals 6, 16, 18, 22 Apr. 9
5.2 Simple arrangements and selections 2, 12, 14, 20 Apr. 9
5.3 Arrangements and selections with repetitions 4, 10, 22 Apr. 23
5.4.Distributions 2, 8 Apr. 23
5.5 Binomial Identities 23, 32 Apr. 23
8.1 Venn Diagrams 12, 18 Apr. 30
8.2 Inclusion exclusion formula 12, 28, 38 Apr. 30
7.1 Recurrence relations 4, 18 Apr. 30
7.3 Linear recurrence relations 3, 5 Apr. 30
7.2 Divide-and-conquer relations 4 May 7
7.4 Inhomogeneous recurrence relations 8, 9, 11 May 7
6.1 Generating functions models 2, 3 May 7
6.2 Calculating coefficients of generating functions 4, 11, 18 Not graded
6.5 Summation methods 1 , 2 Not graded
7.5. Solving recurrence relations using generating functions 1, 2, 3 Not graded