Math 318, Graph Theory, Spring 2007

Professor Terry Loring, Department of Mathematics and Statistics,

• There are many deadlines regarding grading and registration which are listed by the Office of the Registrar of the University of New Mexico
• The text is A First Look at Graph Theory by Clark and Holton, ISBN 9810204906.
• The catalog states you need instructor's permission to take this class. This is not exactly as intended. If you have passed as semester of calculus you are fine. If you have not taken a semester of calculus, you may still be fine.
• I'll send eMail via your UNM accounts. Check this several times per week, or turn on forwarding to an account you frequent: How To #504 - Forward Your UNM Electronic Mail.

Week One, January 15 - 19, 2007

• A list of topics
• Wednesday: Discuss policies, set midterm dates. The definition of a graph. §1.1
• Friday: Graphs as Models §1.2

Week Two, January 22 - 26, 2007

• Monday: Definitions: isomorphism, bipartite, etc. §1.3
• Incidence information in the definition of a graph.
• Isomorphism as common relabelings.
• Homework 1, due January 29
• Bondy and Murty. A classic, now out of print.
• Since a few of you asked: Typesetting graphs in latex using xy-pic.
• Wednesday: §1.4
• Friday: Subgraphs §1.5

Week Three, January 29 - February 2, 2007

• Degree Sequences .
• Classifying small graphs (very small).
• Homework 2, due February 9
• Monday: Paths and walks, degree sequence. § 1.6
• Wednesday: bipartite graphs. Classifying "up to isomorphism" § 1.6
• Friday: adjacency matrix. § 1.7

Week Four, February 5 - 9, 2007

• Homework 3, due February 16
• We are skipping § 1.8, for now.
• Trees, § 2.1
• Spanning Trees, § 2.2
• Classifying Trees.

Week Five, February 12 - 16, 2007

• Bridges, § 2.3
• Minimum Weight Spanning Trees (Kruskal's Algorithm), § 2.4
• If you missed Wednesday's lecture, you can probably figure out Kruskal's algorithm just fine from this Minimum Weight Spanning Tree Example
• Don't worry about Prim's algorithm.

Week Six, February 19 - 23, 2007

• Monday: A few review problems
• Wednesday: Midterm I
• Friday: Minimum Spanning Trees, § 2.4

Week Seven, February 26 - March 2, 2007

• Monday: Shortest Path Problems, § 2.5
• Wednesday: Cut Vertices, indepenedent paths, § 2.6
• Examples of Dijkstra's algoritm to find lowest-cost paths
• Homework 4, due March 5
• Friday: Euler Circuits, § 3.1

Week Eight, March 5 - 9, 2007

• Homework 5, due March 21
• Monday: The Chinese Postman Problem, § 3.2
• Finding Euler Circuits, Solving Postman problems

Spring Recess, March 11-18, 2007

Week Nine, March 19 - 23, 2007

• Homework 6, due March 19
• Knight's Tours, five by six
• We are skipping 3.4
• Friday: § 4.1 (Matchings)

Week Ten, March 26- 30, 2007

• Monday: § 4.1 (Matchings)
• Wedneday: § 4.2 The Marriage Problem
• Friday: § 5.1, Plane and Planar Graphs.
• fun with the Peterson Graph
• Matching algorithms to be use in medical transplant matchings.
• We are skipping § 4.3-5.

Week Eleven, April 2 - 6, 2007

• Homework 7, due April 13
• Monday: § 5.2, Euler's Formula.
• Wednesday: § 5.2
• Friday: § 5.3, Regular Polyhedra.

Week Twelve, April 9 - 13

• Monday: § 5.4, Kuratowski's Theorem
• Wednesday:§ 5.5, Grinberg's Theorem
• Friday:§ 5.6, The dual of a plane graph
• Review problems Updated to have 5 problems

Week Thirteen, April 16 - 20, 2007

• Monday: Review. The midterm will cover: § 2.1-6, including cut vertices a bridges, not degrees of connectivity; § 3.1-2; § 4.1-2; § 5.1-2.
• Wednesday: Midterm II
• Friday:

Week Fourteen, April 23 - 27, 2007

• Homework 8, due May 2

Week Fifteen, April 30 - May 4, 2007

• The final will cover all the material mentioned above for the first two midterms, plus § 6.1-2.
• Review problems, III

Finals Week, May 7-11

• the home page of the Office of the Registrar
• Wednesday, May 9, Final 10:00 a.m.-12:00 p.m.