Course syllabus - Graph Theory, Networks and applications
Scope
7.5 credits
Course code
MAA600
Valid from
Autumn semester 2024
Education level
Second cycle
Progressive Specialisation
A1N (Second cycle, has only first-cycle course/s as entry requirements).
Main area(s)
Mathematics/Applied Mathematics
School
School of Education, Culture and Communication
Ratified
2014-03-05
Revised
2023-12-12
Literature lists
Course literature is preliminary up to 8 weeks before course start. Course literature can be valid over several semesters.
Objectives
The objective of this course is to present the core concepts and methods of graph theory and to develop, within this context, the student's ability to handle logic, algorithms, modelling, and computations in a meaningful way.
Learning outcomes
Upon completion of the course the student is expected to be able to
- correctly account for the core examples, ideas, and concepts of graph theory
- apply basic graph-theoretical theorems
- apply algorithms for solving certain standard graph-theoretical problems
- state general mathematical problems in graph-theoretical language
- apply standard transformations of graph-theoretical problems to make them more tractable
- apply concepts and methods of graph theory within computer science and information technology
Course content
- simple graphs, multigraphs, pseudographs, and digraphs
- paths, cycles, connectivity, and distance in graphs
- algorithms for the shortest distance in graphs
- trees, bipartite graphs, and other elementary classes of graphs
- matchings
- algorithms for finding matchings in graphs
- vertex- and edge-colouring
- networks and flows
- encodings of graphs and algorithmic aspects of these
Tuition
Lectures and classes with both individual and group work.
Specific requirements
At least totally 120 credits in the engineering, natural sciences, business administration or economics areas of which at least 60 credits within the engineering and natural science area including 30 credits mathematics/applied mathematics in which Basic Vector Algebra, 7.5 credits, and Discrete Mathematics, 7.5 credits, or equivalent is included.
In addition Swedish course 3/Swedish course B and English course 6/English course A are required. For courses given entirely in English exemption is made from the requirement in Swedish course 3/Swedish course B.
Examination
Examination (TEN2), 4 credits, 3, 4 or 5
Project (PRO1), 3,5 credits, 3, 4 or 5
A student who has a certificate from MDU regarding a disability has the opportunity to submit a request for supportive measures during written examinations or other forms of examination, in accordance with the Rules and Regulations for Examinations at First-cycle and Second-cycle Level at Mälardalen University (2020/1655). It is the examiner who takes decisions on any supportive measures, based on what kind of certificate is issued, and in that case which measures are to be applied.
Suspicions of attempting to deceive in examinations (cheating) are reported to the Vice-Chancellor, in accordance with the Higher Education Ordinance, and are examined by the University’s Disciplinary Board. If the Disciplinary Board considers the student to be guilty of a disciplinary offence, the Board will take a decision on disciplinary action, which will be a warning or suspension.
Grade
Pass with distinction, Pass with credit, Pass, Fail