COURSE OBJECTIVES

• Learn and Know about important classes of graph problems.
• Understand basic algorithms for graph.
• Learn to use graph algorithms as a modelling tool.
• Apply strong background of graphs and graphs algorithms knowledge to solve problems of computer science, biology, sociology and engineering

COURSE LEARNING OUTCOMES (CLO)


CLO: 1. Learn and Recognize the basics of graphs, graph algorithms.
CLO: 2. How to analyze graph algorithms and estimate their cost.
CLO: 3. CLO:3. Apply the concepts of graphs by using different programming techniques

COURSE CONTENTS


• Graphs Algorithms Basic Introduction, Graphs Introduction and Formal Definition, Graph Problems, Graphs Basic Definitions: Finite Graphs and Infinite Graphs, Complete Graphs, Bipartite Graphs and Complete Bipartite Graphs, Multi graphs, Directed Graphs, Planer Graphs
• Graphs Definitions and Concepts: Planar Graphs. Sub graphs, Induced sub graphs, Spanning Sub graphs, Incident, Adjacent, Degree, Regular Graphs, Graph Isomorphism, Walk, Path, Circuits
• Graph components, Connected Graphs, Disconnected Graphs
• Graph centralities: Betweenness centrality, Degree Centrality, Closeness Centrality, Directed Graphs
• Eulerian Graph, Fleury’s Algorithm for Euler Circuit
• Hamiltonian Graph with Examples, Euler Circuits
• Travelling Sales Man Problem
• Shortest Path Algorithms, Floyd and Warshall
• Dijkstra Algorithms, Bellman ford, Spanning Graph
• Spanning Trees, Maximum Spanning Trees, Prims Algorithm, Kruskal Algorithm
• Breadth First Search
• Depth First Search, Depth First Search for Digraphs
• Flow networks, Edge Connectivity
• Vertex Coloring, Edge Coloring
• Modeling problems using graphs Social network analysis
• Image processing, Graph databases, Graph Mining, Organization structure using graphs, Web graph, Social Network Analysis