Study Guide@lith   Link to LiU Homepage
 

Linköping Institute of Technology

Search

 Link to LiU Homepage
 
Valid for year : 2013
 
TATA64 Graph Theory, 6 ECTS credits.
/Grafteori/

For:   CS   D   DAV   IT   MMAT  


OBS!
The course is only offered every second year. It will be offered during 2013.
 

Prel. scheduled hours: 36
Rec. self-study hours: 124

  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 and Edmondsâ?Ts algorithm for isomorphism of 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, 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 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: Göran Forsling
Examiner: Armen Asratian
Link to the course homepage at the department


Course Syllabus in Swedish

Linköping Institute of Technology
Link to top of pagep


Contact: TFK , val@tfk.liu.se
Last updated: 01/24/2013