Syllabus
Review of Graphs: Graphs and Sub graphs, isomorphism, matrices associated with graphs, degrees, walks, connected graphs, shortest path algorithm. Eccentricity.
Trees: Trees, cut-edges and cut-vertices, spanning trees, minimum spanning trees, DFS, BFS algorithms.
Connectivity: Graph connectivity, k-connected graphs and blocks.
Euler and Hamilton Graphs: Euler graphs, Euler’s theorem. Hamilton cycles, Chinese-postman problem, approximate solutions of traveling salesman problem. Closest neighbour algorithm.
Matching and Colorings: Matchings, maximal matchings. Coverings and minimal coverings. Graph Dominations and Independent sets. Vertex colorings, Planar graphs. Euler theorem on planar graphs.
Large Scale networks: Introduction. Graph and Networks. Network topologies. Examples of large-scale networks and networked systems. Power Law distributions. Scale-free networks. Random graph models for large networks: Erdos-Renyi graphs, power-law graphs, small world graphs, phase transitions. Network stabilities.
Graph Networks and Centralities: Degree and distance centralities. Closeness centrality. Betweeness centrality. Eigenvector centrality and Page ranking algorithm and applications. Clustering coefficient and clustering centrality. Introduction to community detections.
Case Studies: Implementation of the centralities and community detection algorithms with Transport networks, Biological networks, ect.,