Graph Terminology and Data Structures: Graphs, Graph Models, Adjacency and Incidence, Degree, Computer representation of graphs: Adjacency matrix, Incidence matrix, circuit matrix, adjacency list, Isomorphism, Permutation algorithm for graph isomorphism, Sub graphs, Walks, Paths, Circuits, Connected graphs, Components, Adjacency matrix algorithm for connectedness, Fusion algorithm for the connectedness and components, Operations on graphs: Union, Ring-Sum, Fusion, Join and Product, Algorithm for the graph operations, Complete graphs, Bipartite graphs, Directed Graphs, in-degree, out-degree, directed paths, directed cycles, DFS & BFS traversals for graphs and digraphs, Strong and weak connectivity in digraphs, Algorithm for the strong components of a digraph, Matrices and adjacency lists of digraphs.
Shortest Path Algorithms &Traversability: Shortest Path, distances, eccentricity, shortest path algorithms, Dijkstra’s algorithm for the single source shortest paths, Application of the Dijkstra’s algorithm to the shortest path routing in the Computer Networks, Floyd’s algorithm for all pair shortest paths and eccentricities, Euler graphs, Characterization of Euler graphs, Chinese Postman problem, Randomly Euler graphs and Exhibition hall design problem, Algorithm for Euler tours, Euler digraphs, Teleprinter’s problem, Hamiltonian paths and circuits, Traveling salesman problem, Grey Codes and Hamilton cycles of Hyper Cubes, Matricial Product algorithm for all Hamilton cycles.
Trees & Applications: Trees, Properties, Rooted trees, Rooted & Binary Trees, Prefix codes, Binary codes, Huffman’s Algorithm, Spanning trees, Kruskal’s& Prim’s algorithms for the optimal spanning tree, Activity Networks in Project management, Topological sorting, CPM Algorithm for Activity Networks, Arborescence, Prefix, in-fix and postfix Tree traversals, Expression trees, Polish notation, Matrices of digraphs, Acyclic digraphs, decyclization, Graphs in Computer Programming, Fundamental cycles, algorithm for the fundamental cycles, Fundamental cut sets, algorithm for the fundamental cut sets, Vectors & Vector spaces of a graph, cycle & cut-set vector spaces of a graph. Connectivity, Networks & Combinatorial Optimization: Cut vertices, Bi-connected graphs, algorithm for cut vertices and biconnected graphs, Vertex & Edge connectivity, Menger’s Theorem (Statement only), Network flows, Ford and Fulkerson’s Theorem (Statement only), Edmonds-Karp Algorithm for the maximal network flow, Network Simplex algorithm for the minimum cost flow, Matching, Perfect matching, Hall’s marriage theorem, Edmond’s Algorithm for the maximum cardinality matching, Independent set, Covering, Clique, Dominating Set.
Planarity, Coloring & Intractable graph problems: Planar graphs, Kuratowski graphs, Different representations of planar graphs, DMP Algorithm for the Planarity detection, Geometric dual, Coloring, chromatic number, Four color theorem (Statement only), Grundy coloring, time table scheduling problem, chromatic polynomials, Algorithmic complexity, growth rates, P, NP, NPC classes, Cook’s theorem (Statement only), NPC reduction, NPC Graph problems.