|
Lecturer(s)
|
-
Večerka Arnošt, RNDr.
-
Bělohlávek Radim, prof. RNDr. Ph.D., DSc.
-
Osička Petr, Mgr. Ph.D.
|
|
Course content
|
<ol> <li>Basic terms, graph definition, basic types of graphs. <li>Operations on graphs (union, intersection etc.), graph isomorphism, <li>Walk, tour, path, connectivity of undirected and directed graphs, condensation of a directed graph. <li>Various graph representations, incidence matrix, adjacency matrix, relation between the matrices; graph representation suitable for implementation. <li>Depth-first graph search algorithm and breadth-first graph search algorithm. <li>Significant node sets in a graph, independent and dominating subsets of nodes, cliques in a graph; heuristic algorithms for computing of these sets. <li>Graph colouring and the chromatic number of a graph, basic theorems about chromatic numbers; heuristic algorithms for graph colouring. <li>Spanning trees, Kruskal?s algorithms for computing of the minimum spanning tree. <li>Cycles in a graph. Fundamental set of cycles and its computing. <li>Distances in a graph. Algorithms for computing the shortest path in graph. <li>Eulerian graph and Hamiltonian graph. Traveling salesman problem. <li>Matching. Usage of matching for solving Chinese postman problem. <li>Planar graphs, necessary and sufficient conditions for graph planarity, algorithm for planar graph drawing. </ol>
|
|
Learning activities and teaching methods
|
|
Lecture, Demonstration
|
|
Learning outcomes
|
The course is the second part of two-semester Algorithms and Data Structures course. This part is an introduction to graph theory. It deals with important graph problems and algorithms for their solving.
1. Knowledge Describe the problem of searching.
|
|
Prerequisites
|
unspecified
|
|
Assessment methods and criteria
|
Oral exam
Understanding the elements of graph theory. Mastering the algorithms of graph theory problems.
|
|
Recommended literature
|
-
Aho, A.V., Hopcroft, J.E., Ullman, J.D. (1983). Data Structures and Algorithms. Addison-Wesley.
-
Bhargava, A. Y. (2016). Algorithms.. Manning Publications Co.
-
CORMEN, T. H., LEISERSON C. E., RIVEST D. L., STEIN C. (2001). Introduction to Algorithms, Second Edition. MIT Press.
-
KNUTH, D. (2005). The Art of Computer Programming, Volume 3, Sorting and Searching, Second Edition. Addison-Wesley.
-
Manber U. (1989). Introduction to Algorithms. A creative approach.. Addison-Wesley.
-
Sedgewick, R. (2002). Algorithms in C++ Part 5: Graph Algorithms (3rd Edition). Addison-Wesley.
-
Skiena, S.S. (2012). The Algorithm Design Manual. Springer-Verlag.
|