| CODE | MAT2413 | ||||||||
| TITLE | Introduction to Graph Theory with Applications | ||||||||
| UM LEVEL | 02 - Years 2, 3 in Modular Undergraduate Course | ||||||||
| MQF LEVEL | 5 | ||||||||
| ECTS CREDITS | 4 | ||||||||
| DEPARTMENT | Mathematics | ||||||||
| DESCRIPTION | (A) Theory: - Introductory concept: vertices, edges, paths, cycles, connectedness and special classes of graphs, such as complete graphs and bipartite graphs. The maximum and minimum number of edges in a connected graph on a given number of vertices. - Simple examples of the relation between the spectrum of a graph and its structure. - Trees. Equivalent definitions of trees. - Connectivity and Menger's Theorem. - Bipartite graphs seen as the easiet instance of graph colouring, namely the 2-colourable graphs. Characterisation in terms of not having odd cycles and edge-set partitioned into cutsets. - Eulerian graphs. Equivalent characterisations. Also, characterisations in terms of no odd cutsets and edge-set partitioned into cycles. - Hamiltonian graphs. Ore's Theorem. - Chromatic number of a graph. Brook's Theorem for graphs which are not regular. - Planarity. Euler's polyhedral formula. Non-planarity of K_5 and K_{3,3}. Kuratowski's Theorem (without proof). - The Five Colour Theorem for planar graphs. (B) Applications: - A brief look at ranking players in a tournament or web-pages. - Kruskal's Algorithm for finding a minimum weight spanning tree. Brief introduction to the greedy algorithm on matroids. - A brief look at trees as data-structures. - Dijkstra's Algorithm. - Activity networks. - The difficulties of scheduling. - Introduction to the Travelling Salesman Problem. Connection with scheduling and a brief discussion of computationally hard problems. The twice-around-the-spanning-tree heuristic. - Flow networks. The Minimum-Cut-Maximum-Flow Theorem. Application: Proof of Menger's Theorem Study-unit Aims - The aim of this unit is to give students a first taste of graph theory both from the pure and the applied side. For those students majoring in Mathematics, this course will link with other combinatorial courses they would have studied as well as others which they would be taking in the third and fourth years. It will also show them that the seemingly abstract mathematics they are studying has applications in the real world. - Other students doing IT or Statistics and Operations Research will recognise that the graphs in this course and the methods to solve questions about them are closely related to the data structures and algorithms they encounter in their courses. - For students in the Faculty of Education this course is an opportunity for them to see how non-trivial mathematical problems often have a game-like origin, and maybe this could help them devise innovative topics in the classes they would be teaching. Learning Outcomes 1. Knowledge & Understanding: By the end of the study-unit the student will be able to: 1. Understand what a graph is, what type of questions are asked by graph theorists, and be prepared for the more advanced courses they would meet in the second and third year. 2. See graphs within the wider context of combinatorial optimisation. 2. Skills: By the end of the study-unit the student will be able to: 1. Understand and produce simple proofs about the property of graphs. 2. Understand some elementary algorithmic concepts particularly in combinatorial optimisation and learn some ways in which computationally intractible problems are solved heuristically. Main Text/s and any supplementary readings - Course notes will be handed out for most of the topics. - Graph Theory with Applications by A.J. Bondy and U.S.R. Murty (available with permission online at Professor Bondy's website: http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html) - Schaum's Outline of Graph Theory, by V.K. Balakrishnan. |
||||||||
| ADDITIONAL NOTES | Pre-requisite Study-unit: MAT1411 | ||||||||
| STUDY-UNIT TYPE | Lecture and Independent Study | ||||||||
| METHOD OF ASSESSMENT |
|
||||||||
| LECTURER/S | Josef Lauri |
||||||||
|
The University makes every effort to ensure that the published Courses Plans, Programmes of Study and Study-Unit information are complete and up-to-date at the time of publication. The University reserves the right to make changes in case errors are detected after publication.
The availability of optional units may be subject to timetabling constraints. Units not attracting a sufficient number of registrations may be withdrawn without notice. It should be noted that all the information in the description above applies to study-units available during the academic year 2024/5. It may be subject to change in subsequent years. |
|||||||||