GRAPH THEORY AND COMBINATIONS
Group A

Graphs and digraphs, subgraphs, degree, walk path, cycle, trees, spanning trees, distance,
connectivity, reactivity and reachability, adjacency matrix.
Eularian paths and circuits in graphs and diagraphs.
Hamiltonian paths and circuits in graphs and tournaments.
Matching, perfect matching, 4-colour theorem, vertex colouring, chromatic polynomial edge
colouring.

Group B


Planar and non-planar graphs, Euler's formula, Kuratowgki's theorem. Network, Max flow-
Min cut theorem. Graph enumeration-Polya's counting theorem. Graph algorithms-shortest path, minimal spanning tree, etc.
Basic combinatorial numbers, recurrence, generating functions, multinomials. Counting
principles. Polya's theorem, inclusion and exclusion principles. Block design and error
correcting codes. Hadamard matrix. Finite geometries.

 

© Copyright 2008. All right reserved - AMIE Students