Course syllabus - Graph Theory, Networks and Applications

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

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

Grading scale: 5, 4, 3