| TATA64 |
Graph Theory, 6 ECTS credits.
/Grafteori/
For:
CS
D
DAV
IT
Mat
MMAT
U
|
OBS! |
The course is only offered every second year. It will be offered during 2017.
|
| |
Prel. scheduled
hours: 48
Rec. self-study hours: 112
|
| |
Area of Education: Science
Main field of studies: Mathematics, Applied Mathematics
|
| |
Advancement level
(G1, G2, A): A
|
|
Aim:
To give good knowledge of graph theoretical concepts. And to practice
how to use them in mathematics, natural science and computer science.
After completing the course, students should:
- know important classes of problems in graph theory
- be able to formulate and prove fundamental theorems on trees, matchings, connectivity, colorings, plane and hamiltonian graphs
- be able to describe and apply some basic algorithms for graphs
- have a knowledge on elementary Ramsey theory
- be able to use graphs as a tool to model real-life problems
|
|
Prerequisites: (valid for students admitted to programmes within which the course is offered)
Elementary courses in linear algebra and discrete mathematics.
Note: Admission requirements for non-programme students usually also include admission requirements for the programme and threshhold requirements for progression within the programme, or corresponding.
|
|
Organisation:
Lectures and problem sessions.
The course runs over the entire spring semester.
|
|
Course contents:
- Trees: Cayleyâ?Ts formula, spanning trees.
- Connectivity and Mengerâ?Ts theorem,
- Hamilton cycles and colorings of graphs,
- Matchings and coverings, Tutteâ?Ts theorem on perfect matchings, Egervary's algorithm
- Elementary Ramsey theory
- Plane graphs: Eulerâ?Ts formula, the five-color theorem,
- Some applications of graphs in natural science, timetabling and
computer science.
|
|
Course literature:
J.A.Bondy and U.S.R. Murty, Graph theory with applications (available on the internet)
R. Diestel, Graph Theory, 4th ed., 2010 (available on the internet
And some extra material handed out during the course.
|
|
Examination: |
|
Written examination
|
6 ECTS
|
| |
|
|
Course language is English.
Department offering the course: MAI.
Director of Studies: Jesper Thorén
Examiner: Carl Johan Casselgren
Link to the course homepage at the department
Course Syllabus in Swedish
|