## 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]

### Tutorial material

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

### Lecture notes

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

### Assessment

- 30% midterm
- 70% final exam

The following

grading scheme will be applied to your final mark.