Syllabus for CSC/Math 4408 and CSC 5408, Dr. Ellen Gethner

CSC/Math 4408 and CSC 5408, Applied Graph Theory (Spring 2008)

Syllabus

automatically updated on 29 January 2008

[ Instructor | Class Time and Room | Textbook | Prerequisites | Objectives | Grades and Policies | Schedule| Academic Deadlines (pdf) | Student Page ]

The Student Page is up and running. Contact Luke at luke dot guildner at email dot cudenver dot edu if you have trouble logging on.
Click here To Obtain a Free copy of Mathematica for your home computer.
Please e-mail a recognizable digital photo of yourself to Luke before Monday 28 January. luke dot guildner at email dot cudenver dot edu

Instructor

Dr. Ellen Gethner
Email: ellen dot gethner at cudenver dot edu
Office: North Classroom 2604-A3
Phone: (303) 556 2358 (Use at your own risk)
Office hours:

2:15-3:45pm Mon and Wed
8:15-9:15pm Mon
11:30-12:30 Tues
and by appointment

Class Time and Room

Mondays and Wednesdays 4:00-5:15pm in North Classroom 1315. (Note last minute change!!!!)
We will also meet regularly in the Raytheon Lab to do Mathematica work.

Textbook: none required

If you want to buy a book here are some suggestions. All are available at Amazon.com.

Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, by Sriram Pemmaraju and Steven Skiena; Cambridge University Press, 2003 (for help with the Combinatorica package in Mathematica)
Introduction to Graph Theory (4th Edition), by Robin J. Wilson; Prentice Hall or Addison Wesley, 1996 (for both undergraduates and graduates for general graph theory information)
Introduction to Graph Theory (2nd Edition), by Douglas B. West, Prentice Hall, 2000 (especially for graduate students as a good resource for projects, and most other things graph theoretic)

Other (optional) resources:

Graph Theory with Applications by Bondy and Murty (free download)
Pearls in Graph Theory : A Comprehensive Introduction, by Nora Hartsfield; Dover (available at the Tattered Cover Bookstore in LoDo)
Introduction to Graph Theory, by Chartand and Zhang (2005)
Discrete Mathematics with Algorithms by Albertson and Hutchinson (free download)
Online Graph Theory Warmup by Chris Caldwell
Planar Graph Java Applet Game

Prerequisites

Either CSC 2411 (Discrete Structures) or Math 3000 (Introduction to Abstract Math). Each student must sign and return a prerequisite agreement form to receive any credit for any assignment or exam. If this form is not returned by the 3rd week, the student will be administratively dropped from the course.

Course Objectives

We will begin by acquiring knowledge of the basic tools in Graph Theory (models and representations, basic results on degrees, isomorphism, and connectivity. Then we will move on to more advanced topics such as Trees, Planarity, and Graph Coloring (including the Four Color Theorem), thickness, and games with graphs. If time permits, we will talk about the graph algorithm that is at the heart of Google's success.

Grades and Policies

Assignments: Homework assignments (six) will count toward forty percent of your grade. Each assigment will have an assortment of straightforward problems as well as challenging problems. Write up your ideas on all of the problems that you have given some thought to, even if you do not believe you have a complete solution. Be sure to be neat, write in complete sentences, and do not leave out any steps: clarity of exposition may contribute toward a positive score. Please talk to one another about the assignments, but the write-ups should be done individually, giving credit where credit is due.
Late assignments: None allowed. There are no exceptions. I will drop the lowest homework score. This means you may choose to miss an assignment and the score of 0 will be dropped.
Examinations: There will be one midterm examination worth thirty percent of your grade and a final examination, also worth thirty percent of your grade. The midterm exam must be taken on Monday, March 10th in class: NO EXCEPTIONS. A missed midterm will be assigned a failing grade. The final examination will be given only once, on the date assigned by the registrar: NO EXCEPTIONS.
A project proposal, final paper, and conference style presentation will replace the final examination for graduate students who have signed up for CSC 5408.

Schedule

Lecture	Date	Topic(s)	Comments	Reading	Assignment	Criteria
One	23 January 2008 (Wednesday)	Introduction to Graph Theory	The Party Problem; graphs as models	Class Notes
Two	28 and 30 January 2007	Vocabulary and Definitions and Mathematica Demo	Points, nodes, vertices, endpoints, loops, multiple edges; Directed, Undirected, and Simple Graphs; Multigraph; Real world examples modelled by Graph Theory; Graph Isomorphism with examples; More vocabulary: degree, adjacencies, neighbors, incidence; Classes of Graphs: complete,... To be continued	Class Notes	Homework 1 handed out on January 30th. Hardcopy due in class on Monday 11 February. Send a copy of your Mathematica work to me by email before class on February 11th.
Three	5 and 7 February 2008	Mathematica Session on Monday; graph classes and some graph gadgets	Graph Classes, continued: bipartite, complete bipartite, n-star, path, simple path, cycle, simple cycle; Degree sequence, special property of sum of degrees of a graph, k-regular graphs; Subgraphs (supergraphs): induced, proper, spanning	Class Notes and section 1.4 in our text for an overview of Mathematica.	Homework 1 is due on Monday: Don't forget to send by email (to Dr. Gethner) your Mathematica notebook that generates your graphic output!
Four	11 and 13 February 2007	More Vocabulary; Special Topic: Graphic Degree Sequences	Connecteness: component, maximal, number of connected components,induced subgraph, distance between two vertices, the Girth of a graph, the Peterson Graph. Proof of correctness of the Havel-Hakimi Algorithm. Begin Trees.	Class Notes
Five	18 and 20 Feb 2008	Special Topics. Meet in our regular classroom.	Matrices and Graphs: New Gadgets; Trees: Definition and Characterization Theorem; powers of the adjacency matrix of a graph and what the entries mean	Class Notes and Mathematica and Matrix Multiplication	Homework 2 due on 18 February in or before class.
Six	25 and 27 Feb 2008	Feb 18th, 2nd Mathematica Session in the Raytheon Lab; Feb 21st, more on Trees.	Adjacency Matrix, continued: an algorithm to test connectivity; Trees: Unique path characterization, number of edges in a tree	Class Notes and Section 8.6 of our text, and TreeQ, IsomorphicQ, DegreeSequence, and RealizeDegreeSequence	Homework 3 is due on Monday 25 February 2008
Seven	3 and 5 March 2008	Trees and Connectivity	Bridges, connectivity and another tree characterization; w(G) versus w(G\e), characterization of bridges; Tree edges are bridges; \|E(G)\| and and \|V(G)\| with respect to w(G); Minimum number of edges needed for a graph to be connected; yet another tree characterization theorem (three equivalent statements); Spanning trees and characterization of connected graphs; Special Topic: number of spanning trees by way of deletion and contraction.	Class Notes	For the midterm, study lecture notes through the Proof of Theorem 3.3. Study homeworks 1-3. You may bring two 4" by 6" notecards with any notes (both sides) that you care to bring to the exam.
Eight	10 and 12 March 2008	Midterm plus Spanning Trees, continued	Monday 10th March: Midterm Exam	Class notes and Section 8.2.3 in text	Homework 4 arrives next week
Nine	17 and 19 March 2008	Spanning Trees, continued	Cayley's Theorem on the number of spanning trees of a complete graph; Defn of contraction along an edge; Big Problem in Three Parts that leads to a recursive algorithm to count the number of spanning trees of an arbitrary graph; Big Example of how to use Big Problem to count spanning trees; Matrix Tree Theorem (an alternative method for counting spanning trees)	Class notes and Section 8.2.3 again	Homework 4 has arrived. It is due on March 31st.
Ten	17 and 19 March 2008	Special Topic in Chapter 3: Optimization by way of finding minimum spanning trees.	Kruskal's Algorithm and Prim's Algorithm for finding minimum spanning trees. Definition of weighted graph.	Class notes and Section 8.2.2 in text	Homework 5 arrives on Wednesday and is due on Wednesday 9 April.
Ten	24-30 March 2008	Spring Break
Eleven	31 March and 2 April 2008	Special Topic in Chapter 3: Optimization by way of finding minimum spanning trees.	Kruskal's Algorithm and Prim's Algorithm for finding minimum spanning trees. Definition of weighted graph.	Class notes and Section 8.2.2 in text	Homework 5 arrives on Wednesday and is due on Wednesday 9 April.
Twelve	7 and 9 April 2008	Chapter 4: Connectivity.	A theorem due to Whitney: a relation among edge connectivity, vertex connectivity, and minimum vertex degree. Begin a new special topic related to connectivity: Building reliable communications networks. Given integers k and n with k smaller than n, first find the minimum number of edges that a k-connected graph on n vertices must have. Next, construct such a graph to show that the edge bound is sharp.	Class notes and pp 242-243 in text
Thirteen	14 and 16 April 2008	Connectivity continued. Chapter 5: Begin planarity.	Construct a reliable (ie k-connected graph on n vertices) communications network with the fewest number of edges. Menger's Theorem: connectivity from a different point of view. New Chapter: chapter 5. Definition of plane and planar graphs. Euler's formula for a plane embedding of a planar graph. The complete graph on five vertices is not planar.	Class notes and Section 7.2.6 (Harary Graphs) Section 8.7 (planarity) in our text	The topic of Hamiltonian and Eulerian Graphs is included in Homework 5, which is due this week on Wednesday.
Fourteen	21 and 23 April 2008	Planarity.	Polyhedral Graphs. Average vertex degree of planar (and hence polyhedral) graphs. Dual of a plane graph. Special Topic: The Platonic Solids. Why there are only five of them (tetrahedron, cube, octahedron, icosahedron, dodecahedron). Characterization of Planar Graphs: Subdivision of a graph. Contraction along an edge, revisited. Contractible edge (one that preserves connectivity). Existence of contractible ecdges in simple 3-connected graphs. First half (and harder part) of Kuratowski's Theorem: a graph with no subdivision of K5 or K3,3 is planar.	Class notes and knowledge of Mathematica objects TetrahedralGraph, OctahedralGraph, CubicalGraph, DodecahedralGraph, and IcosahedralGraph.	Homework 6 (last one!) arrives Monday 14 April and is due on Monday 28 April.
Fifteen	28 and 30 April 2008	Finish Characterization of Planar Graphs. Begin Chapter 6: Coloring Graphs	Other half of Kuratowski's Theorem: Any graph with a subdivision of K5 or K3,3 is not planar. New Topic and Chapter: Graph Coloring (an elegant euphemism for scheduling). Crayola Airlines and Their Big Problem. Graph Model: k-coloring, proper k-coloing, color class, chromatic number. Five immediate facts about the chromatic number of a graph (see class notes). Characterization of graphs with chromatic number 2. Brook's Theorem (proof ommitted, technique to come later). Coloring Maps in the Plane: History of the Four Color Theorem. Proof of the Six Color Theorem.	Class notes and page 181 of our text for helpful hints on displaying graphs with colored vertices. ChromaticNumber and MinimumVertexColoring will be useful Mathematica commands to know, too.
Sixteen	5 and 7 May	Graph Coloring Finished. Google and Instant Insanity [k-factors, particularly 2-factors of a graph]	Proof of the Five Color and Four Color Theorems for Planar Graphs. Thickness-Two Graphs and a Chromatic Mystery; an application to testing printed circuit boards (handouts included). Mathematical Dessert: How Google Works. Games on Graphs: A graph theory solution to the game of Instant Insanity (k-factor of a graph, particularly 2-factors).	Class Notes and Herb Wilf's Note on Searching the Web and Grad Student Project by Sergey Brin and Lawrence Page, where Google was Born.
Seventeen	Week of 12 May 2008	FINAL EXAM: time and date to be determined by registrar.	The Final Exam is comprehensive, but Google, and Instant Insanity will not be on the exam. Mathematica will not be tested, either.	Extra office hours to be determined	You may bring four 4" by 6" notecards with any notes (both sides) that you care to bring to the exam.