ukraine ifo

Faculty of Transportation Sciences

ctu logo

  1. Home
  2. Current Students
  3. Courses
  4. Information about course: Graph Theory

Graph Theory

Course Code:
11Y1TG
Academic Degree:
bachelor
Study Programme:
Technology in Transportation and Telecommunications (B1041A040001)
semesterlanguagestudy field / specialization
4czech flagDOS Transportation Systems and Technology - B-DOS
4czech flagITS Intelligent Transport Systems - B-ITS
4czech flagLED Air Transport - B-LED
4czech flagLOG Logistics and Transport Processes Control - B-LOG
Form of Study:
full-time
Credits:
2
Number of Hours:
2 + 0 hours per week - in full-time study
Type of Course:
elective
Course Completion:
classified credit
Course Tutor:
 
roh  Lectures:
Mgr. Lucie Kárná, Ph.D.
Supervising Department:
Department of Applied Mathematics (16111)
Keywords:
Weighted graph, algorithm, minimum spanning tree, shortest path problem,maximum flow problem, circulation, critical path, bipartite graph.
Abstract:
Basic concepts and terminology of graph theory, graph representation. Problems of graph theory, problem instance. Graph search algorithms, trees, minimum spanning tree, shortest path problem, Eulerian path, bipartite graph matching, flow networks, circulations, critical path method, traveling salesman problem. Problem of existence and optimization and algorithms for their solving. Computational complexity, dealing with NP-complete problems, heuristic approach.
Objectives:
Deeper understanding of graph theory basics. Learning of bacis concepts and problems in the field of algoritmization. Classical problems of graph theory and algorithms for their solving. Introducing to time complexity and efficiency of algorithms.
Course website
http://www.fd.cvut.cz/department/k611/PEDAGOG/K611YTG.htm