Credits: 3 (3-0-0)
Prerequisites: COL106
Overlaps with: MTL776
Description
Introduction to Graphs: Definition and basic concepts; Trees:
characterizations, counting of minimum spanning tree; Paths and Distance in Graphs: Basic Definitions, center and median of a graph, activity digraph and critical path; Eulerian Graphs: Definition and Characterization; Hamiltonian Graphs: Necessary and sufficient conditions, Planar Graphs: properties, dual, genus of a graph; Graph Coloring: vertex coloring, chromatic polynomials, edge coloring, planar graph coloring; Matching and Factorizations: maximum matching in bipartite graphs, maximum matching in general graphs, Hall’s marriage theorem, factorization; Networks: The Max-flow min-cut theorem, connectivity and edge connectivity, Menger’s theorem; Graph and Matrices.
Prerequisite Tree
flowchart TD
MTL768-619[MTL768]
COL106-619 --> COL100-619[COL100]
MTL768-619 --> COL106-619[COL106]
classDef empty height:17px, fill:transparent, stroke:transparent;
classDef trueEmpty height:0px, width:0px;