| TATA64 | Graph Theory, 6 ECTS credits. /Grafteori/ |
||
OBS! |
The course is only offered every second year. It will be offered during 2011. |
||
Prel. scheduled
hours: 36 |
|||
|
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 smester. |
|||
| Course contents: Trees: Cayleyâ?Ts formula, spanning trees and Edmondsâ?Ts algorithm for isomorphism Connectivity and Mengerâ?Ts theorem, blocks 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, Grinbergâ?Ts formula Some applications of graphs in natural science, timetabling and computer science. |
|||
| Course literature: J.A.Bondy and U.S.R. Murty, Graph theory 2008. |
|||
| Examination: | |||
| Written examination |
6 ECTS |
||
Course language is English. Department offering the course: MAI. Director of Studies: Ulf Janfalk Examiner: Armen Asratian Course Syllabus in Swedish |
|||
|
|
 |
|||||
| ||||||