Objectives and competences
Objectives:
Students master the basic concepts of graph theory, understand the problems of solving in combinatorial optimization, know classical combinatorial optimization problems and algorithms for finding solutions, perform algorithms step-by-step and acquire skills in modelling certain practical problems using graph theory.
Competencies:
Students can model and solve specific practical problems using graph theory. They understand the basics of algorithms and can derive algorithm steps on a specific example.
Content (Syllabus outline)
Basic graph theory
graphs, digraphs, weighted graphs, networks, applications of graphs and digraphs, isomorphic graphs, cllases of graphs, list of small graphs, connected graph, planar graph, regular graph, bipartite graph, adjacancy matrix and incidence matrix, trees, spanning trees, walks and closed walks in graphs, Eulerian and Hamiltonian graphs, Eulerian trail, Hamiltonian cycle, vertex and edge colourings, totally colouring, chromatic number, chromatic index.
Combinatorial optimization
algorithms, efficiency of algorithms, graph searching, deapt-first search, breadht-first search, DFS and BFS tree, shortest path algorithm, Dijkstra's algorithm, long path algorithm, optimization of project, minimal spaning tree problem, Prime's algorithm, Eulerian and Hamiltonian problems, Fleury's algorithm, Chinese postman problem, travelling salesman problem, greedy algorithm, practical use of graph colouring (scheduling, traffic flows, storing).
Learning and teaching methods
Lectures, discussion and computer exercises.
Intended learning outcomes - knowledge and understanding
After completing this course, students will be able to:
- explain basic terms of graph theory and problems of finding solution of combinatorial optimizations problems,
- recognize and analyse classical combinatorial optimization problems,
- perform algorithms step-by-step and use computer software,
- find the shortest and the longest path in graphs and digraphs,
- find the minimal spanning tree,
- find Eulerian trail and determine bounds for Hamiltonian cycle,
- find a solution to the Chinese postman problem and the travelling salesman problem,
- colour graph using the greedy algorithm and determine bounds of chromatic number and chromatic index of graphs,
- construct model of some practical problems and solve them using graph theory.
Intended learning outcomes - transferable/key skills and other attributes
To model some traffic problems using graph theory and to find the solutions using discussed algorithms.
Readings
• Wilson, R. J., & Watkins, J. J. (1997). Uvod v teorijo grafov (Let. 63, str. 397). Društvo matematikov, fizikov in astronomov Slovenije. https://plus.cobiss.net/cobiss/adz/sl/bib/72250368
• Žerovnik, J. (2005). Osnove teorije grafov in diskretne optimizacije (2. popravljena izd., str. 173). Fakulteta za strojništvo. https://plus.cobiss.net/cobiss/adz/sl/bib/54389249
• Aldous, J. M., & Wilson, R. J. (2006). Graphs and applications: an introductory approach (5th print. 2006, str. XI, 444). Springer. https://plus.cobiss.net/cobiss/adz/sl/bib/11038486
• Hillier, F. S., & Lieberman, G. J. (2021). Introduction to operations research (11th ed., str. XVII, 964). McGraw Hill. https://plus.cobiss.net/cobiss/adz/sl/bib/180409091
Additional information on implementation and assessment Note 1: The computational exam can be replaced by two midterm exams.
Note 2: To pass the course, you must achieve at least 60 % on the calculation exam and at least 50 % on the theoretical exam.
