1. Sets, sub-sets & operations on sets – Finite and infinite sets – Relations & Properties of relations – equivalence relation - Groups- Rings and Fields.
2. Partial order relation, Poset, hub, glb, maximal and minimal elements of a poset – Definition & example of Boolean algebra – Lattices, Distributive laws in lattices – Complemented lattices – Propositional Calculus – Boolean functions, minimum & maximum terms, simplification of Boolean function with Karnaugh map & Quiane Mc Clusky method
3. Basic theorems on permutations & combinations – Pigeon hole principle, principle of inclusion and exclusion – Ordinary and exponential generating functions – Recurrence equations
4. Basic definitions of Graphs, connectivity of a graph, cut points, cycles – Hamiltonian graphs – sub graphs - spanning sub graphs - isomorphic graphs - matrix representation of graphs, Fusion - fusion algorithm, Bipartite graphs, Tree, different characterization of trees Algorithms on graphs – Breadth First Search and Depth First Search, Dijkstra’s algorithm for shortest path, Floyd’s algorithm for all pairs of shortest paths, Kruskal’s and Prim’s algorithm for minimum spanning tree
5. Graph coloring and chromatic polynomials-network flows-maxflow-min cut theorem, Ford and Fulkerson algorithm, separating sets, Basic concepts of Median graphs
|
1. Discrete Computational Structures (2nd Ed): Robert R. Korfhage , Academic Press (1984)
2. Rings, Fields and Groups: An Introduction to Abstract Algebra (2nd Ed): Reg Allenby (1999)
3. Elements of Discrete Mathematics (1st Ed): L CL Liu, McGraw-Hill (1985)
4. Discrete Mathematical Structures for Computer Science (1st Ed): Bernard Kolman, Robert Busby, PHI (1987)
5. First look at graph theory (1st Ed): John Clark & Derek Allan Holton, Allied Publishers (1995)
6. Graph Theory with Applications to Engineering & Computer Science: Narsingh Deo, PHI (2004)
|