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.
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.