Introduction to the Theory of Computing 2

1) Basic notions of graph theory: graph, simple graph, degree of a vertex, subgraph, induced subgraph, walk, trail, tour, path, cycle, isomorphism.

2) Connected graph, connected component, tree, spanning tree. Existence of a spanning tree.

3) Storing graphs: adjacency list, adjacency matrix. Directed graphs. Efficiency of graph algorithms. Deciding connectivity, finding a shortest path (with unit edge lengths): Breadth First Search.

4) Computing a minimum weight spanning tree: Kruskal's algorithm.

5) Euleri trails and tours, necessary and sufficient conditions on their existence. Hamiltonian paths and cycles. Necessary conditions on their existence: the maximum number of components after deleting k nodes. Sufficient conditions: theorems of Dirac and Ore.

6) Bipartite graphs, their characterization with odd cycles. Chromatic number. Greedy coloring, upper bound on the chromatic number in terms of the maximum degree. Maximum clique size, its relation to the chromatic number, Zykov's construction.

7) Optimal coloring of interval graphs. Matching, vertex cover, independent set, edge cover. Relation between the sizes of the maximum matching and the minimum vertex cover. Gallai's theorems.

8) Computing a maximum matching in a bipartite graph, the augmenting path algorithm, its optimality. Kőnig's theorem on the equality between the sizes of a maximum matching and a minimum vertex cover.

9) Edge-chromatic number, its relation to the maximum degree, Vizing's theorem.Kőnig's theorem on the edge coloring of bipartite graphs.

10) The maximum flow problem: the notions of network, flow, overall value of a flow. The augmenting path algorithm for computing a maximum flow. The notion of an st-cut of a network, and its capacity.

11) Ford-Fulkerson theorem, Edmonds- Karp theorem. The integer valued maximum flow problem. The problem of edge-disjoint s-t paths, Menger's corresponding theorem.

12) The problem of edge-disjoint paths in undirected graphs, the problems of vertex-disjoint paths in directed and undirected graphs, Menger's corresponding theorems. The notions of k-connectivity and k-edge-connectivity, Menger's corresponding theorems.

13) The shortest path problem with real edge length in directed graphs, the Bellman-Ford algorithm.

14) Summary and review.