Students will be introduced to the definition of a graph as a data structure, its efficient representation in the computer, and various special types of graphs. Through well-known problems with graphs and algorithms for their solution, students will become familiar, at the conceptual level, with and also practically implement some of the algorithms and thus learn how to use a graph data structure to model the actual physical problems.

Conditions for enrollment

The necessary requirements to enrol in the second year of the studies.

Course description

Introduction and basic terms. A mathematical definition of the graph and examples. Types of graphs. An efficient way to store graphs in the computer. Rarely filled graphs. The problem of graph traversal. BFS and DFS algorithms. The problem of node connectivity in a graph. An algorithm for finding strongly connected components in a graph. The problem of the Euler cycle. The smallest spanning tree problem. The shortest path problem. The Bellman-Ford and the Dijkstra algorithm. NP-complex graph problems. The graph colouring problem. The travelling salesman problem. Network definition. The maximum flow problem in the network.

Student requirements

Defined by the Student evaluation criteria of the Faculty of Electrical Engineering, Computer Science and Information Technology Osijek and paragraph 1.9

Monitoring of students

Defined by the Student evaluation criteria of the Faculty of Electrical Engineering, Computer Science and Information Technology Osijek and paragraph 1.9

Obligatory literature

1. 1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford Introduction to Algorithms (3rd ed.) MIT Press and McGraw-Hill. ISBN 0-262-03384-4. (2009) [1990]

Pretraži literaturu na:

1. 1 R. Sedgewick Algorithms in C++ Part 5: Graph Algorithms (3rd Edition) Addison-Wesley Professional, 2002.

2. 2 Shimon Even Graph Algorithms Cambridge University Press, 2011, ISBN: 1139504150, 9781139504157

Conducting university questionnaires on teachers (student-teacher relationship, transparency of assessment criteria, motivation for teaching, teaching clarity, etc.). Conducting Faculty surveys on courses (upon passing the exam, student self-assessment of the adopted learning outcomes and student workload in relation to the number of ECTS credits allocated to activities and courses as a whole).

Overview of course assesment

1. describe a graph data structure and some known graph problems and graph algorithms

2. identify the graph structure in modelling many known problems and use it to solve these problems

3. perform complexity analysis for known graph algorithms

4. implement and use different algorithms for problems such as the shortest path, an Euler cycle, and the like

5. apply the acquired knowledge in designing software support where it is necesary to use graphs

Aktivnosti studenta: Vidi tablicu aktivnosti