# MATH20150 Graphs and Networks

This is a core course that prepares for essentials needed in various fields of Discrete Mathematics and Computer Science. It aims to cover basic concepts and results in graph theory and the theory of network flows.

Show/hide contentOpenClose All

Curricular information is subject to change

Learning Outcomes:

After successful completion of the course, a student should:1. be able to determine whether or not certain sequences belong to simple graphs;2. be able to construct a graph, given a graphic sequence;3. be able to perform simple mutations of a graph, such as constructing its subgraphs, its complement and its dual where one exists;4. know basic results about acyclic graphs (trees)5. be able to compute minimal weight spanning trees (Prim & Kruskal algorithms);6. be able to identify Eulerian graphs and find Euler circuits (Fleury's algorithm);7. know some necessary and suffcient conditions for a graph to be Hamiltonian and be able to apply these to arbitrary graphs;8. be familar with Euler's polyhedral formula and apply it to establish non-planarity;9. be able to determine isomorphisms for small graphs;10. be familiar with the min-cut max flow theorem;11. be able to apply the Ford-Fulkersen algorithm for the construction of a maximal flow.

Student Effort Hours:
Student Effort Type Hours
Specified Learning Activities

24

Autonomous Student Learning

50

Lectures

18

Tutorial

12

Total

104

Approaches to Teaching and Learning:
Lectures, tutorials, enquiry and problem-based learning.
Requirements, Exclusions and Recommendations
Learning Requirements:

Basic Discrete Mathematics and Combinatorics

Module Requisites and Incompatibles
Equivalents:
Graphs and Networks (MATH27150)

Assessment Strategy
Description Timing Open Book Exam Component Scale Must Pass Component % of Final Grade In Module Component Repeat Offered
Examination: End of trimester exam. 2 hour End of Trimester Exam No Standard conversion grade scale 40% No

70

No
Examination: Midterm exam. The timing of the midterm can be slightly changed in order to accommodate as many people as possible. Week 7 No Standard conversion grade scale 40% No

30

No

Carry forward of passed components
No

Resit In Terminal Exam
Spring Yes - 2 Hour