COURSE

FTEC4270

Introduction to Graph Theory

Society Hub / Financial Technology · 4 Credits

This course is to equip students with basic knowledge of graph theory that will be needed in mathematics, computer science, and engineering (in particular network analysis). Topics include but not restricted to: Euler tours and Chinese postman problem, Hamilton cycles and traveling salesman problem; minimum spanning trees and searching algorithms; block decomposition, ear decomposition, connectivity and edge connectivity; network flows, Ford‐ Fulkerson (Max‐ Flow Min‐ Cut) theorem, augmenting‐ path algorithm; planar graphs, Euler formula, duality, classification of Platonic solids, Kuratowski (planarity) theorem; maximum matchings and perfect matchings, matchings in bipartite graphs, matchings in general graphs, Tutte‐ Berge theorem, Petersen theorem; probabilistic method, page rank problem, random walks; cycle spaces and bond spaces, graph Laplace operator, matrix‐ tree theorem; Four‐ Color problem, colorings and flows, chromatic number and flow number, chromatic polynomials, flow polynomials, Tutte polynomials; matroids.