460-4039/01 – Graph Algorithms (GAL)
Gurantor department | Department of Computer Science | Credits | 4 |
Subject guarantor | RNDr. Eliška Ochodková, Ph.D. | Subject version guarantor | RNDr. Eliška Ochodková, Ph.D. |
Study level | undergraduate or graduate | Requirement | Optional |
Year | | Semester | winter |
| | Study language | Czech |
Year of introduction | 2010/2011 | Year of cancellation | 2010/2011 |
Intended for the faculties | FEI | Intended for study types | Follow-up Master |
Subject aims expressed by acquired skills and competences
After graduation student will be able to:
1. For solving given problems choose proper graph algorithms and implemnt it.
2. Experiment with chosen datasets and analyze achieved results.
3. Interpret experiments results and design possible modifications of used algorithms.
4. Summarize properties of real networks represented by used dataset.
5. Cooperate on project.
Teaching methods
Lectures
Tutorials
Project work
Summary
This course will be concentrating on the basic graph algorithms. Learning and designing efficient algorithms for basic graph theoretic problems that are used as building blocks elsewhere (shortest paths, minimum spanning trees, matching, flows, ...). This course is concerned in models and algorithms for complex networks such as the Web, the internet, social networks and biological networks, too. The goal is to see the common structure and properties that underlie these networks.
Compulsory literature:
1. M. E. J. Newman: The structure and function of complex networks, SIAM Reviews, 45(2): 167-256, 2003
2. A.L. Barabasi: Scale Free Networks
3. S. H. Strogatz: Exploring Complex Networks
4. R. Albert and L.A. Barabasi: Statistical Mechanics of Complex Networks, Rev. Mod. Phys. 74, 47-97 (2002).
7. McHugh J. A.: Algorithmic graph theory, PRENTICE HALL, 1990.
8. Cormen T.H., Leiserson Ch.E., Rivest R.L.: Introduction to algorithms, The MIT Press, 1990.
9. Bang-Jensen J., Guitn G.: Digraphs, Theory, Algorithms and Applications, Springer 2002
10. Jungnickel D.: Graphs, Networks and Algorithms, Springer 2005
Recommended literature:
1. The Stony Brook Algorithm Repository, http://www.cs.sunysb.edu/~algorith/
2. Journal of Graph Algorithms and Applications, ISSN: 1526-1719, http://www.cs.brown.edu/publications/jgaa/
Way of continuous check of knowledge in the course of semester
Conditions for credit - Encompassing chosen project: problem understanding, algorithm selection, implementation, functionality of application, experiments and their results, project presentation.
It is necessary to obtain at least (>=) 23 points from 45 possible.
E-learning
Other requirements
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.
Complex networks.
Common structure of complex networks.
Their properties.
Exercises:
Demonsrarton of particular algorithms.
Projects:
The goal of project is to demonstrate knowledge of graph algorithms through their implemetatation.
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction
Předmět neobsahuje žádné hodnocení.