MT4514 Graph Theory

Academic year

2024 to 2025 Semester 1

Further information on which modules are specific to your programme.

Key module information

SCOTCAT credits

15

The Scottish Credit Accumulation and Transfer (SCOTCAT) system allows credits gained in Scotland to be transferred between institutions. The number of credits associated with a module gives an indication of the amount of learning effort required by the learner. European Credit Transfer System (ECTS) credits are half the value of SCOTCAT credits.

SCQF level

SCQF level 10

The Scottish Credit and Qualifications Framework (SCQF) provides an indication of the complexity of award qualifications and associated learning and operates on an ascending numeric scale from Levels 1-12 with SCQF Level 10 equating to a Scottish undergraduate Honours degree.

Availability restrictions

Not automatically available to General Degree students

Planned timetable

10.00 am Mon (even weeks), Tue and Thu

This information is given as indicative. Timetable may change at short notice depending on room availability.

Module coordinator

Dr S Huczynska

Dr S Huczynska
This information is given as indicative. Staff involved in a module may change at short notice depending on availability and circumstances.

Module description

The aim of this module is to introduce students to the study of graph theory as a tool for representing connections between data. Topics to be covered may include: basic theory and applications, Eulerian graphs, Hamiltonian graphs, planar graphs, spanning trees and applications, networks, matching problems.

Relationship to other modules

Pre-requisites

BEFORE TAKING THIS MODULE YOU MUST PASS MT1003 OR PASS MT2504

Assessment pattern

2-hour Written Examination = 100%

Re-assessment

Oral examination = 100%

Learning and teaching methods and delivery

Weekly contact

2.5 lectures (x 10 weeks) and 1 tutorial (x 10 weeks).

Intended learning outcomes

  • Understand and be able to use the formal definition of a graph and basic notions such as graph isomorphism, adjacency matrix, subgraphs and minors
  • Be familiar with and able to work with the concept of connectivity and paths in graphs; be able to establish results about Eulerian tours and Hamiltonian cycles
  • Know how to characterize trees and use appropriate proof techniques (e.g. induction) to establish results about them
  • Be familiar with the concept of planarity and questions of graph colouring and to prove results about them; be able to calculate the chromatic polynomial of a graph
  • Be familiar with the concept of planarity and questions of graph colouring and to prove results about them; be able to calculate the chromatic polynomial of a graph
  • Appreciate the idea that a sufficiently large graph cannot avoid possessing certain structure; apply Ramsey Theory to small examples