Introduction to the basic concepts and techniques of graph theory, emphasizing precise mathematical descriptions. Uses of theory to design algorithms for graph problems, and to verify their correctness.
Coverage: Paths, circuits, Euler walks. Notions of connectivity and biconnectivity, correlative notions of connected and biconnected components. Basic theory of trees. Spanning trees and their properties, fundamental cycles as basis of a vector space of subgraphs.
Mathematical induction for graphs. Application of mathematical induction to selected problems (coloring, longest path, planarity). Design of recursive algorithms for graphs, using (bi)connected components decomposition. Application to selected problems.
Recursive algorithms for trees, dynamic programming for trees.
Iterative computation for trees. Tree centers.