Course syllabus - Graph Theory, Networks and applications 7.5 credits

Grafteori, nätverk och tillämpningar

Course code: MAA600
Valid from: Autumn semester14
Level of education: Second cycle
Subject: Mathematics
Main Field(s) of Study: Mathematics/Applied Mathematics,
In-Depth Level: A1N (Second cycle, has only first-cycle course/s as entry requirements),
School: UKK
Ratification date: 2014-03-05

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

Teaching methods

Lectures and classes with both individual and group work.

Specific entry requirements

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 MDH 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 (2016/0601). 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.

Rules and regulations for examinations

Marks

TK

Enviromental aspects

Environmental aspects have been considered but do not form part of the learning objectives of the course.
 

Course literature is preliminary until 3 weeks before the course starts. Literature may be valid over several terms.

Valid from: Autumn semester14

Decision date: 2014-08-08

Last update: 2014-08-25

Books

West, Douglas Brent;

Introduction to graph theory

ISBN: 0-13-014400-2 LIBRIS-ID: 4548461

xix, 588 s.

Valid from: Autumn semester15

Decision date: 2015-06-23

Last update: 2015-06-23

Books

Wilson, Robin J.;

Introduction to graph theory

ISBN: 9780273728894 (pbk.) LIBRIS-ID: 11887022

viii, 184 s.