CS40021: Applied Graph Theory
| CS40021 | |
|---|---|
| Course name | Applied Graph Theory |
| Offered by | Computer Science & Engineering |
| Credits | 4 |
| L-T-P | 3-1-0 |
| Previous Year Grade Distribution | |
| {{{grades}}} | |
| Semester | Autumn |
Syllabus[edit | edit source]
Syllabus mentioned in ERP[edit | edit source]
Fundamental concepts (basic definitions, operations, properties, proof styles); Trees (properties, distances and centroids, spanning trees, enumeration); Matchings (bipartite graphs, general graphs, weighted matching); Connectivity (vertex and edge connectivity, cuts, blocks, k-connected graphs, network flows); Traversibility (Eulerian tours, Hamiltonian cycles); Coloring (vertex and edge coloring, chromatic number, chordal graphs); Planarity (duality, Euler s formula, characterization, 4-color theorem); Advanced topics (perfect graphs, matroids, Ramsay theory, extremal graphs, random graphs); Applications.References1.Douglas B. West, Introduction to Graph Theory, Prentice Hall of India.2.Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science. Prentice-Hall.3.Frank Harary, Graph Theory, Narosa.4.R. Ahuja, T. Magnanti, and J. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall.