MATH20150 Graphs and Networks

Academic Year 2020/2021

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 compute the Pruefer sequence of a labelled tree;7. be able to identify Eulerian graphs and find Euler circuits (Fleury's algorithm);8. know some necessary and suffcient conditions for a graph to be Hamiltonian and be able to apply these to arbitrary graphs;9. be familar with Euler's polyhedral formula and apply it to establish non-planarity;10. be able to determine isomorphisms for small graphs;11. be familiar with the min-cut max flow theorem;12. be able to apply the Ford-Fulkersen algorithm for the construction of a maximal flow.

Student Effort Hours: 
Student Effort Type Hours
Lectures

18

Small Group

6

Tutorial

12

Specified Learning Activities

24

Autonomous Student Learning

50

Total

110

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
Continuous Assessment: About 4 short exams during the semester (this number could vary slightly). Ideally evenly spaced, with the final one in the final week, and a bit longer (probably one hour). Unspecified n/a Standard conversion grade scale 40% No

100


Carry forward of passed components
No
 
Resit In Terminal Exam
Spring Yes - 2 Hour
Please see Student Jargon Buster for more information about remediation types and timing. 
Feedback Strategy/Strategies

• Group/class feedback, post-assessment

How will my Feedback be Delivered?

Not yet recorded.

Name Role
Dr Carl Bracken Lecturer / Co-Lecturer