Graph Theory ((4 Credits))

Catalog description

Topics covered in this course include: graphs as models, paths, cycles, directed graphs, trees, spanning trees, matchings (including stable matchings, the stable marriage problem and the medical school residency matching program), network flows, and graph coloring (including scheduling applications). Students will explore theoretical network models, such as random graphs, small world models and scale-free networks, as well as networked datasets from social, infrastructure and information networks, the role of strong and weak ties, triadic closure, and centrality measures, as well as the fragility of networked systems and contagious process on networks of various topologies. This knowledge may be obtained from a course such as Discrete Mathematics, for example. This course contains elements which rely on vision to complete. If you have a visual impairment and are considering registering for this course, it is recommended that you reach out to Accessibility Resources and Services ([email protected]) in advance of registration to determine if this course is appropriate and what alternatives may be available. This course was previously SMT-273244. Prerequisites: Discrete Math Foundations of mathematics and mathematical proof: logic, methods of proof (both inductive and deductive), sets, relations and functions.