MATH 454-001 Graph Theory and Applications/Math 553-001 Discrete Applied Mathematics I (Ellis)

Skip down to homework assignments
Instructor: Robert Ellis Office: E1 Bldg, Rm 105C Email:

Lectures

 TR 11:25am-12:40pm E1 Bldg. 106

Office Hours

 MW 11am-4:15pm, Walk-in
TR 1:50-4:30pm, By appointment		 Office phone 567-5336

Textbook

 West, Introduction to Graph Theory, 2nd edition, Prentice Hall

Exam Schedule

 Exam 1: R Oct 22 454Key 553Key
Exam 2: T Nov 24 joint key
Final: R Dec 10, 10:30am-12:30pm		 Exams 1 & 2 will cover material including all returned homework to date

First day handout (pdf) (course contract & exam schedule).
Department course syllabus. Math 454, Math 553.
Concept map, Graphs: What is the definition of a graph? (Created using IHMC CmapTools)
Concept map, Walks: What are the kinds of walks in a graph? (Created using IHMC CmapTools)

Sample exams from Fall 2005: Exam 1, Exam 2, Final Exam

Supplemental Reading (books at Galvin Library)

For alternative points of view and for additional applications:
Graphs and Applications: An Introductory Approach, J.M.Aldous R.J.Wilson
Applied Combinatorics, F.R.Roberts
Applied Combinatorics, A.Tucker
Graph Theory, R.Diestel
Graph Theory Applications, L.R.Foulds
Topics in Intersection Graph Theory, T.A.McKee F.R.McMorris
Graph Theory and Applications, Marshall
Bipartite Graphs and their Applications, A.S.Asratian, T.MJ Denley, R.Haggkvist

 

Homework Due Dates

Due Date Math 454 Assignment Math 553 Assignment
R 8/27 Review handout of example notes for first part of Section 1.1 before lecture.
T 9/1 Review 2nd handout of example notes, and fill in the blank examples, before lecture. This is the last notebook entry that will be modeled for you.
R 9/3 Complete notebook entry for pages 19-26 before lecture.
R 9/3, 5pm
Mailbox in E1 210 		HW 1. Section 1.1: 10, 12, 14, 18 (give the isomorphism); pick one of 26, 27; pick one of 35, 38. HW 1. Section 1.1: 14, 18; pick one of 26, 27; pick one of 31, 34; pick one of 35, 38; 47
R 9/10 Complete notebook entry for pages 26-30 and 34-38 up to Conjecture 1.3.12 before lecture.
T 9/15 Complete notebook entry for pages 38-47 before lecture.
"Determine," "Show," etc. mean write a proof.
T 9/15, 5pm
Mailbox in E1 210 		HW 2. Section 1.2: 3, 15; 17 or 18; 20 or 22, 25 or 26, 38 or 40 HW 2. Section 1.2: 17 or 18; 20 or 22; 25 or 26; 38 or 40
R 9/24, 5pm
Mailbox in E1 210 		HW 3. Section 1.2: 8, 10
Section 1.3: 3, 7, 8, 12, 17, 26 or 32, 40 or 41 		HW 3. Section 1.2: 36 or 43 (see errata for corrected problem statements)
Section 1.3: 12, 16 or 29, 26 or 32, 40 or 41
R 9/24 Complete notebook entry for pages 53-58 before lecture.
T 9/29 Complete notebook entry for pages 59-63 before lecture.
R 10/1 Complete notebook entry for these pages before lecture.
Math 454: pp.67-73
Math 553: pp.67-75
F 10/2, 5pm
Mailbox in E1 210 		HW 4. Section 1.3: 57 or 63
Section 1.4: 4, 5, 10 or 11, 19 or 20, 36 or 37 		HW 4. Section 1.3: 57 or 63
Section 1.4: 10 or 11, 14 or 25, 19 or 20, 36 or 37; choose one of 16 or 30 or 35
R 10/8 Complete notebook entry for these pages before lecture.
Math 454: pp.81-88
Math 553: pp.81-91
T 10/13, 5pm
Mailbox in E1 210 		HW 5. Section 2.1: 2, 17 or 18, 29, 35 or 36, 47, 62 or 64 HW 5. Section 2.1: 17 or 18, 29, 35 or 36, 47, 62 or 64, 72
T 10/13 Complete notebook entry for these pages before lecture.
Math 454: pp.95-96
Math 553: pp.95-96
R 10/15 Complete notebook entry for these pages before lecture.
Math 454: pp.97-100 and 107-113
Math 553: pp.97-103 and 107-113
T 10/20, 5pm
Mailbox in E1 210 		HW 6. Section 2.2: 6, 7, 15, 17, 24
Section 2.3: 2, 10 		HW 6. Section 2.2: 6, 7, 15, 17, 19 or 20, 28 or 29, 34
Section 2.3: 10
T 10/27 Complete notebook entry for these pages before lecture.
Math 454: pp.113-115
Math 553: pp.113-118
R 10/29 Complete notebook entry for these pages before lecture.
Math 454: pp.123-129
Math 553: pp.123-134
R 10/29, 5pm
Mailbox in E1 210 		HW 7. Section 2.3: 3, 13 or 14, 15, 18
(Reminder: we discussed a detailed reason behind 13 in lecture.)
Section 3.1: 3, 8 		HW 7. Section 2.3: 13 or 14, 15, 17, 19, 26, 28
Section 3.1: 3, 8
T 11/3 Complete notebook entry for these pages before lecture.
Math 454: pp.136-140
Math 553: pp.136-145
R 11/5 Complete notebook entry for these pages before lecture.
Math 454: pp.149-156
Math 553: pp.149-157
R 11/5
In class		 Exam 1 rewrite due.
See email for rules.
R 11/5, 5pm
Mailbox in E1 210 		HW 8. Section 3.1: 9, 16, 19, 21, 32
Section 3.2: 2, 5 		HW 8. Section 3.1: 19, 24, 32, 43, 48, 49
Section 3.2: 4, 6, 7
  You should be able to trace through the Hungarian or Augmenting Path Algorithm on an exam (see slides link below).
F 11/6, 5pm
Mailbox in E1 210		 Homework amnesty deadline.
See email for rules.
R 11/12 Read the rest of Section 4.1, and read Section 4.2 through p.164.
T 11/17 Complete notebook entry for these pages before lecture.
Math 454: pp.161-170
Math 553: pp.161-172
T 11/17, 5pm
Mailbox in E1 210 		HW 9. Section 3.3: 2, 4, 6, 10, 22
Section 4.1: 1, 4, 8
Also prove the following: the hypercube Qk has connectivity k. 		HW 9. Section 3.3: 6, 7, 8, 12, 22
Section 4.1: 8, 10
Also prove the following: the hypercube Qk has connectivity k.
R 11/19 Complete notebook entry for these pages before lecture.
Math 454: pp.176-184
Math 553: pp.176-187
F 12/4, 5pm
Mailbox in E1 210 		HW 10. Section 4.1: 20, 27, 30
Section 4.2: 2, 3, 6
Section 4.3: 1, 2, 3		 HW 10. Section 4.1: 20, 27, 34
Section 4.2: 2, 6, 11 or 23
Section 4.3: 3, 5 or 10, 13
Due Date Math 454 Assignment Math 553 Assignment

Show work for full credit on homework. Words like "determine" and "show" mean give a proof. Sometimes a proof is an example (for an existence statement) and a disproof is a counterexample (for a universal statement).

Topics for additional investigation (in rough order from lecture)

Ramsey numbers and Ramsey's Theorem Wikipedia, MathWorld
The matching problem Wikipedia, MathWorld
The graph coloring problem Wikipedia, MathWorld (vertex coloring)
The Shortest-Path Problem Wikipedia
Real-time traffic congestion maps for the Gary/Chicago/Milwaukee Transportation Corridor; UIC's AI Lab works on traffic problems
The original solution to the Konigsberg bridge problem by Euler.
(Challenging) The computational complexity class #P, and a proof that counting the number of Eulerian circuits in a graph is #P-complete.
A de Bruijn cycle applet for many lengths and radices (binary, ternary, etc.)
Demo applet for Kruskal's Algorithm for finding a minimum spanning tree of a graph (by Kenji Ikeda).
Demo applet for Dijkstra's Algorithm for finding a shortest u,v-path for fixed u and arbitrary v (by Kenji Ikeda).
Example from 10/28 lecture of the Augmenting Path Algorithm for maximum matching/minimum vertex cover, and of the Hungarian Algorithm for maximum weighted matching/minimum weighted cover.

Lecture materials for final lecture on Tuesday 12/1:
    See Blackboard->Course Documents for slides on 4.1 and 4.2 through Menger's Theorem.
    See Max Flow/Min Cut slides, by Kevin Wayne, for an intuitive alternative to Section 4.3.
    See a demo on the Ford-Fulkerson Algorithm, Kevin Wayne, for finding a maximum flow in a network.
    See a wealth of applications of Network Flow, Kevin Wayne, to see how it generalizes Menger's Theorem, the Konig-Egervary Theorem, and solves a broad class of interesting applications.

page maintained by Robert Ellis / http://math.iit.edu/~rellis/