4- Course Content :-
|
Topic |
No. of hours |
Lecture |
Tutorial/Practical |
|
Introducing graphs & algorithmic complexity :- Introducing graphs. Introducing algorithmic complexity. Introducing data structures and depth-first searching. Adjacency matrices and adjacency lists. Depth-first searching. Two linear-time algorithms. |
3 |
3 |
- |
|
Spuming-trees, branching and connectivity :- Spanning-trees and branching. Optimum weight spanning-trees. Optimum branching. Enumeration of spanning-trees. |
3 |
3 |
- |
|
Circuits. cut-sets and connectivity :- Fundamental circuits of a graph. Fundamental cut-sets of a graph. Connectivity. |
3 |
3 |
- |
|
Planar graphs :- Basic properties of planar graphs. Genus, crossing-number and thickness Characterizations of planarity. Dual graphs. planarity testing algorithm. |
3 |
3 |
- |
|
Networks and flows :- Maximizing the flow in a network. Menger's theorems and connectivity. A minimum-cost flow algorithm. |
3 |
3 |
- |
|
Matching :- Definitions. Maximum-cardinality matching. Perfect matching. Maximum-weight matching. |
3 |
3 |
- |
|
Eulerian paths and circuits :- Eulerian graphs. Finding Eulerian circuits. Postman problems :- Counting Eulerian circuits. The Chinese postman problem for undirected graphs. The Chinese postman problem for digraphs. |
3 |
3 |
- |
|
Hamiltonian tours :- Some elementary existence theorems. Finding all Hamiltonian tours by matricial products. The travelling salesman problem. factors of a graph. |
3 |
3 |
- |
|
Coloring graphs :- Dominating sets. independence and cliques. Coloring graphs. Edge-coloring. |
3 |
3 |
- |
|
Vertex-coloring. Chromatic polynomials. Face- colorings of embedded graphs. The five-color theorem. The four-color theorem. |
3 |
3 |
- |
|
Graph problems and Intractability :- Introduction to NP-completeness. The classes P and NP. NP-completeness and Cook's theorem. NP-complete graph problems. |
3 |
3 |
- |
|
Problems of vertex cover. independent set and clique. Problems of Hamiltonian paths and circuits and the travelling salesman problem. Problems concerning the coloring of graphs. |
3 |
3 |
- |