MA6230 GRAPH THEORY Basics: subgraphs, isomorphism,
automorphism group, matrices associated with graphs, degrees, walks,
connected graphs, shortest path algorithms. Bipartite
graphs: characterization,
trees, cut-edges and cut-vertices, spanning trees, minimum spanning trees,
DFS, BFS algorithms Connectivity: k-connected graphs,
characterization of 2-connected graphs Euler and
Hamilton graphs:
characterization of Euler graphs, necessary/ sufficient conditions for the
existence of Hamilton cycles, Fleury's algorithm for eulerian trails,
Chinese-postman-problem (complete algorithmic solution), approximate
solutions of traveling salesman problem Matchings: Berge's theorem, Hall's theorem, Tutte’s perfect
matching theorem, k-matchings (reduction to perfect matching problem),
job-assignment- problem Books: (1) J.A. Bondy and U.S.R. Murty: Graph Theory and
Applications (Freely downloadable from Bondy's website) (2) D.B. West:
Introduction to graph theory, P.H.I. (2004) |