456-0097/01 – Graph algorithms (GRA)

Gurantor departmentDepartment of Computer ScienceCredits4
Subject guarantorRNDr. Eliška Ochodková, Ph.D.Subject version guarantorRNDr. Eliška Ochodková, Ph.D.
Study levelundergraduate or graduateRequirementChoice-compulsory
Year3Semesterwinter
Study languageCzech
Year of introduction1997/1998Year of cancellation2003/2004
Intended for the facultiesFEIIntended for study typesMaster
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+1

Subject aims expressed by acquired skills and competences

The main goal of this course is to introduce a graph algorithms and their applications to the computer systems.

Teaching methods

Summary

This course covers graph algorithms and applications of graph theory to computer systems.The algorithms are presented in a clear algorithmic style, sometimes with considerable attention to data representation. Favourite algoritms: Depth-first and breadth-first search, classical shortest-path alg., Dijkstra alg., topological oredering alg., coloring and matching of graph (Edmonds matching alg.), network flows.

Compulsory literature:

Cormen, Leiserson, Rivest: Introduction to algorithms, MIT Press, 2001. McHugh J. A.: Algorithmic graph theory, PRENTICE HALL, 1990. Sedgewick R.: Bundle of Algorithms in Java, Third Edition (Parts 1-5): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms, Addison-Wesley 2003. Chartrand, Lesniak: Graphs & Digraphs, CRC Press 1996.

Recommended literature:

Way of continuous check of knowledge in the course of semester

E-learning

Další požadavky na studenta

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

Lectures: Representation of graphs - graphic, adjacency matrix, the edge list, the edge incidence matrix, and the adjacency list. Graph traversal - basic algorithm, depth-first search, breadth-first search. Shortest path - basic algorithm and its modifications, Dijkstra's algorithm, Bellman-Ford's algorithm. Floyd's algorithm and negative cycle testing. Topological ordering of vertices and edges - algorithm of topological ordering and its modifications of searching shortest path. Cycle testing. (Strong) components algorithm - apply Floyd's algorithm. Graph connectivity. Minimum spanning tree. Transitive closure and reduction Matching on a bipartite graphs - maximum matching algorithm on a bipartite graphs, cheapest maximum matching algorithm on a complete bipartite graphs. Maximum matching - maximum matching algorithm of Edmonds. Euler trail - conditions of existence open (closed) euler trail on directed (undirected) connected graphs. Euler trail algorithms. Graph coloring - verticies coloring algorithm, edges coloring algorithm. Algorithm of independent sets. Planar graphs. Network flows - maximum flow algorithm (Ford-Fulkerson algorithm), cheapest maximum flow algorithm. Heuristic algorithms - Hamiltonian paths, isomorphic graphs, independent sets.

Conditions for subject completion

Full-time form (validity from: 1960/1961 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Exercises evaluation and Examination Credit and Examination 100 (145) 51
        Examination Examination 100  0
        Exercises evaluation Credit 45  0
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2003/2004 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava 3 Choice-compulsory study plan
2003/2004 (M2612) Electrical Engineering and Computer Science (2601T004) Measurement and Control Engineering P Czech Ostrava Choice-compulsory study plan
2003/2004 (M2612) Electrical Engineering and Computer Science (2612T018) Electronics and Communication Technology P Czech Ostrava Choice-compulsory study plan
2003/2004 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (10) Elektrické stroje a přístroje P Czech Ostrava Choice-compulsory study plan
2003/2004 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (20) Elektrické pohony a výkonová elektronika P Czech Ostrava Choice-compulsory study plan
2003/2004 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava Choice-compulsory study plan
2003/2004 (M2612) Electrical Engineering and Computer Science (3907T001) Electrical Power Engineering P Czech Ostrava Choice-compulsory study plan
2003/2004 (B2612) Electrical Engineering and Computer Science (1801R001) Computer Science P Czech Ostrava 3 Choice-compulsory study plan
2002/2003 (M2612) Electrical Engineering and Computer Science (2601T004) Measurement and Control Engineering P Czech Ostrava Choice-compulsory study plan
2002/2003 (M2612) Electrical Engineering and Computer Science (2612T018) Electronics and Communication Technology P Czech Ostrava Choice-compulsory study plan
2002/2003 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (10) Elektrické stroje a přístroje P Czech Ostrava Choice-compulsory study plan
2002/2003 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (20) Elektrické pohony a výkonová elektronika P Czech Ostrava Choice-compulsory study plan
2002/2003 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava Choice-compulsory study plan
2002/2003 (M2612) Electrical Engineering and Computer Science (3907T001) Electrical Power Engineering P Czech Ostrava Choice-compulsory study plan
2002/2003 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava 3 Choice-compulsory study plan
2001/2002 (M2612) Electrical Engineering and Computer Science (2601T004) Measurement and Control Engineering P Czech Ostrava Choice-compulsory study plan
2001/2002 (M2612) Electrical Engineering and Computer Science (2612T018) Electronics and Communication Technology P Czech Ostrava Choice-compulsory study plan
2001/2002 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (10) Elektrické stroje a přístroje P Czech Ostrava Choice-compulsory study plan
2001/2002 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (20) Elektrické pohony a výkonová elektronika P Czech Ostrava Choice-compulsory study plan
2001/2002 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava Choice-compulsory study plan
2001/2002 (M2612) Electrical Engineering and Computer Science (3907T001) Electrical Power Engineering P Czech Ostrava Choice-compulsory study plan
2001/2002 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava 3 Choice-compulsory study plan
2000/2001 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava 3 Choice-compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner