Math 443/543, Fall 2012

Exams

• Exam 1 will be in class on October 8. It will cover Introduction to graphs, Transportation problems, Planar graphs and coloroings, and digraphs, traffic, and tournaments. (First through Fifth batches of notes). You may use one sheet of notes. Here is an old test 1 (not guaranteed to be representative of the exam).
• Exam 2 will be in class on November 28. It will cover graphs as matrices and page rank, graph laplacians, matching and stable marriage, and small world phenomena (Sixth through Ninth batches of notes). Here is an old test 2 (not guaranteed to be representative of the exam).
• Final Exam will be December 7, 1-3pm. It will cover all topics, including network flows. Here is an old final exam (not guaranteed to be representative of the exam).
• Office hours for the last week of class will be Thursday 3-4:30 and Friday 10-11:30.

C-x refers to Chapter x in Chartrand, BM-x refers to Chapter x in Bondy-Murty, etc.

Homework (to be done)

• C-1, problems 21, 22
• Induction Problem: Use mathematical induction to prove that the sum of an even number of odd numbers is even and an odd number of odd numbers is odd. (Hint: recall that even numbers can be enumerated as 2n for n=0,1,... and that odd numbers can be enumerated as 2m+1 for m=0,1,2,...)
• C-2, problems 1, 2, 3, 5, 6, 7, 10, 14,15, 16, 18
• C-2, problems 36,40,43,45,46,53,57.
• C-3, problems 1, 2, 7, 17, 18, 23, 24
• BM- 18.1.1
• C-9, problems 2, 3, 8, 9, 15, 21, 24, 25, 27
• BM- 10.1.7
• C-4, problems 4, 6, 7, 12, 13, 14, 18
• C-7, problems 4, 7, 8, 9, 11, 13, 17, 19, 20 (see p. 156 for definition of transmitter and receiver)
• C-10.1 - read about "incidence matrices" on p. 220. Do problems 2, 4, 7, 9
• BL-Exercises 1, 3, 5
• BL - Exercises 7,8,9,10,11
• Problem sheet 1 - updated 11/16
• C-5, 20, 24, 27
• Problem sheet 2 on stable marriage.
• Problem sheet 3 on small world. - updated 11/19
• Problem sheet 4 on network flows
• BM - 7.1.2, 7.1.3

Homework assignments (to be turned in)

• Due Wednesday, September 5: C-2 problems 3, 15, 18, Induction Problem listed above.
• Due Wednesday, September 19: C-2 problem 53, C-3 problems 7, 23
• Due Wednesday, October 3: C-9 problems 8, 25, Read the definition of dual of a plane graph in BM on p. 252, then do 10.3.8a (note that e(G) denotes the number of edges and v(G) denotes the number of vertices).
• Due Wednesday October 24: C-10.1 problem 7, BL- Exercises 1,5
• Due Wednesday November 7: Problem Sheet 1- problems 1, 6, 7, 8
• Due Monday November 26: Problem Sheet 2 - problems 1, 3 ,Problem Sheet 3 - problems 6a, 7 (you may use the result from problem 5 if needed).