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

-