Course syllabus - Graph Theory, Networks and applications 7.5 credits
Grafteori, nätverk och tillämpningar
|Valid from:||Autumn semester14|
|Level of education:||Second cycle|
|Main Field(s) of Study:||Mathematics/Applied Mathematics,|
|In-Depth Level:||A1N (Second cycle, has only first-cycle course/s as entry requirements),|
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.
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
- 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
- algorithms for finding matchings in graphs
- vertex- and edge-colouring
- networks and flows
- encodings of graphs and algorithmic aspects of these
Lectures and classes with both individual and group work.
Specific entry requirements
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.
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
Introduction to graph theory
2. ed. : Upper Saddle River, N.J. : Prentice Hall , cop. 2001 -
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
Introduction to graph theory
5. ed. : Harlow : Prentice Hall , 2010 -
ISBN: 9780273728894 (pbk.) LIBRIS-ID: 11887022
viii, 184 s.