Course: MAT 353 3.0 Graph Theory (Compulsory)
Course content: Graphs: Basic Definitions in Graph Theory, Traveling Through a Graph, Connectedness, Euler Tours , Hamiltonian Cycles, Graph Representation, Adjacency Matrices, Adjacency Lists, Planarity of Graphs, Euler’s Formula , Kuratowski’s Theorem, Coloring of Graphs, Vertex Coloring, Edge Coloring, Face Coloring and Chromatic Number, Color Theorems; Trees: Basic Definitions for Trees, Rooted Trees , Ordered Trees, Binary Trees and m-ary Trees, Spanning Trees, Depth First Search, Breadth First Search, Minimum Spanning Trees, Prim’s Algorithm, Kruskal’s Algorithm, Paths and Flows: Shortest Paths and Longest Paths, Dijkstra’s Algorithm , Single-source(sink) Shortest Paths, Multiple-source(Sink) Shortest Paths, Flows, The Ford-Fulkerson Algorithm, The Maxflow-Mincut Theorem, Matching: Matching and Covers, Maximum Matching , Hall’s Matching Condition, Min-Max Theorem , Independent Sets and Covers, Dominating Sets, Algorithms and Applications, Maximum Bipartite Matching, Weighted Bipartite Matching, Stable Matching
Recommended Readings:
Graph Theory and Its Applications by Jonathan L. Gross and Jay Yellon