SLO | EN

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.

  • doc. dr. RIJA ERVEŠ, prof. mat. in fiz.

  • Written examination: 70
  • Oral examination: 30

  • : 45
  • : 15
  • : 15
  • : 105

  • Slovenian
  • Slovenian

  • TRAFFIC AND TRANSPORTATION ENGINEERING - 1st