Exam 3: May 17, 2006, 11am--1pm
Extra Office Hours: Friday, May 12, 1:30-4pm

Exam 3 covers all classes from April 7 through May 12, including Sections 5.1, 5.3, 7.1, & 7.2 from the book, and notes on minimum spanning trees, the traveling salesman problem, shortest path, maximum and perfect matchings, and max flow/min cut.

Determination questions

• You may have to give examples of graphs satisfying certain criteria.
• You may have to give and prove a formula for the number of H subgraphs in a family of graphs G (like 5.1 & 5.3)
• You may have to find or count the spanning trees of a graph.
• You may have to implement Kruskal's algorithm to find the minimum cost spanning tree.
• You may have to find an optimal Traveling Salesman tour.
• You may have to find a Traveling Salesman tour within two times optimal.
• You may have to implement the Hungarian algorithm to find a maximum matching in a graph.
• You should know the difference between maximum matching and maximal matching.
• You may have to apply Hall's Marriage Theorem.
• You may have to implement the Gale-Shapley algorithm to find a perfect matching of stable marriages.
• You may have to determine if given set of flows on edges is indeed a flow in the network.
• You may have to implement the Ford-Fulkerson algorithm to find a max flow and min cut.
• You may have to prove that a given flow is maximal or given cut is minimal.
• You may have to apply the ideas of max flow / min cut to solve some problem (like we did with transshipments, max matching, and vertex cover on the homework)
• You may have to find a vaild transshipment or show why one does not exist.
• You will not have to know anything about optimization or linear programming.

Proofs

• There will be proofs. They will all be provable using facts you've learned about graphs and the theorems from the book. I will try to not make them too difficult!
• I can't give any more information, but check out the practice problem set on the Homework part of the website.

Exam 2: April 6, 2006
Extra Office Hours: Wednesday, April 5, 1:45-3:45pm

Exam 2 covers all classes from February 22 through April 4, including Sections 4.3, 8.1-8.3, 9.1-9.2, & 10.3 from the book, and notes on connectedness, matrices in graph theory, and other topics.

Determination questions

• You may have to give examples of graphs satisfying certain criteria.
• You may have to determine a statistic of a graph, such independence number or crossing number.
• You may have to determine the connectivity or edge connectivity of a graph.
• You may have to determine a maximal independent set or a minimal vertex cover of a graph.
• You may have to determine if a graph is planar or critical planar.
• You may have to find a planar embedding of a graph, and perhaps use Euler's formula.
• You may have to show that a graph is not planar using Kuratowski's Theorem.
• You will not have to deal with thickness or genus.
• You may have to find a block decomposition of a graph.
• You may have to find the dual graph to a given graph.
• You may have to find an adjacency matrix and/or incidence matrix of a graph.
• You may have to interpret an adjacency matrix and/or powers of an adjacency matrix.
• You may have to interpret eigenvalues and eigenvectors of an adjacency matrix.
• You will not have to use the Matrix Tree Theorem.
• You may have to find a de Bruijn sequence or graph.
• You may have to find a knight's tour or explain why one does not exist.

Proofs

• There will be proofs. They will all be provable using facts you've learned about graphs, the theorems from the book and Lemmas A-B. I will try to not make them too difficult!
• I can't give any more information, but check out the practice problem set on the Homework part of the website.

Exam 1: February 23, 2006
Extra Office Hours: Wednesday, February 22, 1:45-3:45pm

Exam 1 covers all classes from January 23 through February 20, and Sections 1.1-2.3 & 3.1 from the book.

Determination questions

• You may have to give examples of graphs satisfying certain criteria.
• You may have to determine if the degree sequence of a graph is graphic.
• You may have to determine if two graphs are isomorphic, and exhibit an isomorphism between them.
• You may have to determine a statistic of a graph, such as those on your worksheet.
• You may have to determine if a graph is critical.
• You may have to find a perfect matching in a graph.
• You may have to find a Hamiltonian cycle and/or an Eulerian circuit in a graph.

Proofs

• There will be proofs. They will all be provable using facts you've learned about graphs, the theorems from the book and Lemma A. I will try to not make them too difficult!
• I can't give any more information, but check out the practice problem set on the Homework part of the website.

Exam Expectations
        The exams are given in the Thursday sections of class, so they are 1:25 long. I plan to make the tests 1:00 long, so that there will be minimal time pressure. There will be proofs on the test, but because of the time constraints they can not be long proofs. That is not to say that they will take a short amount of time to ponder, but at least one solution is less than two paragraphs long. The time constraint also implies there will not be too many proof questions.
        Of course, you will need to justify all your answers in order to have full credit, just like on the homework. If you use any theorems or methods, state them by name.
        A good place to start organizing your knowledge from the course is to go to the Topics Covered section of the web page. This will give you a chance to see what material we have covered, and allow you to see if there are any definitions that don't make sense to you.