Objectives and competences
The objectives of this course are: to know basic terms of graph theory, to understand problems of finding solutions, to know classical combinatorial optimization problems and perform steps for finding solutions, to perform algorithms step-by-step, to use computer software, and to acquire the basic ideas of modelling of some practical problems using graph theory.
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, connectivity, planarity, 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), use computer software .
Learning and teaching methods
Lectures, discussion and exercises with use of computer software..
Intended learning outcomes - knowledge and understanding
Knowledge and Understanding:
On completion of this course the student 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,
- 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
R. J. Wilson, J. J. Watkins, Uvod v teorijo grafov, DMFA Slovenije, Ljubljana, 1997.
J. Žerovnik, Osnove teorije grafov in diskretne optimzacije, 2. popravljena izdaja, FS UM, Maribor, 2005.
J. M. Aldous, R. J. Wilson, Graphs and applications: an Introductory approach, Springer, 5th printing, London, 2006.
L. R: Foulds, Graph theory Application, Springer, New York, 1992.
F. S. Hillier, G. J. Lieberman, Introduction to Operation Research, Ninth Edition, McGraw-Hill, New York, 2009.
Prerequisits
Prerequisites for enrolling in the course: none.
Prerequisite for taking the oral exam is scoring at least 60% on written exam and completed individual homeworks.
Additional information on implementation and assessment Note: prerequisite for taking the oral exam is scoring at least 60% on written exam and completed individual homeworks.
