[ATG] Algorithmic Graph Theory

BCKIS

[ATG] Algorithmic Graph Theory

Main objectives of the course:

To make students acquainted with essential optimizing graph theory algorithms. To teach student to write computer codes for some graph algorithms.

The course information sheet
Course information sheet
University: University of Žilina
Faculty: Faculty of Management Science and Informatics
Course ID: 5BA126Course name: Algorithmic Graph Theory (ATG)
Form, extent and method of teaching activities:
Number of classes per week in the form of lectures,
laboratory exercises, seminars or clinical practice		Lectures: 2.0 Seminars: 0.0 Lab.exercises: 2.0
Methods by which the educational activity is deliveredPresent form of education
Applied educational activities and methods suitable for achieving learning outcomes
Number of credits: 5.0
Study workload: hours
Specification of the study workload:
Recommended term of study: 2. year, summer semester
Study degree: 1.
Required subsidiary courses:
Prerequisites:

Co-requisites:
Course requirements:
Continuous assessment / evaluation:
40% = 40 points
Final assessment /evaluation:
60% = 60 points
To enroll for an exam student must have 20 points.
Course outcomes:
To make students acquainted with essential optimizing graph theory algorithms. To teach student to write computer codes for some graph algorithms.
Course scheme:
Lectures:
1. Essentiall notions of graph theory. Fundamentals of combinatorics. Representation of graphs.
2. Paths in graphs, connectivity of graphs. Tarry's algorithm.
3. Algorithms, computational complexity and NP-hard problems. Polynomial reduction of problems.
4. Shortest path in graph and in digraph. Shortest paths algorithms. Identification of negative cycles.
5. Trees, spanning tree, minimum (or maximum) weighted spanning tree in a graph - Kruskal's algorithm. Application for searching a path having maximum capacity. Breadth-first search and Depth-first search.
6. Acyclic digraphs. Monotone numbering of acyclic graph. Project planning - CPM method.
7. Flows in networks. Ford-Fulkerson algorithm for maximum flow in a network.
8. Minimum cost maximum flow.
9. Eulerian tour. Matchings in graphs. Chinese postman problem. Edmonds algorithms.
10. Travelling postman problem - TSP. Suboptimal algorithms for TSP.
11. Medians and centers. Cliques, independent sets, covering sets in graphs. Allocation problems.
12. Planar graphs. Graph coloring problem.

Laboratory work:

1. Repetition of fundamentals of combinatorics and binary relations.
2 Computational complexity an polynomial reduction of problems.
3. Graph connectivity and Tarry's algorithm.
4. Shortest paths algorithms.
5. Kruskal's algorithm and paht with maximum capacity.
6. Acyclic digraphs. Monoton numbering. Project planning - CPM method.
7. Ford-Fulkerson algorithms for maximum flow.
8. Minimum cost maximum flow ina networki.
9. Algorithmsfor eulerina tour. Edmonds's algorithms for Chinese postman problem.
10. Heuristics for travelling salesman problem.
11. Allocation problems, independent sets and cliques.
12. Algorithms for graph coloring problem.
Literature:
Palúch, S.: Teória grafov, EDIS, Žilina, ISBN 80-7100-874-5 (dostupné aj na http://frcatel.fri.uniza.sk/users/paluch/ resp. http://frcatel.fri.uniza.sk/users/paluch/grafy-ps.zip )
Plesník, J.: Grafové algoritmy, VEDA, SAV Bratislava 1983
Evans, J.,R., Minieka, E.: Optimizarion Algorithms for Networks and Graphs, Marcel Decker, New Yourk, second edition 1992, ISBN 0-8247-8602-5
Gross,J., Yellen, J.: Graph Theory and its Applications, CRC Press, 1998, ISBN 0-8493-3982-0
Instruction language: slovak/english
Notes:
Course evaluation::
Total number of evaluated students: 173
ABCDEFX
34.10 % 9.25 %21.39 %11.56 %19.08 % 4.62 %
ABCDEFX
34.10 % 9.25 %21.39 %11.56 %19.08 % 4.62 %
Course teachers:
Last updated: 2021-08-25 06:20:00.000
The person responsible for the course: Ing. Tomáš Majer, PhD.
Approved by:
SOURCE: https://vzdelavanie.uniza.sk/vzdelavanie/planinfo.php?kod=274633&lng=en