Math 318, Graph Theory, Spring 2009
- The catalog states you need instructor's permission to take
this class. This is not exactly as intended. If you have passed
a semester of calculus you are fine.
If you have not taken a semester of calculus, but have top grades
in precalc courses adn want to take this class, you should contact me.
-
Catalog Course Descriptions
- 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.
- 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 19 - 23, 2009
Monday: Martin Luther King, Jr. Day, holiday, January 19.
- Wednesday: The definition of a graph. Loops vs. links. §1.1
- A more standard definition of a graph.
- Friday: Graphs as Models §1.2 An informal definition
of isomorphism. Definitions of degree, incidence, adjacence,
parallel edges.
- Isomorphism as common relabeling.
- Our book's definition of a graph excludes the so-called
null graph. This has zero vertices and zero edges.
Search on the phrase "is the null graph a pointless
concept" and enjoy.
Week Two, January 26 - 30, 2009
- Tentative grading percentages: MidI 25%; MidII 25%; HW 20%; Final 30%.
- Monday: Definitions: isomorphism, bipartite, odd
even, isolated, degree sequence. §1.3
- Homework 1 due by class time on February 2.
- Wednesday: The handshake lemma: vertex degrees sum
to twice the edge count. §1.4
- Friday: Subgraphs §1.5
- Despite what the text says on page 17, please distinguish
"is a subgraph" from "is isomorphic to a subgraph."
- It is known which sequences arise as degree sequences of some
simple graph. See problem 1.5.6 in the classic
"Graph Theory with Applications"
by Bondy and Murty.
Week Three, February 2 - 6, 2009
- Monday: Paths, walks, trails,
cycles, open walk, closed walk. Classifying
"up to isomorphism" § 1.6
- Homework 2 due by class time on February 9.
- Wednesday: definition of a regular graph.
Connected components. § 1.6
- Classifying up to isomorphism all simple graphs
with degree sequence (1,1,1,1,2,2,4).
- Friday: bipartite equals "no odd cycles."
Week Four, February 9 - 13, 2009
- Monday: adjacency matrix. § 1.7 Trees.
Pathes are unique in trees § 2.1
- Homework 3 due February 16.
- Wednesday: Classifying small trees.
- Friday: Spanning Trees, § 2.3 Classifying connected simple
graphs with five vertices and five edges.
Isomorphic simple graphs have isomorphic complements.
Week Five, February 16 - 20, 2009
Week Six, February 23 - 27, 2009
Week Seven, March 2 - 6, 2009
Week Eight, March 9 - 13, 2009
- Monday: Hamiltonian graphs. § 3.3
- Homework 6, due March 23.
- Wednesday: Knight's Tours, six-by-six
I was mistaken in class. The stategy we started with does work.
- Friday: Hamiltonian graphs, continued.
- We are skipping page 104 to 107 of § 3.3.
- We are skipping § 3.4
- Reminder: I do not accept late homework. If you can't attend class,
you can scan it and email it in, or slide it under by office door.
Also, I drop the two lowest scores, and will create makeup assignments
for multi-week emergences.
March 16 - 20: Spring Break , 2009
Week Nine, March 23 - 27, 2009
- Monday: Matchings § 4.1
- Homework 7, due March 30.
- Wednesday: The Marriage Problem,
Matchings in bipartite graphs § 4.2, 4.3
- Friday: Optimal assignments § 4.5
- We are skipping § 4.5.
Week Ten, March 30 - April 3, 2009
Week Eleven, April 6 - 10 , 2009
- Monday: Review.
- The midterm will not cover § 4.5.
- Wednesday: April 8, Midterm II
- Friday: The dual of a plane graph, § 5.6.
Week Twelve, April 13 - 17 , 2009
- Monday: Directed graphs, basic definitions, § 7.1.
- Wednesday: In-degree and out-degree. § 7.2.
- Homework 9, due April 22.
- Friday: Tournaments. § 7.3.
Week Thirteen, April 20 - 24 , 2009
- Monday: Traffic flow. § 7.4.
- We are skipping the Hopcroft and Tarjan algorithm (pages 256 to
328).
- Wednesday: Networks. Flows and Cuts. § 8.1.
- Friday: Max Flow equals Min Cut.
- We are skipping § 8.2.
- Homework 10 (now 4 problems), due May 1.
Week Fourteen, April 27 - May 1 , 2009
- Monday: Menger's theorem. Edge connectivity. § 8.3.
- Wednesday: Menger's theorem, edge and vertex versions.
- Friday: Graphs on a torus or on a Klein bottle.
Week Fifteen, May 4 - 8 , 2009
Finals Week May 11-16, 2009
Math 327, Spring 2009