The course treats graph theoretical concepts and problems, both theoretically and in applications. In the course, the basic theory of different types of graphs is given in detail, especially for trees and bipartite graphs. In the course is also presented some of the algorithms that partially or completely solve certain graph theoretical problems. Examples of such problems are finding a maximum weight matching, and finding a maximal flow in a network. The theory of matchings and Hall's theorem are treated, together with spanning trees and Menger's theorem. Furthermore, the theory of vertex and edge colorings is treated, including Brooks' theorem and Vizing's theorem. The course concludes with an introduction to matroid theory.
The course requires courses in Mathematics, minimum 60 ECTS or at least two years of university studies and in both cases a course in discrete mathematics, minimum 7,5 ECTS or equivalent. Proficiency in English equivalent to the level required for basic eligibility for higher studies. Where the language of instruction is Swedish, applicants must prove proficiency in Swedish to the level required for basic eligibility for higher studies
Guaranteed place
Applicants in some programs at Umeå University have guaranteed admission to this course. The number of places for a single course may therefore be limited.
Application code
UMU-58119
Application
Application deadline was
15 October 2024.
The application period is closed.
Application and tuition fees
As a citizen of a country outside the European Union (EU), the European Economic Area (EEA) or Switzerland, you are required to pay application and tuition fees for studies at Umeå University.
