MATH20150: Graphs and Networks     Semester 1, 2014/15

Dr Masha Vlasenko

G12 Science North, School of Mathematical Sciences
Belfield Office Park

Lectures: Tuesday 4pm and Thursday 3pm in Theatre N ART

This course teaches essentials needed in various fields of discrete mathematics and computer science. It covers basic concepts and results in graph theory and the theory of network flows.

FINAL EXAM took place on Monday, December 15. [paper] [solutions]

MIDTERM EXAM took place on Thursday, October 16. [paper] [solutions] [q. 2 b,c,d solutions]
[RESULTS]

Tutorial material

Tutorials take place at 1pm on Monday (room A105 ART) and 11am on Wednesday (room S1.67 SCS).

Lecture notes

  1. The Handshaking Lemma and other properties of degrees [1]
  2. The Havel-Hakimi algorithm and realization problem [1][2]
  3. Connectivity, adjacence and incidence matrices [1][2][3][4]
  4. Basic properties of trees [1][2]
  5. Degree sequence of a tree [1]
  6. Spanning trees [1]
  7. Minimal weight spanning trees and greedy algorithms [1][2]
  8. Eulerian cycles and paths [1]
  9. Hamiltonian cycles and paths [1][2]
  10. Graph isomorphism and symmetry [1][2]
  11. Planar graphs [1][2][3]
  12. Networks and flows [1][2]
  13. Min-cut max-flow theorem [1][2]
  14. Ford-Fulkerson algorithm [1][2]

Assessment

The following grading scheme will be applied to your final mark.