Graphs and Networks

Cod y Modiwl
MA32410
Teitl y Modiwl
Graphs and Networks
Blwyddyn Academaidd
2026/2027
Semester
Semester 1
Cyd-gysylltydd y Modiwl
Dr Gwion Evans
Rhestr Ddarllen
Gweld ar Aspire
Anghymharus (Unrhyw Flwyddyn Acad)
MT32410
Staff Eraill sy'n Cyfrannu

Dulliau Asesu

Math o Asesiad

Manylion Asesiad

Hyd Asesiad

Cyfran
Arholiad Semester Written Examination: 2 Awr 100%
Arholiad Ailsefyll Written Examination: 2 Awr 100%

Canlyniadau Dysgu

Wedi cwblhau'r modiwl dylai'r myfyrwyr fedru:

  1. Investigate elementary properties of graphs;
  2. Perform simple graph construction;
  3. Represent abstract graphs diagrammatically;
  4. Determine whether a graph satisfies various criteria;
  5. Apply algorithms for finding components;
  6. Describe the algorithms of Dijkstra and Floyd, and to apply them in simple cases;
  7. Apply critical path analysis to simple projects;
  8. Apply either Prim's or Kruskal's algorithm for finding optimum weight spanning trees;
  9. Apply the Ford-Fulkerson algorithm to a transport network to find a maximum flow.

Disgrifiad cryno

Graph theory has developed from research into a number of classical problems - Euler's Konigsberg Bridge Problem, Kirchoff's Electrical Network Problem, Cayley's Enumeration of Chemical Graphs and the Four Colour Problem for Plane Maps. A full solution is found to the Euler Problem and a related problem due to Hamilton is studied. Shortest and longest path algorithms are given with applications, for instance, to job scheduling (PERT). Algorithms are described for finding optimum weight spanning trees inweighted graphs. They can be used, for example, to find least cost connected transport networks. The theory of flows in transport networks is outlined: in paticular the max-flow-min-cut theorem. Two areas of application are traffic flows and matching theory.

Nod

To provide an introduction to some topics in classical graph theory. To describe network algorithms such as those for finding optimum length paths, optimum weight spanning trees and maximum flows and to illustrate them with applications to simple cases.

Cynnwys

1. Elementary graph theory. Special graphs. Simple applications. Associated matrices. Walks and connectivity. Eulerian and Hamiltonian graphs. Trees.
2. Paths and components in graphs. Algorithms to determine components. Shortest (Dijkstra) and longest path algorithms. Floyd's algorithm.
3. Topological sorting. Critical Path Analysis.
4. Spanning trees. Prim's and Kruskal's algorithms for finding optimum weight spanning trees.
5. Transport networks. Flows, cuts. The max-flow-min-cut theorem. The Ford-Fulkerson algorithm.
6. Applications.

Sgiliau Modiwl

Math o Sgiliau

Manylion Sgiliau
Addasrwydd a gwydnwch Students are expected to develop their own approach to time-management and to use the feedback from marked work to support their learning.
Cydlynu ag erail Students will be encouraged to work in groups to solve problems.
Cyfathrebu proffesiynol Students will be expected to submit clearly written solutions to set exercises.
Datrys Problemau Creadigol The assignments will give the students opportunities to show creativity in finding solutions and develop their problem solving skills.
Gallu digidol Use of the internet, Blackboard, and mathematical packages will be encouraged to enhance their understanding of the module content and examples of application
Sgiliau Pwnc-benodol Broadens exposure of students to topics in mathematics, and an area of application that they have not previously encountered.

Nodau

Mae'r modiwl hwn yn cydymffurfio a FfCChC Lefel 6