Introduction to the Theory of Computing 2

1) Basics of combinatorics: permutations, variations and combinations with and without repetition. Relations between binomial coefficients, Pascal's triangle, binomial theorem.

2) Basic notions of graph theory: graph, simple graph, degree of a vertex, walk, path, cycle, connected graph, connected component, tree, spanning tree. Deciding connectivity, finding a shortest path (with unit edge lengths): Breadth First Search.

3) Computing a minimum weight spanning tree: Kruskal's algorithm. The notion of a planar graph, equivalence with graphs drawable on a sphere, Euler's polyhedron formula.

4) Relation between the number of nodes and edges of a simple, planar graph. The non-planarity of the K₅ and K_3,3 graphs, Kuratowski's theorem. The dual of a planar graph, correspondences between the number of vertices/edges/regions, the image of cycles and cuts.

5) The notions of Eulerian path and Eulerian cycle, necessary and sufficient conditions on their existence. The notions of Hamiltonian path and Hamiltonian cycle. Necessary conditions on their existence: the maximum number of components after deleting k nodes. Sufficient conditions: theorems of Dirac and Ore.

6) The notion of a bipartite graph, their characterization with odd cycles. The notion of chromatic number. Greedy coloring, upper bound on the chromatic number in terms of the maximum degree. The notion of maximum clique size, relation to the chromatic number, Mycielski's construction.

7) Optimal coloring of interval graphs. The notions of matching, vertex cover, independent set and 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. Tutte's theorem.

9) The notion of edge-chromatic number, its relation to the maximum degree, Vizing's theorem. The maximum flow problem: the norions of network, flow, overall value of a flow, the augmenting path algorithm for computing a maximum flow.

10) The notions of an st-cut of a network, and its capacity, the Ford-Fulkerson theorem, the Edmonds- Karp theorem. The integer valued maximum flow problem. The problem of edge-disjoint s-t paths, Menger's corresponding theorem.

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

12) The shortest path problem in undirected and directed graphs with positive edge lengths, and with real edge length in directed graphs, the algorithms of Dijsktra, Ford and Floyd.

13) Depth First Search in undirected and directed graphs, deciding the existence of directed cycles. Acyclic directed graphs, topological ordering. The shortest and longest path problem in acyclic directed graphs.

14) Summary and review.