Introduction and fundamental concepts, Structure and basic definition in graph theory, methodology, proofs, basic properties of graphs; graph operations and their symbolic designation. Orientation of graphs, associated matrices and their relationship. Groups; automorphism groups, symmetric graps, graph enumeration, Polya's power group enumeration theorem. Colourability : five colour theorem, four colour conjecture, Heawood map colouring theorem, critical graphs, homomorphism, chromatic polynomial. Graph algorithms: DFS for non-separable components, orderer trees, application of Hoffman tree to sort by merge technique, Catalan numbers, maxflow problem, Ford and Flukerson's algorithms, Dinic's algorithm, Zero-one net flow, maximum matching in bipartite graphs, NP-complete problems, vertex cover, Hamiltonian paths and circuits, colouring, Steiner tree; max-cut, multicommodity integral flow.

- None

Course Type | Major |
---|---|

Credit Hour | 3 |

Lecture Hour | 45 |